I have an assignment that creates nodes and a inserts them into a doubly linked list. One of the specifications is to include a destructor. For some reason my destructor seems to be deleting either the objects or pointers or both when I call addSortedList() in main. If I take out the destructor the program runs just fine, with it there the program crashes when addSortedList() is called. I even spent some time with my instructor today and he said my destructor looked fine and couldn't figure out what was causing the problem. Could anybody explain to me why this is happening?
#include <iostream>
using namespace std;
template <typename T>
class DoublyLinkedList;
template <typename T>
class Node
{
friend class DoublyLinkedList<T>;
public:
Node();
Node(const T& data, Node<T> *next, Node<T> *prev);
private:
T data;
Node<T> *next;
Node<T> *prev;
}; // end class Node
//*******************************************************************
// Create a header node for an empty linked list.
template <typename T>
Node<T>::Node()
{
next = this;
prev = this;
}
//*******************************************************************
// Create a regular node to be inserted into a linked list
template <typename T>
Node<T>::Node(const T& data, Node<T> *next, Node<T> *prev)
{
this->data = data;
this->next = next;
this->prev = prev;
}
//*******************************************************************
template <typename T>
class DoublyLinkedList
{
public:
DoublyLinkedList();
DoublyLinkedList(const T arr[], int arrSize);
~DoublyLinkedList();
void insert(Node<T> *insertionPoint, const T& data);
void display();
DoublyLinkedList<T> addSortedList(const DoublyLinkedList<T>& list2);
private:
Node<T> *header; // pointer to header node (header points to
// front and back of list)
int size; // number of data nodes in list
}; // end class DoublyLinkedList
//*******************************************************************
// Default constructor creates only a header node
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList()
{
header = new Node<T>();
size = 0;
} // end constructor
//*******************************************************************
// Constructor takes in array and array size and creates a doubly
// linked list with a header node.
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList(const T arr[], int arrSize)
{
header = new Node<T>();
size = arrSize;
for (int i = size - 1; i > -1; i--)
{
insert(header->next, arr[i]);
}
} // end constructor
//*******************************************************************
// Destructor to delete nodes after use.
template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
Node<T> *oldFrontPointer; // pointer to node to be deleted
Node<T> *newFrontPointer; // pointer to next node to be deleted
oldFrontPointer = header->next;
while (oldFrontPointer->next != header)
{
newFrontPointer = oldFrontPointer->next;
delete oldFrontPointer;
oldFrontPointer = newFrontPointer;
}
delete header;
} // end destructor
//*******************************************************************
// This function inserts a new node into a list
template <typename T>
void DoublyLinkedList<T>::insert(Node<T> *insertionPoint, const T& data)
{
Node<T> *prevNodePtr; // pointer to node that precedes insertionpoint
Node<T> *newNodePtr; // pointer to new node
prevNodePtr = insertionPoint->prev;
newNodePtr = new Node<T>(data, insertionPoint, prevNodePtr);
size++;
insertionPoint->prev = prevNodePtr->next = newNodePtr;
} // end insert
//*******************************************************************
// This function prints the node data from a list
template <typename T>
void DoublyLinkedList<T>::display()
{
Node<T> *currentNodePtr = header->next;
if (size == 0)
{
cout << "Empty linked list.";
}
else
{
while (currentNodePtr != header)
{
cout << currentNodePtr->data << " ";
currentNodePtr = currentNodePtr->next;
}
}
cout << "\n";
} // end display
//*******************************************************************
// This function merges the parameter list into the calling object
// list in sorted order assuming both lists are presorted.
template <typename T>
DoublyLinkedList<T> DoublyLinkedList<T>::
addSortedList(const DoublyLinkedList<T>& list2)
{
Node<T> *list1Pointer = this->header->next;
Node<T> *list2Pointer = list2.header->next;
while (list1Pointer != this->header && list2Pointer->next != list2.header)
{
// insert list 2 nodes if they are smaller than list 1 current node
if (list1Pointer->data > list2Pointer->data)
{
insert(list1Pointer, list2Pointer->data);
list2Pointer = list2Pointer->next;
}
// move list 1 pointer if list 1 current node is smaller than
// list 2 current node
else if (list1Pointer->data < list2Pointer->data)
{
list1Pointer = list1Pointer->next;
}
// insert list 2 nodes that are smaller than list 1 current node
else if (list1Pointer->next == this->header)
{
insert(list1Pointer, list2Pointer->data);
list2Pointer = list2Pointer->next;
}
}// end while
// insert last list 2 nodes that are larger than last node in
// list 1 at the end of the list
while (list1Pointer->next == this->header && list2Pointer != list2.header)
{
list1Pointer = list1Pointer->next;
insert(list1Pointer, list2Pointer->data);
list2Pointer = list2Pointer->next;
}
return *this;
} // end addSortedList
int main()
{
int arrA[] = {20,80,100};
int arrB[] = {10,30,60,100,110};
int arrASize = sizeof(arrA)/sizeof(int);
int arrBSize = sizeof(arrB)/sizeof(int);
DoublyLinkedList<int> listA(arrA, arrASize);
DoublyLinkedList<int> listB(arrB, arrBSize);
DoublyLinkedList<int> listC;
listC.display();
listA.display();
listB.display(); //extra
listA.addSortedList(listB);
listA.display();
listB.display();
} // end main
