Templated doubly-linked-list

Question

I've been wanting to revise what I knew on templated classes so thought I'd write a doubly linked list to practice.

It works fine, so all is well and good on that front, but is there something I've missed?

Current things I am aware of:

• naming - could be a little more explicit
• functionality - i.e. handling node* pointers so I could (for example) search for and delete a node containing a certain value, without scanning through the list twice.

I do plan to fix / add this later.

Specifically, I'm looking mainly for feedback on how I've done the templating, and any RAII issues, though I will happily take any further feedback.

Note that I've used .h as the interface header and .hpp for the implementation to separate the interface and implementation (using .hpp instead of .imp or similar as it is recognised type on my system). I understand that for the template to work for all types it needs to be in the header, otherwise each type to be used needs to be defined, correct?

I've been compiling with:

g++ -std=c++11 use_dllist.cpp -Wall -Wextra -pedantic -o dll.exe

dlllist.h:

#ifndef __d_l_list__
#define __d_l_list__
#include <string>
template<class T>class d_l_listnode
{
public:
   d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
   T data;
};

template<class T> class d_l_list
{
    d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail
    int node_count = 0;

    void deep_copy(d_l_list<T>& original,d_l_list<T>& destination);

public:
    d_l_list();
    d_l_list(d_l_list<T>&);
    d_l_list<T>& operator=(d_l_list<T>&);
    ~d_l_list();
    int  add_node(T data, int index);
    int  find_node(T data);
    bool del_node(int index);
    bool is_empty();
    int  get_node_count();
    void print_list(std::string delimiter);
    void print_list_debug();
};

#include "dllist.hpp"
#endif

dllist.hpp:

#include <iostream>

template<class T>
d_l_list<T>::d_l_list()
{
    node_count = 0;
    end[0] = NULL;
    end[1] = NULL;
}

template<class T>
void d_l_list<T>::deep_copy(d_l_list<T>& original, d_l_list<T>& destination)
{
  destination.node_count = 0;
  destination.end[0] = NULL;
  destination.end[1] = NULL;
  d_l_listnode<T>*current_node = original.end[1];
  while(current_node)
  {
    destination.add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template<class T>
d_l_list<T>::d_l_list(d_l_list<T>& original)
{
  deep_copy(original, *this);
}

template<class T>
d_l_list<T>& d_l_list<T>::operator=(d_l_list<T>& original)
{
  deep_copy(original, *this);
  return *this;
}

template<class T>
d_l_list<T>::~d_l_list()
{    while(node_count){del_node(0);}}

template<class T>
void d_l_list<T>::print_list(std::string delimiter)
{
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout << node->data << (node->link[1]?delimiter:"");
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
void d_l_list<T>::print_list_debug()
{
  std::cout<<"head: "<<end[0]<<":"<<(node_count?end[0]->link[0]:0)<<"\ntail: "<<end[1]<<":"<<(node_count?end[1]->link[1]:0)<<std::endl; //second should always print '0'. If not, problem.
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout<<node->data<<"\t\t:"<<node<<"\t"<<node->link[0]<<"\t:"<<node->link[1]<<"\n";
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
int d_l_list<T>::get_node_count()
{
  return node_count;
}

template<class T>
int d_l_list<T>::find_node(T data)
{
  int index = 0;
  d_l_listnode<T>* current_node = end[0];
  while (current_node)
  {
    if (current_node->data == data)
      return index;
    current_node = current_node->link[1];
    index++;
  }
  return -1;
}

template<class T>
int d_l_list<T>::add_node(T data, int index)
{
  bool traversal_direction = true;

  if (index > node_count/2){
    index = node_count - index;
    traversal_direction = false;}

  if (index < 0)
    {index = 0;}

  d_l_listnode<T>* new_node = new d_l_listnode<T>;
  if (!new_node)
    {return -1;}

  new_node->data=data;

  if (!end[0])
  {
    end[0] = new_node;
    end[1] = new_node;
    node_count = 1;
    return 0;
  }

  d_l_listnode<T>* current_node = end[!traversal_direction];

  for (int i = 0; i < index && i < node_count; i++)
    {current_node = current_node->link[traversal_direction];}

  if (!(current_node->link[0]&&current_node->link[1]))
  {
    end[!traversal_direction] = new_node;
    new_node->link[!traversal_direction] = NULL;
  }
  else
  {
    new_node->link[!traversal_direction] = current_node->link[!traversal_direction];
    new_node->link[!traversal_direction]->link[traversal_direction] = new_node;
  }
  new_node->link[traversal_direction] = current_node;
  current_node->link[!traversal_direction] = new_node;

  node_count++;
  return traversal_direction?index:node_count-index-1;
}

template<class T>
bool d_l_list<T>::del_node(int index)
{
  if (!node_count) 
    {return false;}

  bool traversal_direction = true;

    if (index >= node_count/2)
    {
      index = node_count - index - 1;
      traversal_direction = false;
    }

    d_l_listnode<T>* current_node = end[!traversal_direction];

    if (index < 0)
      {index = 0;}

    for (int i = 0; i < index; i++)
      {current_node = current_node->link[traversal_direction];}

    for (int i = 0; i <= 1; i++)
    {
      if (!current_node->link[!i])
        {end[!i] = current_node->link[i];}
      else
        {current_node->link[!i]->link[i] = current_node->link[i];}
    }
  //}
  delete current_node;
  node_count--;
  return true;
}

use_dllist.cpp (just something to exercise the functionality):

#include "dllist.h"
#include <iostream>
#include <climits>


void printout(d_l_list<int>& list)
{
    std::cout << "\nnumber of nodes: " << list.get_node_count() << std::endl;
    std::cout << "list contents:" << std::endl;
    list.print_list(", ");
}

int main()
{
    d_l_list<int> list;

    std::cout<<"created list" << std::endl;

    //printout(list);

    for (int i = 0; i<10; i++)
    {
        int j = list.add_node(i, 5);
        std::cout<<"added a node, value: "<<i<<", index: "<< j << std::endl;
    }

    printout(list);

    {
      std::cout<<"\nCopy Constructor:"<<std::endl;
      d_l_list<int> list2(list);
      printout(list2);
    }
    {
      std::cout<<"\nAssignment:"<<std::endl;
      d_l_list<int> list3 = list;
      printout(list3);
    }

    std::cout<<"\nfinding '8'" << std::endl;
    int index = list.find_node(8);
    std::cout<<"deleting '8' (index: "<<index<<")"<< std::endl;

    list.del_node(index);

    printout(list);

    std::cout<<"\ndeleting #1" << std::endl;
    list.del_node(1);

    printout(list);

    std::cout<<"\ndeleting #5" << std::endl;
    list.del_node(5);

    printout(list);

    std::cout<<"\ndeleting #INT_MAX ("<<INT_MAX<<")" << std::endl;
    list.del_node(INT_MAX);

    printout(list);

    while(list.get_node_count())
    {
      std::cout<<"\ndeleting #0" << std::endl;
      list.del_node(0);
      printout(list);
    }
}

Answer 1

File extensions

Separating the interface from the implementation is great. However, the .h/.hpp split is not obvious. The most frequent file extensions used for implementation files that cannot go into .cpp files are .inl (for inline) and .tpp (for template cpp). I know that at least some code editors or IDEs recognize the extension .inl (at least Code::Blocks), but many of them can be configured to recognize additional extensions anyway. Try to use something more obvious that .hpp for the implementation file.

Names

A few remarks related to names in general:

• Try to write your preprocessor names in FULL_CAPS_CASE so that they can be identified with a single glance and not confused with regular function, class or variable names.

• Also, your header guard names are incorrect: names with double underscores (anywhere in the name) are reserved for the implementers. Names beginning with an underscore followed by an uppercase letter are also reserved for the implementers. A good well-formed name for you header guard would be D_L_LIST_ since single trailing underscores are fine.

• When possible, try to use the injected class name in a cass template. It allows to write shorter code and reduces the maintenance costs: if you change the template parameter name, you won't have to edit the lines where you used the injected class name. For example, your operator= would become:

  d_l_list& operator=(d_l_list&);
  

• print_list is a bad name for a method since you already know that you are printing a list. A better name could be print but we will see later a more idiomatic way to print things.

const-correctness

You should really take into account the const-correctness, which means that you should add const to specify that an object won't be modified:

• operator= should take a const d_l_list& instead of a d_l_list& to assert that it will not modify the assigned variable.

• All the methods that do not modify the class should be marked const:

  bool is_empty() const;
  

  And there are many such methods: print_list, print_list_debug, get_node_count, is_empty and find_node.

Printing stuff

The idiomatic way to print stuff in C++ is to overload operator<< for an std::ostream& and your type. In your case, it should be:

template<typename T>
std::ostream& operator<<(std::ostream& stream, const d_l_list<T>& list)
{
    // print stuff to stream...
    return stream;
}

Note that the overloaded operator is a free function, not a class method.

Null pointer constant

Currently, you are using two different ways to represent the null pointer constant:

• NULL, as in end[0] = NULL;.
• 0 as in d_l_listnode* link[2] = {0,0};.

You are using C++11. The C++11 way to represent a null pointer constant is nullptr. The two lines above could be rewritten as:

• end[0] = nullptr;
• d_l_listnode* link[2] = {nullptr,nullptr};.

In-class initializers and default construction

You used in-class initializers to default-initialize the members of d_l_list. However, you initialized them with the exact same values in the default constructor. Actually, if you use the explicitly defaulted default constructor, it will use the in-class initializers to initialize the members. Therefore, you can simply define it as such:

template<class T>
d_l_list<T>::d_l_list()
    = default;

Use the copy-and-swap idiom

The copy-and-swap idiom is an idiom that lets you write correct and short code. In short, the copy should be written in the copy constructor of the class while the operator= should rely on the copy constructor to perform the copy. Here is what it would look like for your class:

template<class T>
d_l_list<T>::d_l_list(const d_l_list<T>& other)
{
  // Uninitialized members use the
  // in-class initializers here, that's
  // why I left out the initialization part

  d_l_listnode<T>* current_node = other.end[1];
  while(current_node)
  {
    this->add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template<class T>
d_l_list<T>& d_l_list<T>::operator=(d_l_list<T> other)
{
  swap(*this, other);
  return *this;
}

In short, operator= performs a copy of other thanks to the copy constructor and then swaps the contents of *this and other. Then, other is destructed and its contents (the original contents of *this) are cleaned. The post I linked goes further into the details and is really worth reading. Anyway, using the copy-and-swap idiom is safe, efficient enough, and allows you to remove the deep_copy method.

Answer 2

A few notes:

You have this code:

d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
[...]
d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail

and client code:

destination.end[0] = NULL;

In client code (i.e. where you need to know this) you have no ovbvious way to know that 0 means tailwise, without looking at the class declaration.

You could define an enumeration so you'd have:

destination.end[left_link] = NULL;
destination.end[right_link] = NULL;

This would ensure consistence in client code and improved semantical information.

Consider implementing iteration access, compatible with the STL. This would enable you to use the class in a lot of idiomatic ways (like performing an iteration operation for stream input and output and std algorithms: e.g. find and sort).

Consider using full names for classes (d_l_list makes me think of a "download list" for some reason). Also consider calling the class bidi_list instead (or something similar): the fact it provides fast access for iteration and insertion is important in client code; the fact it is implemented as a linked list is just an implementation detail.