8
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ never open a namespace declaration in a header file btw. So for instance, don't put in 'using namespace std;' \$\endgroup\$ – C Johnson Sep 26 '11 at 9:04
  • \$\begingroup\$ C Johnson, why not in .h, but could be in .cpp? \$\endgroup\$ – Medicine Sep 27 '11 at 18:35
  • \$\begingroup\$ ok got it, it can cause trouble to other header files included which are not in the same namespace. \$\endgroup\$ – Medicine Sep 27 '11 at 20:09
10
\$\begingroup\$
  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.

\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$
  • 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.
\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.