C++ Templates - LinkedList

Question

EDIT -- Answered below, missed the angled braces. Thanks all.

I have been attempting to write a rudimentary singly linked list, which I can use in other programs. I wish it to be able to work with built-in and user defined types, meaning it must be templated.

Due to this my node must also be templated, as I do not know the information it is going to store. I have written a node class as follows -

template <class T> class Node
{
    T data; //the object information
    Node* next; //pointer to the next node element

public:
    //Methods omitted for brevity
};

My linked list class is implemented in a seperate class, and needs to instantiate a node when adding new nodes to the end of the list. I have implemented this as follows -

#include <iostream>
#include "Node.h"
using namespace std;

template <class T> class CustomLinkedList
{
    Node<T> *head, *tail;

public:

    CustomLinkedList()
    {
        head = NULL;
        tail = NULL;
    }

    ~CustomLinkedList()
    {

    }

    //Method adds info to the end of the list
    void add(T info)
    {
        if(head == NULL) //if our list is currently empty
        {
            head = new Node<T>; //Create new node of type T
            head->setData(info);
            tail = head;
        }
        else //if not empty add to the end and move the tail
        {
            Node* temp = new Node<T>;
            temp->setData(info);
            temp->setNextNull();
            tail->setNext(temp);
            tail = tail->getNext();
        }
    }

    //print method omitted
};

I have set up a driver/test class as follows -

#include "CustomLinkedList.h"
using namespace std;

int main()
{
    CustomLinkedList<int> firstList;

    firstList.add(32);
    firstList.printlist();
    //Pause the program until input is received
    int i;
    cin >> i;

    return 0;
}

I get an error upon compilation however - error C2955: 'Node' : use of class template requires template argument list - which points me to the following line of code in my add method -

Node* temp = new Node<T>;

I do not understand why this has no information about the type, since it was passed to linked list when created in my driver class. What should I be doing to pass the type information to Node?

Should I create a private node struct instead of a seperate class, and combine the methods of both classes in one file? I'm not certain this would overcome the problem, but I think it might. I would rather have seperate classes if possible though.

Thanks, Andrew.

Answer 1

While the answers have already been provided, I think I'll add my grain of salt.

When designing templates class, it is a good idea not to repeat the template arguments just about everywhere, just in case you wish to (one day) change a particular detail. In general, this is done by using typedefs.

template <class T>
class Node
{
public:
  // bunch of types
  typedef T value_type;
  typedef T& reference_type;
  typedef T const& const_reference_type;
  typedef T* pointer_type;
  typedef T const* const_pointer_type;

  // From now on, T should never appear
private:
  value_type m_value;
  Node* m_next;
};


template <class T>
class List
{
  // private, no need to expose implementation
  typedef Node<T> node_type;

  // From now on, T should never appear
  typedef node_type* node_pointer;

public:
  typedef typename node_type::value_type value_type;
  typedef typename node_type::reference_type reference_type;
  typedef typename node_type::const_reference_type const_reference_type;
  // ...

  void add(value_type info);

private:
  node_pointer m_head, m_tail;
};

It is also better to define the methods outside of the class declaration, makes it is easier to read the interface.

template <class T>
void List<T>::add(value_type info)
{
  if(head == NULL) //if our list is currently empty
  {
    head = new node_type;
    head->setData(info);
    tail = head;
  }
  else //if not empty add to the end and move the tail
  {
    Node* temp = new node_type;
    temp->setData(info);
    temp->setNextNull();
    tail->setNext(temp);
    tail = tail->getNext();
  }
}

Now, a couple of remarks:

• it would be more user friendly if List<T>::add was returning an iterator to the newly added objects, like insert methods do in the STL (and you could rename it insert too)
• in the implementation of List<T>::add you assign memory to temp then perform a bunch of operations, if any throws, you have leaked memory
• the setNextNull call should not be necessary: the constructor of Node should initialize all the data member to meaningfull values, included m_next

So here is a revised version:

template <class T>
Node<T>::Node(value_type info): m_value(info), m_next(NULL) {}

template <class T>
typename List<T>::iterator insert(value_type info)
{
  if (m_head == NULL)
  {
    m_head = new node_type(info);
    m_tail = m_head;
    return iterator(m_tail);
  }
  else
  {
    m_tail.setNext(new node_type(info));
    node_pointer temp = m_tail;
    m_tail = temp.getNext();
    return iterator(temp);
  }
}

Note how the simple fact of using a proper constructor improves our exception safety: if ever anything throw during the constructor, new is required not to allocate any memory, thus nothing is leaked and we have not performed any operation yet. Our List<T>::insert method is now resilient.

Final question:

Usual insert methods of single linked lists insert at the beginning, because it's easier:

template <class T>
typename List<T>::iterator insert(value_type info)
{
  m_head = new node_type(info, m_head); // if this throws, m_head is left unmodified
  return iterator(m_head);
}

Are you sure you want to go with an insert at the end ? or did you do it this way because of the push_back method on traditional vectors and lists ?

Answer 2

Might wanna try

Node<T>* temp = new Node<T>;

Also, to get hints on how to design the list, you can of course look at std::list, although it can be a bit daunting at times.