Bug in destructor of doubly linked list (C++)

toobladink · April 17, 2019

I was going over an assignment with my professor to get some points back, and we were both having issues with the destructor. We wanted to call "Delete(1)" instead of "Delete(i)" because it deletes the item at the front of the list and doesn't require the list to be traversed to the very end before deleting something.

Everything else works as it should, but we want to find a way to have the destructor (List4::~List4()) to have O(1) rather than O(N) operations

If we use Delete(1), we can delete like 4 thiings (of a 7 item list) and then we get a segmentation fault)

// File that includes all member functions for class List4
// Where List4 is a linked list that has a head and tail as a "dummy node"
// And each node has a pointer to the next node and the previous node

#include <iostream>
#include "proj9.h"

using namespace std;

List4::List4()
{
	head = new doubleNode;
	tail = new doubleNode;
	length = 0;
	head->prev = NULL;
	tail->next = NULL;
	head->next = tail;
	tail->prev = head;
}

List4::~List4()
{
	int size = length;
	for (int i = size; i > 0; i--)
	{
		cout << "Deleting item" << endl;
		Delete(i); // We want to have Delete(1) but we get segmentation faults. Any idea why?
	}
	delete head;
	delete tail;
}

doubleNode* List4::FindPosition(int pos)
{
	doubleNode* addrPos = head;
	int i = 0;
	while (i < pos)
	{
		addrPos = addrPos->next;
		i++;
	}
	return addrPos;
}

void List4::Insert(itemType newItem, int pos)
{
	doubleNode* insPtA = FindPosition(pos-1);
	doubleNode* insPtB = insPtA->next;
	doubleNode* cur = new doubleNode;
	cur->prev = insPtA;
	cur->next = insPtB;
	cur->item = newItem;
	insPtB->prev = cur;
	insPtA->next = cur;
	cur = NULL;
	length++;
}

void List4::Delete(int pos)
{
	doubleNode* ptrA = FindPosition(pos)->prev;
	doubleNode* ptrB = ptrA->next->next;
	ptrB->prev = ptrA;
	ptrA->next = ptrB;
	length--;
	delete ptrA->next;
}

doubleNode* List4::Find(itemType target)
{
	doubleNode* cur = new doubleNode;
	cur = head->next;
	int i = 0;
	while (i < length)
	{
		if (cur->item == target)
		{
			return cur->next;
		}
		cur = cur->next;
		i++;
	}
	if (i == length) // if this statement is reached, item was not found
		return NULL;
}

int List4::DeleteItem(itemType delItem)
{
	doubleNode* cur = new doubleNode;
	cur = head->next;
	int counter = 0;
	for (int i = 0; i < length; i++)
	{
		if (cur->item == delItem)
		{
			counter++;
			Delete(i);
		}
		cur = cur->next;
	}
	delete cur;
	return counter;
}

void List4::PrintForward()
{
	doubleNode* cur = new doubleNode;
	int i = 0;
	cur = head->next;
	while (i < length)
	{
		cout << cur->item << endl;
		cur = cur->next;
		i++;
	}
}

void List4::PrintBackwards()
{
	doubleNode* cur = new doubleNode;
	int i = 0;
	cur = tail->prev;
	while (i < length)
	{
		cout << cur->item << endl;
		cur = cur->prev;
		i++;
	}
}


// If you're interested in the header file, here it is:

#ifndef LIST4_H
#define LIST4_H

typedef int itemType;

struct doubleNode
{
 doubleNode* prev;
 itemType item;
 doubleNode* next;
};

class List4
{
 public:
   List4();
   ~List4();
  
   /*
   pre: List exists, pos is in the range [1..length+1].
   post: new node is inserted at postion pos. 
   */
   void Insert(itemType item, int pos);   

   /*
   pre: List exists, pos is in the range [1..length].
   post: node postion pos is deleted. 
   */
   void Delete(int pos);   

   /*
   pre: List exists
   post: returns the addres of the item is item is in the list
         returns NULL if the item is not in the list 
   */
   doubleNode* Find(itemType item);  

   /*
   pre: List exists
   post: deletes every instance of item in the list 
         returns the number of deletions
   */
   int DeleteItem(itemType item);   

   /*
   pre: List exists.
   post: The item value of each node, from head to tail,
         is displayed on the screen, excluding the dummy nodes. 
   */
   void PrintForward();
   
   /*
   pre: List exists.
   post: The item value of each node, from tail to head,
         is displayed on the screen, excluding dummy nodes.
   */
   void PrintBackwards();


   //#Bonus +10
   /*
   pre: List exists.
   post: Nodes in the list are sorted in ascending order using
         selection sort
   */
   void Sort();

 private:
   /*
   pre: List exists, pos is in the range [1..length+1].
   Post: Returns the address of the node in position pos
         This one is tricky because of the dummy nodes.
	 If pos = 1, return the address of the head dummy node
	 if poss length+1, return the address of the node before
	 the tail dummy node
   */
   doubleNode* FindPosition(int pos);
   int length;         //length of the list
   doubleNode* head;   //points to the first dummy node 
   doubleNode* tail;   //points to the last dummy node  
};
#endif

reniat · April 17, 2019

The memory issue is likely here from the look of it:

void List4::Delete(int pos)
{
    doubleNode* ptrA = FindPosition(pos)->prev;
    doubleNode* ptrB = ptrA->next->next;
    ptrB->prev = ptrA;
    ptrA->next = ptrB; // After this point, ptrA->next points to what used to be ptrA->next->next
    length--;
    delete ptrA->next; // So when this delete executes on ptrA->next, it deletes the pointer behind the target
  
    // also after ptrA->next is re-assigned there is no longer a reference to the original ptrA->next so thats a memory leak
}

Also, be careful using 1 indexing for your container. For example, as written, it looks like you're going to dereference a null pointer if you tried to delete an item at pos = 0, and most programmers will think of pos 0 as the start, not pos 1.

Also also, try to get in the habit of using nullptr instead of NULL when possible. It's a best practice in modern C++ for type safety. As an example, lets say you have a function foo with 2 overloads, an int and a pointer type:

void foo(int i);

void foo(char* c);

foo(NULL) and foo(nullptr) would call different overloads since NULL is just a macro for an int, even though both are "null pointer" representations.

EDIT: also, i'm confused at the attempt to get O(1) time during destruction, as you are still having to delete n elements. I don't think that's possible since you can't "batch delete" in C++ AFAIK. You're essentially trying to traverse an array of n elements in O(1) time...

toobladink · April 18, 2019

@reniat Thank you!

But I guess my question is now, is there a way to actually delete that node with the way I have things configured? By that I mean, won't there still be memory used by the program, since we just redirected the pointers so nothing is pointing to that?

reniat · April 18, 2019

46 minutes ago, toobladink said:

By that I mean, won't there still be memory used by the program, since we just redirected the pointers so nothing is pointing to that?

correct, that's a memory leak and you want to avoid that. I'm not saying you shouldnt use delete (you definitely should if you aren't using smart pointers), i'm saying you should delete your target node, not the node next to it

something like:

void List4::Delete(int pos)
{
    doubleNode* ptrA = FindPosition(pos)->prev;
    doubleNode* ptrB = ptrA->next->next;
    delete ptrA->next;
    ptrB->prev = ptrA;
    ptrA->next = ptrB;
    length--;
}

the only difference being here prtrA->next is being deleted while its pointing to your target node, not after its pointing to the node in positon pos after removal from the list .