0x1000001 0x1000001 - 4 months ago 17
C++ Question

Remove function malfunctioning in doubly linked list

My function to remove nodes from a doubly linked list is adding (overwriting?) values to the list, which appear when the list is printed.

Code for the main, remove and print functions is listed below. The expected output and correlations between the current code and its output are shown below too.

Code for main



In main, the add function is called, and the integer in the parameter is added as a node in the linked list. The add function works, as does the print function.

int main()
{
LinkedList aList;

aList.add(3);
aList.add(10);
aList.add(1);
aList.add(7);
aList.add(9);
aList.add(12);
aList.printAscending();
aList.printDescending();
aList.remove(3);
aList.remove(1); //The integer to be removed with this line ends up in the output
aList.remove(7);
aList.remove(12);
cout << "remove operations should be complete" <<endl;
aList.printAscending();
aList.printDescending();

return 0;
}


Code for remove function



bool LinkedList::remove(int val) //parameter contains value to be removed
{
bool removed = false;
Node* newNode = new Node;
newNode->data = val;
newNode->next = NULL;
newNode->prev = NULL;

Node* curr = head;
while(curr)
{
if(curr->data == val)
{
if(curr == head)
{
head = head->next;
curr->next = NULL;
delete curr;
}

else if(curr != head && curr != tail)
{
Node * previous = curr->prev;
Node * following = curr->next;
previous->next = following;
following->prev = previous;
curr->next = NULL;
curr->prev = NULL;
delete curr;
}

else if(curr == tail)
{
tail = tail->prev;
curr->prev = NULL;
delete curr;
}
removed = true;
}
curr = curr->next;
}
return removed;
}


Code for print functions



//Prints from head to tail of list
void LinkedList::printAscending() const
{
Node* curr = head;
cout<<"\nascending: ";
while(curr)
{
cout << curr->data << " ";
curr = curr->next;
}
cout <<'\n';
}

//Prints from tail to head of list
void LinkedList::printDescending() const
{
Node* curr = tail;
cout << "\ndescending: ";
while(curr)
{
cout << curr->data << " ";
curr = curr->prev;
}

cout << endl;
}


Expected output



ascending: 3 10 1 7 9 12
descending: 12 9 7 1 10 3
remove operations should be complete
ascending: 10 9
descending: 9 10


Actual Output



ascending: 3 10 1 7 9 12 //correct
descending: 12 9 7 1 10 3 //correct
remove operations should be complete //correct
ascending: 10 9 0 //last number, 0, is incorrect
descending: 9 10 1 //last number, 1, is incorrect


If the call in
int main
to remove the integer 1
aList.remove(1)
is replaced with
aList.remove(999)
, the integer 999 appears in the actual output on the descending print instead of 1. However, the integer 0 is appended to the ascending print at all times.

Answer

After you delete curr, you then dereference it:

curr = curr->next;

This is undefined behavior.