Doubly linked list in C++

Question

Please, review the code:

#include <iostream>
using namespace std;

template <class T>
struct Node
{
  Node(T data) : data(data), next(NULL), prev(NULL) {}
  T data;
  Node * next;
  Node * prev;
};

template <class T>
class DoublyLinkedList
{
public:
  DoublyLinkedList() : head(NULL), tail(NULL) {}
  DoublyLinkedList(const DoublyLinkedList<T> & dll);
  ~DoublyLinkedList();
  void addNode(T data);
  //void insertNodeBefore(int data, int before);
  //void insertNodeAfter(int data, int after);
  void deleteNode(T data);
  template <class U>
  friend std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll);
private:
  Node<T> * head;
  Node<T> * tail;
};

template <class U>
std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll)
{
  Node<U> * tmp = dll.head;
  while (tmp)
    {
      os << tmp->data << " ";
      tmp = tmp->next;
    }

  return os;
}

template <class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
  Node<T> * tmp = NULL;
  while (head)
    { 
      tmp = head;
      head = head->next;
      delete tmp;
    }
  head = tail = NULL;
}

template <class T>
void DoublyLinkedList<T>::addNode(T data)
{
  Node<T> * t = new Node<T>(data);

  Node<T> * tmp = head;
  if (tmp == NULL)
    {
      head = tail = t;
    }
  else
    {
      while (tmp->next != NULL)
        {
          tmp = tmp->next;
        }

      tmp->next = t;
      t->prev = tail;

      tail = t;
    }
}

template <class T>
void DoublyLinkedList<T>::deleteNode(T data)
{
  Node<T> * tmp = head;
  while (tmp && tmp->data != data)
    {
      tmp = tmp->next;
    }

  if (tmp)
    {
      if (tmp->prev && tmp->next) // no change to head or tail
        {
          tmp->prev->next = tmp->next;
          tmp->next->prev = tmp->prev;
        }
      else if (tmp->prev) // change to tail
        {
          tmp->prev->next = tmp->next;
          tail = tmp->prev;
        }
      else if (tmp->next) // change to head
        {
          tmp->next->prev = tmp->prev;
          head = tmp->next;
        }

      delete tmp;
    }
}

template <class T>
DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T> & dll)
{
  Node<T> * tmp = dll.head;
  while (tmp)
    {
      this->addNode(tmp->data);
      tmp = tmp->next;
    }
}

int main()
{
  DoublyLinkedList<int> dll;

  dll.addNode(1);
  dll.addNode(2);
  dll.addNode(3);
  dll.addNode(4);
  dll.addNode(5);

  cout << dll << endl;
  DoublyLinkedList<int> dll2(dll);
  cout << dll2 << endl;

  dll.deleteNode(3);
  dll.deleteNode(1);
  dll.deleteNode(5);

  cout << dll << endl;
  cout << dll2 << endl;

  return 0;
}

Answer 1

1. Consider replacing Node<T> with:

   typedef Node<T> node_t;
   
   ...
   
   node_t node;
   

2. Consider making your implementation STL-enabled. If I were user of this class, the first thing I'd ask you is "how do I iterate over this list?". Doubly-linked lists are great when adding items in the middle, how do I do it? (it's about operations like insertBefore(), insertAfter()). How do I sort it? How do I check if item is on the list? How do I search using predicate?

3. Why do you call the method deleteNode if it's only argument is of type T? It's more to findNodeByValueAndDeleteIt(T).

4. What about assignment operator? You should either declare it private (if you don't support it), or implement it explicitly depending on semantics you want to support (deep copy (most likely what you want), reference, COW, etc):

   YourList<int> a; // do something with a
   
   YourList<int> b; // do something with b
   
   a = b; // what is "a" here? what if I add nodes to a? will it affect b?
   
   // imagine, scope ends here, dtor for b is called, everything's fine
   
   // dtor for a is called - here you're going to crash, since
   
   // both a and b were using the same memory and this memory is already
   
   // free, since b's dtor has already been called at this point
   

5. For methods like void addNode(T data) - why do you pass data by value? Since you store item values by value, in either case you're going to call their copy-ctor. Copy-ctor requires const-reference, so you should consider replacing addNode with void addNode(T const& data).

6. using namespace std; - is it only for cout instead of std::cout in your main()?

Checked nothing from the "algorithmic" standpoint, C++ only.

Answer 2

Consider implementing AddNode and RemoveNode to the node themselves so you can unclutter the interface of the linked list, and make it easier for the list to purge the nodes. You should also declare a destructor, as your class presently leaks memory after you are finished (it does not delete all the nodes stored in the list).

Answer 3

• addNode(T data)

  • This should be called addNodeToTail or pushBack since it specifically adds a node to the tail of the list
  • Why are you iterating through the whole list when you already have a pointer to tail? After the while loop, tmp == tail.
  • Never do this: head = tail = t;. Everytime a programmer sees this, they have to stop and think if this is undefined behavior. Make this two separate statements.

• ~DoublyLinkedList

  • Never do multiple assignments this way: head = tail = NULL;. See similar note above.
  • Since the DoublyLinkedList is destructed, there's not point in setting head and tail to NULL since these variables are immediately destructed afterwards.

Answer 4

It's just an additional advice.

typedef Node<T> node_t;

It can't be done. Type definition can't be with template class.

But I heard that we can do over C++11. (not exactly same above code)