Linked list implemented as classes, not imperative code

Question

As an update to previous code I've submitted:

Improvements this time are mainly having everything moved to a class, before I plough on and add more functionality (I've come back to C++ after a few years away and this is a revision exercise).

#include <iostream>
#include "LinkedList.h"

class LinkedList
{
public:
    LinkedList(void);
    ~LinkedList(void);
    void traverseList();
    int length();
    void push(int data);

private:
    struct node{
    int data;
    node *pointee;
    };

    node *head;
    node *last;
    int count;
};

LinkedList::LinkedList(void)
{
        head = new node();
    last = new node();
    head->data = 0;
    head->pointee = last;
    last->data = 0;
    last->data = NULL;
    count = 2;
}

LinkedList::~LinkedList(void)
{
}

/*
    To be replaced with an iterator and an overloaded print operator for output
*/
void LinkedList::traverseList(){
    for(node *iterator = LinkedList::head ; iterator ; iterator = iterator->pointee)
    {
        std::cout << iterator->data << std::endl;
    }
}

int LinkedList::length(){
    return LinkedList::count;
}

void LinkedList::push(int data){

    node *newNode = new node();
    newNode->data = data;
    newNode->pointee = NULL;
    last = newNode;
    ++count;
}

int main(){

    LinkedList list;

    for(int i=1 ; i<4 ; i++)
    {
        list.push(i);
    }

    int length = list.length();
    std::cout << length << std::endl;
    list.traverseList();
    return 0;
}

Answer 1

Since we have no clean implementations:

The thing to notice is that the push_back() and erase() become trivial if you use a sentinal. This is because you do not need to test for NULL in any part of the code.

    Node(Node* after)
    {
        prev          = after;
        next          = after->next;
        prev->next    = this;
        next->prev    = this;
    }
    ~Node()
    {
        prev->next  = next;
        next->prev  = prev;
    }

    iterator push_back(T const& value)
    {
        tail    = new ValueNode(value, tail);

        // If new succeeded then increment count
        ++count;
        return iterator(tail);
    }

    void erase(iterator const& i)
    {
        // Get the value we will set as tail if the delete works
        Node*   newTail = (tail == i.node)
                            ? i.node->prev
                            : tail;
        delete i.node;
        // Delete worked now we can update the state.
        tail    = newTail;
        --count;
    }

Here is the whole code

#ifndef THORS_ANVIL_UTILITY_LINKED_LIST
#define THORS_ANVIL_UTILITY_LINKED_LIST

#include <algorithm>
#include <functional>

template<typename T>
class LinkedList
{
    struct Node
    {
        Node*   prev;
        Node*   next;
        Node(Node* after)
        {
            prev          = after;
            next          = after->next;
            prev->next    = this;
            next->prev    = this;
        }
        ~Node()
        {
            prev->next  = next;
            next->prev  = prev;
        }
        void swap(Node& rhs) throw()  { std::swap(prev, rhs.prev); std::swap(next, rhs.next);}
    };
    struct ValueNode: Node
    {
        ValueNode(T const& value, Node* after)
            : Node(after)
            , data(value)
        {}
        T       data;
    };

    Node    head;
    Node*   tail;
    int     count;

    public:
        struct Iterator: std::iterator<std::input_iterator_tag, T, ptrdiff_t, const T*, const T&>
        {
            Iterator(Node* node): node(node){}

            T&       operator*()        {return  static_cast<ValueNode*>(node)->data;}
            T*       operator->()       {return &static_cast<ValueNode*>(node)->data;}
            T const& operator*()  const {return  static_cast<ValueNode*>(node)->data;}
            T const* operator->() const {return &static_cast<ValueNode*>(node)->data;}

            Iterator& operator++()     /*prefix*/  { node = node->next; return *this;}
            Iterator& operator--()     /*prefix*/  { node = node->prev; return *this;}
            Iterator  operator++(int)  /*postfix*/ { Iterator result(*this);this->operator++(); return result;}
            Iterator  operator--(int)  /*postfix*/ { Iterator result(*this);this->operator--(); return result;}

            bool operator !=(Iterator const& rhs) const    { return node != rhs.node;}
            bool operator ==(Iterator const& rhs) const    { return !(*this != node);}

            mutable Node*   node;
        };

        LinkedList()
            : tail(&head)
            , count(0)
        {}

        ~LinkedList()
        {
            clear();
        }

        void clear()
        {
            while(head.next != &head)
            {
                Node*   old = head.next;
                head.next   = head.next->next;
                --count;
                delete old;
            }
        }

        LinkedList(LinkedList const& copy)
            : tail(&head)
            , count(0)
        {
            std::for_each(copy.head->next, copy.head, std::bind1st(std::mem_fun(&LinkedList::push_back), this));
        }
        LinkedList& operator=(LinkedList rhs)
        {
            rhs.swap(*this);
            return *this;
        }
        void swap(LinkedList& rhs) throw()
        {
            std::swap(head,     rhs.head);
            std::swap(tail,     rhs.tail);
            std::swap(count,    rhs.count);
        }

        bool    isEmpty()   const { return &head == tail; }
        size_t  size()      const { return count; }

        typedef Iterator           iterator;
        typedef Iterator const     const_iterator;

        iterator push_back(T const& value)
        {
            tail    = new ValueNode(value, tail);
            ++count;
            return iterator(tail);
        }

        void erase(iterator const& i)
        {
            Node*   newTail = (tail == i.node)
                                ? i.node->prev
                                : tail;
            tail    = newTail;
            --count;
            delete i.node;
        }

        iterator begin()                {return iterator(head.next);}
        const_iterator begin() const    {return iterator(head.next);}
        iterator end()                  {return iterator(&head);}
        const_iterator end() const      {return iterator(&head);}
};
#endif

Then Main

#include <LinkedList.h>
#include <iostream>

int main()
{
    LinkedList<int> list;
    list.push_back(5);
    LinkedList<int>::iterator item = list.push_back(7);
    for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
    {
        std::cout << *loop << "\n";
    }
    list.erase(item);
    for(LinkedList<int>::iterator loop = list.begin(); loop != list.end(); ++loop)
    {
        std::cout << *loop << "\n";
    }
}

Diagram of Node Insertion:

Node Before Insertion Starts

      after                                        
      #########                         #########   
   -->#  Next #------------------------>#  Next #----
      #       #                         #       #
   ---#Prev   #<------------------------#Prev   #<---
      #########                         #########    

                       NewNode(this)
                       #########
                       #   Next#
                       #Prev   #
                       #########

prev = after;

      after
      #########                         #########   
   -->#  Next #------------------------>#  Next #----
      #       #                         #       #
   ---#Prev   #<------------------------#Prev   #<---
      #########   |                     #########    
                  |
                  |    (this)
                  |    #########
                  |    #   Next#
                  -----#Prev   #
                       #########

next = after->next;

      after
      #########                         #########   
   -->#  Next #------------------------>#  Next #----
      #       #                  |      #       #
   ---#Prev   #<-----------------|------#Prev   #<---
      #########   |              |       #########    
                  |              |
                  |    (this)    |
                  |    ######### |
                  |    #   Next#--
                  -----#Prev   #
                       #########

prev->next = this;

      after
      #########                         #########   
   -->#  Next #------            ------>#  Next #----
      #       #     |            |      #       #
   ---#Prev   #<----|------------|------#Prev   #<---
      #########   | |            |      #########    
                  | |            |
                  | |  (this)    |
                  | |  ######### |
                  | -->#   Next#--
                  -----#Prev   #
                       #########

next->prev = this;

      after
      #########                         #########   
   -->#  Next #------            ------>#  Next #----
      #       #     |            |      #       #
   ---#Prev   #<--- |            |   ---#Prev   #<---
      #########   | |            |   |  #########    
                  | |            |   |
                  | |  (this)    |   |
                  | |  ######### |   |
                  | -->#   Next#--   |
                  -----#Prev   #<-----
                       #########

Answer 2

You have a problem with your constructor and push() method.

When you create a new linked list, you automatically create two new nodes - head and last. This means you can't have an empty linked list as every new linked list will have 2 nodes in it. This isn't what I'd expect a linked list to do; I'd expect a new linked list to have a count of 0 and for both head and last to point to NULL.

When I add an item using push(), the class does this:

last = newNode

However, because last was set to a new node struct in the constructor, the class just lost any reference to the existing last memory and caused a memory leak. Another issue you've got is you're not actually creating a trail from node to node: you never set the pointee property of the previously-last node.

The push() method should look something like this:

void LinkedList::push(int data){
    node *newNode = new node();
    newNode->data = data;
    newNode->pointee = NULL;

    if (!head) {
        head = newNode;
        last = newNode;
    } else {
        last->pointee = newNode;
        last = newNode;
    }

    ++count;
}

The constructor should look like this:

LinkedList::LinkedList(void)
{
    head = NULL;
    last = NULL;
    count = 0;
}

You aren't cleaning anything up the destructor so you're leaking all allocated nodes. The destructor should look something like this:

LinkedList::~LinkedList(void)
{
    node* current = head;
    node* next;

    while (current) {
        next = current->pointee;
        delete current;
        current = next;
    }
}

Finally, I'd suggest capitalising node to Node.

Answer 3

If you are interested in implementing some basic containers, it would be wise to learn about templates. Not only does this remove the need to have multiple copies for anything other than int, it also removes the need for a separate .cpp implementation file.

The Standard Template Library (STL) is a mass of template based classes and as a result, they can be used with basically any type of data.

template<class T>
class List
{
private:
    class Node
    {
        T value;
        Node *next;
        Node *previous;

        Node(const T &data)
            : value(data) { }
    };

    Node *head;
    Node *tail;
    int count;

public:
    List()
        : head(0), tail(0), count(0) { }

    List(const List &list)
        : head(0), tail(0), count(0)
    {
        // Assuming an iterator implementation, copy values
        for(Iterator i = list.Begin(); i != End(); i++)
            Append(*i);
    }

    List &operator =(const List &list)
    {
        List l(list);
        std::swap(head, l.head);
        std::swap(tail, l.tail);
        std::swap(count, l.count);
    }

    ~List()
    {
        Clear();
    }

    void Clear()
    {
        while(head)
        {
            Node *next = head->next;
            delete head;
            head = next;
        }
        count = 0;
        head = tail = 0;
    }

    void Append(const T &data)
    {
        Node *node = new Node(data);
        if (!head)
        {
            node->next = node->previous = 0;
            head = tail = node;
        }
        else
        {
            node->previous = tail;
            tail->next = node;
            node->next = 0;
            tail = node;
        }
        count++;
    }

    int Count() const
    {
        return count;
    }
};

After fully implementing the different functions needed for a functional doubly-linked list, you can use it in code like this.

List<float> numbers;
numbers.Append(1.23f);

List<std::string> strings;
strings.Append("Hello, world!");