C++ Destructor deleting stuff(objects, pointers?) too soon

Question

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

Answer 1

You're returning a value from addSortedList, whereupon your intention is obviously to return a reference to this. The returned, copied value then shares the internal list pointer with the original object and promptly deletes it with it's own destructor.

Replace this:

template <typename T>
DoublyLinkedList<T> DoublyLinkedList<T>::
   addSortedList(const DoublyLinkedList<T>& list2)

with this:

template <typename T>
DoublyLinkedList<T> &DoublyLinkedList<T>::
   addSortedList(const DoublyLinkedList<T>& list2)