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 #<-----
 #########

• Tom Kealy: Could you please explain why you assign next->prev to this and not after in the constructor? It's the only but of the code, I don't understand, even after drawing pictures.
• Loki Astari: @TomKealy: Hope that helps
• Tom Kealy: :O Thanks! I read the code as if you were inserting after between this and prev and thought it didn't make sense. Awesome pics.

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.

• Loki Astari: Most Liked list implementations use a head a tail terminator nodes to make the rest of the code easier to write (see your implementation of push() it could be half the length if you know head and tail are never NULL), so normally I would expect head and tail never to be NULL (though they should not be part of the count as they are not real nodes (they are just there to mark the ends)).
• Loki Astari: Though I also make type names always have a capitol letter first (as in Node) it is hard to make this an overall recommendation as the standard libraries do not use this convention see std::vector, std::map etc.
• Ant: @Loki: Interesting. Having terminator head and tail nodes would make a function that returned the actual tail an O(n) operation.
• Nick Bedford: I agree, Ant. I've implemented lists with iterator classes and I've always used null as the 'end' in the iterator. Also, Loki, I don't think STL and std:: conventions should dictate how any library's conventions should be written. If anything, I much prefer to use CamelCase as it appears more modern and formal. That's my style though.
• Loki Astari: @NickBedford: Using null as the terminator doubles the amount of code you need to write. The standard way of implementing this is to have a fake terminator 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!");

• Loki Astari: If you are going to implement the CopyConstructor (rather than disable) you should also add the assignment operator (see rule of 3/5). To save you I have added one.
• Loki Astari: I find the comment it also removes the need for a separate .cpp implementation file grossly misleading. It does not need to be a template for you to put all the code in the header file nor even if it is a template does not require you to put everything into the header file. In-fact I would suggest that non trivial template class are split into declaration and definition (just like normal code) so that the interface is easy to read (how you include it in the project is different (you use a .tpp or .tcc file that is included from the header). Check the standard library for examples.
• Nick Bedford: To be fair, I was only providing an example of templated code, so there's many things that I haven't included in the example. Operator overloads, copy constructors etc. But for me, I've never heard of templates being split into declaration and definition (besides specialisations), despite writing and looking at many templated classes. Just never come across it myself. That being said, I've tried reading STL code and I find it a chore to read because of the coding conventions used (personal opinion).
• Nick Bedford: I just looked at your assignment operator. I'm not sure how copying some pointers around will assign a List<T> to another List<T>. I would for intents and purposes expect (and functionally require) a copy of the nodes to be made for both lists to work independently.
• Nick Bedford: I stand corrected. I'm curious, do you have any books or references that would point me to more of these very specific implementation idioms?