DaniWeb Forum Index > Software Development > C++

Linked List - Need help deleting!

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

« First

•

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!

#21

Nov 21st, 2008

Now, i am able to get my 3rd song in the list to be deleted. I'm still having problems getting the song that I want the user to delete though. What do I need to change to make it work? Please help!

Here is my 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; 
         first = current->link;    
         }
         else
         {
         found = true;
         current = current->id;
         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; 
         first = current->link;    
         }
         else
         {
         found = true;
         current = current->id;
         delete current;
         }
}

•

Join Date: Jul 2005

Posts: 1,761

Reputation: Lerner is a name known to all

Solved Threads: 283

Lerner

Offline

Posting Virtuoso

Re: Linked List - Need help deleting!

#22

Nov 21st, 2008

>>Should I use bool found?
found is not needed at all in this function. You might want to use something like it as a return value indicating to the calling function that id was found, but in the mechinics of the deletion process it is not needed.

line 23 post # 21 is irrelevant and should be removed.

if you don't want to do anything in terms of user notification if id is not found in the list then you can ignore the case where current is NULL at the end of the loop and do something like this:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if(current != NULL) //id was found
{
   if(current == first)// id is in the first node of the list
     //do something, see my previous posts for pseudocode
  else
     //do somethng else, see my previous posts for psuedocode.
}
if(current != NULL) //id was found
{
   if(current == first)// id is in the first node of the list
     //do something, see my previous posts for pseudocode
  else
     //do somethng else, see my previous posts for psuedocode.
}

It is very unlikely that you really want to assign the int in current->id as the address of an object stored in current like you try to do in line 28 post #21

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!

#23

Nov 21st, 2008

Now, I'm back to deleting the first node again. Is the contents in this function is what you were guiding me towards?

should it be current = current->link->link

 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;
 
 
         if (current != NULL && current->id == id)
         {
         if (current == first)
         { 
          first = current->link;
          delete current;           
         }
         else
         current = current->link;
         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;
    

         if (current != NULL && current->id == id)
         {
         if (current == first)
         { 
          first = current->link;
          delete current;           
         }
         else
         current = current->link;
         delete current;
         }
}

•

Join Date: Jul 2005

Posts: 1,761

Reputation: Lerner is a name known to all

Solved Threads: 283

Lerner

Offline

Posting Virtuoso

Re: Linked List - Need help deleting!

#24

Nov 21st, 2008

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
if (current == first)         
{           
    first = current->link;          
    delete current;
}
if (current == first)         
{           
    first = current->link;          
    delete current;
}

This is fine.

I've emphasized the importance of the role the previous node has in deleting a node from either the interior or the end of list in several previous posts and have to do so again. You won't get the code working correctly without it. Look at my pseudocode and my posts to figure out how to use it.

In addition

Help with Code Tags

C++ Syntax (Toggle Plain Text)

else         
  current = current->link;         
  delete current;

current = current->link; advances current one node down the list. It does nothing about removing current from the list. Then deleting current without connecting previous to next breaks the list into two and the second half is lost because you can no longer access it since the last node of the first part of the list doesn't know the first node of the last part of the list. Take a look at the following:

A->B->C->D

If you delete B without connecting A to C before deleting B then you end up with:

A and C->D

A would still be accessable as first, but there is no way to reach C and D any longer since A knows nothing about C since you didn't store Cs address in As pointer before deleting B.

In your function you could find B okay, but then the current = current->link; statement will advance current to C and your delete current; statement would then delete C, the third node in the list, not the second, giving you

A->B and D but not A->C->D like you want.

Also the delete current statement would often be inside the body of the else statement, not outside of it. Since you don't use {}s after the else statement in post #23 it is outside the body of the else. In this case that's okay since it is legal to call delete on a NULL pointer, though it isn't something I recommend.

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!

#25

Nov 21st, 2008

Hey, I updated the function. I added "previous" to the code, but am I suppose to set it to an mp3type? My function for deleteSong is updated and my full program is below. I tested out the deleteSong function, but when I delete the 3rd song, it does nothing. When delete the first song, it deletes the 2nd song and then it returns garbage numbers afterwards! Where do I go from here? and I closer to my destination? lol

Here is my updated function for deleteSong:

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

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

         if (current != NULL && current->id == id)
         {
         if (current == first)
         { 
          previous = current;
          current = current->link;
          delete current;           
         }
         else
         {
         current = current->previous;
         delete current;
         }
         }
}

Here is the full program:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
#include <string>
 
const int SONGS = 3;
 
using namespace std;
struct mp3Type
{
    int id;
    string songTitle;
    string artist;
    string length;
    string size;
    mp3Type *link,*previous;
};
 
 
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,*previous;
  int id = 0;
  bool found = false;
 
  current = first;
 
  cout<<"Enter song ID that you like to delete"<<endl;
  cout<<endl;
  cin>>id;
 
 
         if (current != NULL && current->id == id)
         {
         if (current == first)
         { 
          previous = current;
          current = current->link;
          delete current;           
         }
         else
         {
         current = current->previous;
         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 = 3;

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


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,*previous;
  int id = 0;
  bool found = false;

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

         if (current != NULL && current->id == id)
         {
         if (current == first)
         { 
          previous = current;
          current = current->link;
          delete current;           
         }
         else
         {
         current = current->previous;
         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;
        }
}