DaniWeb Forum Index > Software Development > C++

C++ RSS

Linked List - Need help deleting!

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Jul 2005

Posts: 1,692

Reputation: Lerner is a name known to all

Solved Threads: 268

Lerner

Offline

Posting Virtuoso

Re: Linked List - Need help deleting!

#11

Nov 20th, 2008

Or something like that yes.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
node * currentNode
node * previousNode
 
//where to start
currentNode = first;
 
//find desired node
while(currentNode != NULL && currentNode->id != id)
  previousNode = currentNode;
  currentNode = currentNode->next;
 
//when loop stops, evaluate why.
if(currentNode == NULL)
  id not found in list
//else id found so now do the deletion part
node * currentNode
node * previousNode

//where to start
currentNode = first;

//find desired node
while(currentNode != NULL && currentNode->id != id)
  previousNode = currentNode;
  currentNode = currentNode->next;

//when loop stops, evaluate why.
if(currentNode == NULL)
  id not found in list
//else id found so now do the deletion part

Last edited by Lerner; Nov 20th, 2008 at 7:11 pm.

Klatu Barada Nikto

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#12

Nov 21st, 2008

•

Originally Posted by Lerner

Or something like that yes.
Help with Code Tags

C++ Syntax (Toggle Plain Text)
node * currentNode
node * previousNode
 
//where to start
currentNode = first;
 
//find desired node
while(currentNode != NULL && currentNode->id != id)
  previousNode = currentNode;
  currentNode = currentNode->next;
 
//when loop stops, evaluate why.
if(currentNode == NULL)
  id not found in list
//else id found so now do the deletion part
node * currentNode node * previousNode //where to start currentNode = first; //find desired node while(currentNode != NULL && currentNode->id != id) previousNode = currentNode; currentNode = currentNode->next; //when loop stops, evaluate why. if(currentNode == NULL) id not found in list //else id found so now do the deletion part

I tried to follow what you told me to do, but now it doesn't delete anything on the list at all. Is there something I did wrong in the code?

Here is the program with deleteSong function updated:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include <string>
 
const int SONGS = 2;
 
using namespace std;
struct mp3Type
{
    int id;
    string songTitle;
    string artist;
    string length;
    string size;
    mp3Type *link,*next;
};
 
 
void addSong(mp3Type*& first, mp3Type*& last);
void deleteSong(mp3Type*& first);
void modifySong(mp3Type*& first, mp3Type*& last);
void printSong(mp3Type*& first);
 
 
int main()
{
	mp3Type *first, *last,*next;
	char selection;
 
 
	do
	{
         cout<<"a - Add a song "<<endl;
         cout<<"d - Delete a song"<<endl;
         cout<<"m - Modify a song's information "<<endl;
         cout<<"p - Print a list of songs "<<endl;
         cout<<"q - Quit "<<endl;
         cin>>selection;
         switch(selection)
         {
                          case 'a': addSong(first,last);
                               break;
                          case 'd': deleteSong(first);
                               break;
                          case 'm': modifySong(first,last);
                               break;
                          case 'p': printSong(first);
                               break;
                          case 'q': 
                               break;
                          default: cout<<"Invalid option "<<endl;
         }
     }
          while (selection != 'q');
 
 
         	system("PAUSE");
	        return 0;
}
 
void addSong(mp3Type*& first, mp3Type*& last)
{
 
 
    int id;
    char songTitle[100];
    char artist[100];
    string length;
    string size;
    mp3Type *newNode;
    char selection;
 
    first = NULL;
    last = NULL;
 
 
 
        for (int i = 0; i < SONGS; i++)
         {
         cout<<endl;
         cout<<"Adding song # "<<i+1<<endl;
         cout<<endl;
         cout<<"\nSong title: ";
         std::cin.getline(songTitle, 100);
         std::cin.getline(songTitle, 100);
         cout<<"ID: ";
         cin>>id;
         cout<<"Artist: ";
         std::cin.getline(artist, 100);
         std::cin.getline(artist, 100);; 
         cout<<"Length: ";
         cin>>length;
         cout<<"Size: ";
         cin>>size;
 
         newNode = new mp3Type; // create new node
         newNode->songTitle = songTitle;
         newNode->id = id;
         newNode->artist = artist;
         newNode->length = length;
         newNode->size = size;
         newNode->link = NULL;
 
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
         }
 
}
 
void deleteSong(mp3Type*& first)
{
 
  mp3Type *last,*current,*trailcurrent,*previous,*next;
  bool found;
  int id;
 
  current = first;
 
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
 
 
         while(current != NULL && current->id != id)
            {
          previous = current;
          current = current->next;
 
        if(current == NULL)
         {
           found = false;
         }
         else
         {
         found = true;
         delete current;
         }
         }   
 
 
}
 
void modifySong(mp3Type*& first, mp3Type*& last)
{
 
   int id;
   char newsongTitle[100];
   char newartist[100];
   string newlength;
   string newsize;
   bool found = false;
   mp3Type *current;
 
   printSong(first);
 
   current = first;
 
 
   cout<<"Enter the id of the song to modify information"<<endl;
   cin>>id;
 
 
   while (current != NULL)
   {         
    if (current->id == id)
    {
         cout<<endl;
         cout<<"Song title: ";
         std::cin.getline(newsongTitle, 100);
         std::cin.getline(newsongTitle, 100);
         cout<<"Artist: ";
         std::cin.getline(newartist, 100);
         cout<<"Length: ";
         cin>>newlength;
         cout<<"Size: ";
         cin>>newsize;
 
     current->songTitle = newsongTitle;
     current->artist = newartist;
     current->length = newlength;
     current->size = newsize;
    } 
   current = current->link; 
    }
 
}
 
void printSong(mp3Type*& first)
{
 
     cout<<"Printing song list..."<<endl;
     mp3Type *current;
 
 
        current = new mp3Type;
        current = first;    
        while (current != NULL)
        {
          cout<<endl;
          cout<<current-> songTitle <<endl;
          cout<<current-> id <<endl;
          cout<<current-> artist <<endl;
          cout<<current-> length <<endl;
          cout<<current-> size <<endl;
          cout<<endl;
          current = current->link;
        }
 
 
}
#include <iostream>
#include <string>

const int SONGS = 2;

using namespace std;
struct mp3Type
{
    int id;
    string songTitle;
    string artist;
    string length;
    string size;
    mp3Type *link,*next;
};


void addSong(mp3Type*& first, mp3Type*& last);
void deleteSong(mp3Type*& first);
void modifySong(mp3Type*& first, mp3Type*& last);
void printSong(mp3Type*& first);


int main()
{
	mp3Type *first, *last,*next;
	char selection;
	
	
	do
	{
         cout<<"a - Add a song "<<endl;
         cout<<"d - Delete a song"<<endl;
         cout<<"m - Modify a song's information "<<endl;
         cout<<"p - Print a list of songs "<<endl;
         cout<<"q - Quit "<<endl;
         cin>>selection;
         switch(selection)
         {
                          case 'a': addSong(first,last);
                               break;
                          case 'd': deleteSong(first);
                               break;
                          case 'm': modifySong(first,last);
                               break;
                          case 'p': printSong(first);
                               break;
                          case 'q': 
                               break;
                          default: cout<<"Invalid option "<<endl;
         }
     }
          while (selection != 'q');
          
          
         	system("PAUSE");
	        return 0;
}

void addSong(mp3Type*& first, mp3Type*& last)
{
     
     
    int id;
    char songTitle[100];
    char artist[100];
    string length;
    string size;
    mp3Type *newNode;
    char selection;
    
    first = NULL;
    last = NULL;
    
    
      
        for (int i = 0; i < SONGS; i++)
         {
         cout<<endl;
         cout<<"Adding song # "<<i+1<<endl;
         cout<<endl;
         cout<<"\nSong title: ";
         std::cin.getline(songTitle, 100);
         std::cin.getline(songTitle, 100);
         cout<<"ID: ";
         cin>>id;
         cout<<"Artist: ";
         std::cin.getline(artist, 100);
         std::cin.getline(artist, 100);; 
         cout<<"Length: ";
         cin>>length;
         cout<<"Size: ";
         cin>>size;
  
         newNode = new mp3Type; // create new node
         newNode->songTitle = songTitle;
         newNode->id = id;
         newNode->artist = artist;
         newNode->length = length;
         newNode->size = size;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
         }
     
}

void deleteSong(mp3Type*& first)
{
     
  mp3Type *last,*current,*trailcurrent,*previous,*next;
  bool found;
  int id;

  current = first;
  
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
    
  
         while(current != NULL && current->id != id)
            {
          previous = current;
          current = current->next;

        if(current == NULL)
         {
           found = false;
         }
         else
         {
         found = true;
         delete current;
         }
         }   
         
     
}

void modifySong(mp3Type*& first, mp3Type*& last)
{
     
   int id;
   char newsongTitle[100];
   char newartist[100];
   string newlength;
   string newsize;
   bool found = false;
   mp3Type *current;
   
   printSong(first);
   
   current = first;
   
   
   cout<<"Enter the id of the song to modify information"<<endl;
   cin>>id;
     
     
   while (current != NULL)
   {         
    if (current->id == id)
    {
         cout<<endl;
         cout<<"Song title: ";
         std::cin.getline(newsongTitle, 100);
         std::cin.getline(newsongTitle, 100);
         cout<<"Artist: ";
         std::cin.getline(newartist, 100);
         cout<<"Length: ";
         cin>>newlength;
         cout<<"Size: ";
         cin>>newsize;
     
     current->songTitle = newsongTitle;
     current->artist = newartist;
     current->length = newlength;
     current->size = newsize;
    } 
   current = current->link; 
    }

}

void printSong(mp3Type*& first)
{
     
     cout<<"Printing song list..."<<endl;
     mp3Type *current;
        
        
        current = new mp3Type;
        current = first;    
        while (current != NULL)
        {
          cout<<endl;
          cout<<current-> songTitle <<endl;
          cout<<current-> id <<endl;
          cout<<current-> artist <<endl;
          cout<<current-> length <<endl;
          cout<<current-> size <<endl;
          cout<<endl;
          current = current->link;
        }
     

}

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#13

Nov 21st, 2008

Here is my deleteSong function that I updated. It is still not deleting the node that the user input. I have been trying to figure this out for week. This is frustrating..

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void deleteSong(mp3Type*& first)
{
 
  mp3Type *last,*current,*trailcurrent,*previous,*next;
  bool found;
  int id;
 
  current = first;
 
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
 
 
         while(current != NULL && current->id != id)
            {
          previous = current;
          current = current->next;
            }
        if(current == NULL)
         {
           found = false;
         }
         else
         {
         found = true;
         delete current;
         }
 
 
 
}
void deleteSong(mp3Type*& first)
{
     
  mp3Type *last,*current,*trailcurrent,*previous,*next;
  bool found;
  int id;

  current = first;
  
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
    
  
         while(current != NULL && current->id != id)
            {
          previous = current;
          current = current->next;
            }
        if(current == NULL)
         {
           found = false;
         }
         else
         {
         found = true;
         delete current;
         }
         
         
     
}

•

Join Date: Jul 2008

Posts: 332

Reputation: cikara21 is an unknown quantity at this point

Solved Threads: 64

cikara21

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#14

Nov 21st, 2008

here's a simple sample code...
i don't test it yet

...
let me know the result...

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
void push_back(mp3Type **p_type, int _id, string _sTitle, string _artist, string _length, string _size)
{
       mp3Type *p = new mp3Type;
       if (&p == NULL)
           return;
       p->id = _id;
       p->songTitle = _sTitle;
       p->artist = _artist;
       p->length = _length;
       p->size = _size;
       p->next = *p_type;
       *p_type = p;
} 
 
void delete(mp3Type *p_type, mp3Type **ret_Type)
{
       mp3Type *t, *n;
       t = p_type;
       int id = 0;
       cout<<"Enter song ID that you like to delete"<<endl;
       cout<<endl;
       cin>>id;
       while (t != NULL)
       {
             if (t->id == id)
             {
                   t = t->next;
                   continue; //-- pass
             }
             int t_id = t->id;
             string t_sTitle = t->songTitle;
             string t_artist = t->artist;
             string t_length = t->length;
             string t_size = t->size;
             push_back(&n,t_id,t_sTitle,t_artist,t_length,t_size);
             t = t->next;  
       }
       *ret_Type = n;
}
 
//--
//-- To call delete
//-- mp3Type *main_Type, *temp_Type;
//-- delete(main_Type, &temp_Type);
//--
void push_back(mp3Type **p_type, int _id, string _sTitle, string _artist, string _length, string _size)
{
       mp3Type *p = new mp3Type;
       if (&p == NULL)
           return;
       p->id = _id;
       p->songTitle = _sTitle;
       p->artist = _artist;
       p->length = _length;
       p->size = _size;
       p->next = *p_type;
       *p_type = p;
} 

void delete(mp3Type *p_type, mp3Type **ret_Type)
{
       mp3Type *t, *n;
       t = p_type;
       int id = 0;
       cout<<"Enter song ID that you like to delete"<<endl;
       cout<<endl;
       cin>>id;
       while (t != NULL)
       {
             if (t->id == id)
             {
                   t = t->next;
                   continue; //-- pass
             }
             int t_id = t->id;
             string t_sTitle = t->songTitle;
             string t_artist = t->artist;
             string t_length = t->length;
             string t_size = t->size;
             push_back(&n,t_id,t_sTitle,t_artist,t_length,t_size);
             t = t->next;  
       }
       *ret_Type = n;
}

//--
//-- To call delete
//-- mp3Type *main_Type, *temp_Type;
//-- delete(main_Type, &temp_Type);
//--

Last edited by cikara21; Nov 21st, 2008 at 4:21 am.

$.:-cikara21-:.$

•

Join Date: Jul 2005

Posts: 1,692

Reputation: Lerner is a name known to all

Solved Threads: 268

Lerner

Offline

Posting Virtuoso

Re: Linked List - Need help deleting!

#15

Nov 21st, 2008

Unless you plan to use the variable called found somewhere there is no sense declaring it, changing it's value, etc.

There is a reason why previousNode is included in the pseudocode. It's because you need to know which node is the one just before the current node in order to connect it with the one just after the current node. That way when you delete the current node the list remains intact, you haven't created two separate lists from the original.

Since the first node in the list doesn't have a previous node you don't need to reconnect previous to next when you delete it, you can just reassign.

The last node in the list doesn't have a node after it. Won't that need to be handled as a special case, too? No it won't. At least it won't if you make sure all pointers to node in new nodes are assigned the value NULL when the new node is declared. If that's done then NULL can be assigned to the previous node just like an actual node.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if(currentNode == NULL)
  //id not in list
//if id is in the first node
else if(currentNode == first)  OR
else if(previousNode == NULL) //assuming previous is defaulted to NULL on declaration
  //reassign second node in list to be first
  //delete current node
else //id is in list and it's not in the first position
  //assign node after current node to node previous to current node
  //delete current node
if(currentNode == NULL)
  //id not in list
//if id is in the first node
else if(currentNode == first)  OR
else if(previousNode == NULL) //assuming previous is defaulted to NULL on declaration
  //reassign second node in list to be first
  //delete current node
else //id is in list and it's not in the first position
  //assign node after current node to node previous to current node
  //delete current node

This algorhithm works well for deleting the first instance of id in the list. It can be modified slightly if you want to delete all instances of id in the list.

Last edited by Lerner; Nov 21st, 2008 at 11:32 am.

Klatu Barada Nikto

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#16

Nov 21st, 2008

•

Originally Posted by cikara21

here's a simple sample code...
i don't test it yet ...
let me know the result...
Help with Code Tags

c++ Syntax (Toggle Plain Text)
void push_back(mp3Type **p_type, int _id, string _sTitle, string _artist, string _length, string _size)
{
       mp3Type *p = new mp3Type;
       if (&p == NULL)
           return;
       p->id = _id;
       p->songTitle = _sTitle;
       p->artist = _artist;
       p->length = _length;
       p->size = _size;
       p->next = *p_type;
       *p_type = p;
} 
 
void delete(mp3Type *p_type, mp3Type **ret_Type)
{
       mp3Type *t, *n;
       t = p_type;
       int id = 0;
       cout<<"Enter song ID that you like to delete"<<endl;
       cout<<endl;
       cin>>id;
       while (t != NULL)
       {
             if (t->id == id)
             {
                   t = t->next;
                   continue; //-- pass
             }
             int t_id = t->id;
             string t_sTitle = t->songTitle;
             string t_artist = t->artist;
             string t_length = t->length;
             string t_size = t->size;
             push_back(&n,t_id,t_sTitle,t_artist,t_length,t_size);
             t = t->next;  
       }
       *ret_Type = n;
}
 
//--
//-- To call delete
//-- mp3Type *main_Type, *temp_Type;
//-- delete(main_Type, &temp_Type);
//--
void push_back(mp3Type **p_type, int _id, string _sTitle, string _artist, string _length, string _size) { mp3Type *p = new mp3Type; if (&p == NULL) return; p->id = _id; p->songTitle = _sTitle; p->artist = _artist; p->length = _length; p->size = _size; p->next = *p_type; *p_type = p; } void delete(mp3Type *p_type, mp3Type **ret_Type) { mp3Type *t, *n; t = p_type; int id = 0; cout<<"Enter song ID that you like to delete"<<endl; cout<<endl; cin>>id; while (t != NULL) { if (t->id == id) { t = t->next; continue; //-- pass } int t_id = t->id; string t_sTitle = t->songTitle; string t_artist = t->artist; string t_length = t->length; string t_size = t->size; push_back(&n,t_id,t_sTitle,t_artist,t_length,t_size); t = t->next; } *ret_Type = n; } //-- //-- To call delete //-- mp3Type *main_Type, *temp_Type; //-- delete(main_Type, &temp_Type); //--

That is code is hard for me to understand.

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#17

Nov 21st, 2008

•

Originally Posted by Lerner

Unless you plan to use the variable called found somewhere there is no sense declaring it, changing it's value, etc.

There is a reason why previousNode is included in the pseudocode. It's because you need to know which node is the one just before the current node in order to connect it with the one just after the current node. That way when you delete the current node the list remains intact, you haven't created two separate lists from the original.

Since the first node in the list doesn't have a previous node you don't need to reconnect previous to next when you delete it, you can just reassign.

The last node in the list doesn't have a node after it. Won't that need to be handled as a special case, too? No it won't. At least it won't if you make sure all pointers to node in new nodes are assigned the value NULL when the new node is declared. If that's done then NULL can be assigned to the previous node just like an actual node.
Help with Code Tags

C++ Syntax (Toggle Plain Text)
if(currentNode == NULL)
  //id not in list
//if id is in the first node
else if(currentNode == first)  OR
else if(previousNode == NULL) //assuming previous is defaulted to NULL on declaration
  //reassign second node in list to be first
  //delete current node
else //id is in list and it's not in the first position
  //assign node after current node to node previous to current node
  //delete current node
if(currentNode == NULL) //id not in list //if id is in the first node else if(currentNode == first) OR else if(previousNode == NULL) //assuming previous is defaulted to NULL on declaration //reassign second node in list to be first //delete current node else //id is in list and it's not in the first position //assign node after current node to node previous to current node //delete current node
This algorhithm works well for deleting the first instance of id in the list. It can be modified slightly if you want to delete all instances of id in the list.

Do I need to have "next" anymore? The last time I tried to include it, it said that it wasn't an mp3Type

•

Join Date: Jul 2005

Posts: 1,692

Reputation: Lerner is a name known to all

Solved Threads: 268

Lerner

Offline

Posting Virtuoso

Re: Linked List - Need help deleting!

#18

Nov 21st, 2008

You may use either link or next, but I wouldn't use both. They serve the same purpose. I usually use the name next but the name link makes sense too. It makes it harder for requestors of homework help to just cut and paste if answers I don't use all the same variable names they use. Hopefully, this forces the requestors learn soemthing about the concepts rather than the specifics when it comes to common algorithms. With the more complicated stuff that clearly isn't homework, then I'm more comfortable using the same names for all the variables as the requestor.

Klatu Barada Nikto

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#19

Nov 21st, 2008

Should I use bool found?

•

Join Date: Mar 2008

Posts: 370

Reputation: NinjaLink is an unknown quantity at this point

Solved Threads: 0

NinjaLink

Offline

Posting Whiz

Re: Linked List - Need help deleting!

#20

Nov 21st, 2008

I got it so that it deletes the first node, but the rest are still on the list. When I delete the first node though and then print the list, the first node is delete, but , the thing is, it leaves a piece of junk behind.

Here is my updated deleteSong function:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void deleteSong(mp3Type*& first)
{
 
  mp3Type *last,*current,*trailcurrent,*previous;
  int id = 0;
  bool found = false;
 
  current = first;
 
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
 
 
        while(current == NULL && current->id != id)
         {
         previous = current;
         current = current->link;
         }
         if (current == NULL)
         {
         found = false;      
         }
         else
         {
         found = true;
         delete current;
         }
}
void deleteSong(mp3Type*& first)
{
     
  mp3Type *last,*current,*trailcurrent,*previous;
  int id = 0;
  bool found = false;

  current = first;
  
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
    

        while(current == NULL && current->id != id)
         {
         previous = current;
         current = current->link;
         }
         if (current == NULL)
         {
         found = false;      
         }
         else
         {
         found = true;
         delete current;
         }
}