Have something to say? Contribute New Article Reply to this Article
Linked List - Need help deleting!
Hello, I'm having a simple problem.
For my program, each song has an id number which stores the songs information. For my deleteSong function, I am asking the user what id of the song does he/she wants to be deleted. After the user enters the id of the song he/she wants to delete, I then print out the list of songs. After I print the list of songs, the problem is the song that is chosen to be deleted remains on the list, while all other songs that were on the list is now deleted. Basically, I just want the song that user chooses to delete, but instead of it being deleted, the others are deleted. How do I solve this problem in my code?
#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;
};
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;
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;
bool found;
int id;
current = first;
cout<<"Enter song ID that you like to delete"<<endl;
cout<<endl;
cin>>id;
for (int i = 0; i < SONGS; i++)
{
if (first->link != NULL)
{
current = first->link;
first->link = first->link->link;
delete current;
}
else
{
found = false;
trailcurrent = first;
}
current = first->link;
}
}
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;
}
}your coded logic reads something like this:
get information from user, but ignore it for as many songs as there are in the list if list is longer than two delete the second song in the list else assign a value to a flag but never evaluate the flags valueThat doesn't correlate very well with your intentions.
should it be
for (int i = id; i < songs; i++)
first->link = current->link->link;
void deleteSong(mp3Type*& first)
{
mp3Type *last,*current,*trailcurrent;
bool found;
int id;
current = first;
cout<<"Enter song ID that you like to delete"<<endl;
cout<<endl;
cin>>id;
for (int i = 0; i < SONGS; i++)
{
if (first->link != NULL)
{
current = first->link;
first->link = first->link->link;
delete current;
}
else
{
found = false;
trailcurrent = first;
}
current = first->link;
}
}I think it has something to do with my pointer, but how do i point it to the right direction?
your coded logic reads something like this:
get information from user, but ignore it for as many songs as there are in the list if list is longer than two delete the second song in the list else assign a value to a flag but never evaluate the flags valueThat doesn't correlate very well with your intentions.
Let me put in right way..
you are creating the renewing list each time you add new nodes (new songs).
in every insertion ... your list pointer is set in to NULL. causing the earlier information to run in vein.
....other part later...
It's more than that.
In order to delete the node you have to find it first. Then, since this is a singly linked list, you need to find the node before the node you want to delete (unless of course you want to delete the first node in the list). Then you point the node prior to the one you want to delete to the one after the one you want to delete. That will remove the desired node from the list, but not delete the memory used to store the node so use the keyword delete to actually delete the desired node
It's more than that.
In order to delete the node you have to find it first. Then, since this is a singly linked list, you need to find the node before the node you want to delete (unless of course you want to delete the first node in the list). Then you point the node prior to the one you want to delete to the one after the one you want to delete. That will remove the desired node from the list, but not delete the memory used to store the node so use the keyword delete to actually delete the desired node
Do I need an identifier called previousnode?
There come 3 condition while deleting..
1. node is at the front
2. node is at last
3. node is in between
You need to have the previous node of the list in order to join again...
You can always refer to any reference book for the while.
Or something like that yes.
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 partOr something like that yes.
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:
#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;
}
}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..
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;
}
}here's a simple sample code...
i don't test it yet :)...
let me know the result...
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);
//--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.
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.
here's a simple sample code... i don't test it yet :)... let me know the result...
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.
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.
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 nodeThis 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
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.
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:
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;
}
}This question has already been solved
You
© 2012 DaniWeb® LLC
