C++ Templated Linked-List Class Example


I am tired of messing with the STL List class with all the strange sytax like (&(*object)).function() and those iterators to keep track of. So, I decided to write my own. I had a miserable time finding a tutorial on how to build a linked-list that uses templates (but plenty that hold just ints - wheee!) so here is my own. First thing's first:

    List Node Class

    Even before we can design a list node class, we have to quickly visit some issues that come up. Since I can't think of a way to pass parameters to the constructor of the object stored in the node class, it will have to define a default, parameterless constructor. (You have to do the same thing with the STL list class.) When an object is added, the assignment operator is called - and unless the templated class overrides it, a simple bitwise copy of the object is performed. This is fine for most classes but if it those classes allocate any memory on the heap, pointers to that memory are copied - not the contents of that memory. 

    template <class T> class SimpleListNode {

public:
	// Variable access functions
	T &get() { return object; };
	void set(T &object) { this->object = object; };

	SimpleListNode<T> *getNext() { return nextNode; };
	void setNext(SimpleListNode<T> *nextNode) { this->nextNode = nextNode; };

private:
	// Node variables
	// object is an instance of the cargo class this node is carrying
	// nextNode is the pointer to the next node in the list
	T object;
	SimpleListNode<T> *nextNode;
};

      Notes

      All the bits having to do with templates are highlighted in blue. It was helpful to me to think of it just like a macro expansion that you would #define. After saying tempate <class T>, use T (or whatever name you like) wherever you would normally place the variable type. Also notice that when referring to templated classes, the brackets (< >) and templated class essentially become part of the name.
    List Class


    I want to make the interface to the list as simple as possible. We need functions to do these things:
    • add
    • remove
    • get
    • next

    So here's a basic class outline. 

    template <class T> class SimpleList {

public:
	SimpleList();
	~SimpleList();
	
	void add(T &addObject);		
	void remove();

	T &get();
	
	void start();
	bool next();
	
	int getSize();

private:
	int size;
	SimpleListNode<T> *headNode;
	SimpleListNode<T> *currentNode, *lastCurrentNode;
};

      Notes

      This seems to be the most efficient interface for accessing the list - in code, it looks like: 
      list.start(); // Reset the list to the beginning
while (list.next()) {	// Iterate through all the elements
	list.get().storedClassFunction();	// Get the elements
}
      The list is internally arranged so that it starts with a dummy node with 'NULL' for the pointer to the next node, and each added node is essentially inserted between the dummy and the 'NULL' so that the node at the end of the list always points to 'NULL'.

      The dummy node is needed for the remove operation - for consistancy, the remove() always causes the currently accessible element to be removed and reset to the previous element so calling next() after remove() does not skip any elements. If you want to remove something at the beginning of the list, you have a problem - hence, the dummy.

      This arrangement is quite simple, but has the side effect of listing elements backwards from the order they were added. There's also no way of sorting, but neither of these things particularly matter to me. (If you want things sorted - you'll have to overload the class to keep sorted's < operator and add the code to insert in order in the add() function.)

    Implementation

      Constructor

      SimpleList() {
	// Create the head dummy node
	headNode = new SimpleListNode;
	headNode->setNext(NULL);

	currentNode = NULL;
	size = 0;
};

      Add

      void add(T &addObject) {

	// Create a new list node
	SimpleListNode *newNode = new SimpleListNode;

	// Set the object
	newNode->set(addObject);
	
	// Insert the new node in between the head node
	// and the last inserted node
	newNode->setNext(headNode->getNext());
	headNode->setNext(newNode);

	size++;
};

      Remove

      void remove() {

	// Cut the currentNode out of the chain
	lastCurrentNode->setNext(currentNode->getNext());
	
	// Delete it - this will also call the destructor
	// of the object the node contains
	delete currentNode;

	// Move the current node back one, so that next()
	// will always point to the next element
	currentNode = lastCurrentNode;

	size--;
};

      Next

      // In addition to advancing the element currently
// pointed at, report whether or not the 
// advancement was successful
bool next() {

	// If the currentNode points at nothing
	// we've reached the end
	if (currentNode == NULL)
		return false;

	// Update the last current node and current node
	lastCurrentNode = currentNode;
	currentNode = currentNode->getNext();

	// If currentNode points at nothing or there 
	// is nothing added, we can return false
	if (currentNode == NULL || size == 0) 
		return false;
	else
		return true;
};

      Get

      T &get() { 
	// If we have reached the end, reset the 
	// currently accessible element (start over)
	if (currentNode == NULL) 
		start();

	return currentNode->get(); 
};

      Destructor

      ~SimpleList() {

	SimpleListNode<T> *pointerToDelete, *pointer = headNode;

	// Iterate through the list
	// deleting nodes as we go
	while (pointer != NULL) {
		pointerToDelete = pointer;
		pointer = pointer->getNext();
		delete pointerToDelete;
	}
};


      start() simply points the current and lastCurrent pointer to the dummy headNode. The complete source is available below.

      Source
    Use

      Here's a simple program to demonstrate the use of the class. It creates a list of class 'A' objects, but you can use any type you want. (Even pointers and ... ints)

      Sample.cpp

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

class A {

public:
	A() { this->value = 0; };
	A(int value) { this->value = value; };
	int value;
};

int main(int args, char**) {

	SimpleList<A> list;

	list.add(A(5));
	list.add(A(12));
	list.add(A(4));
	list.add(A(8));
	list.add(A(24));
	list.add(A(48));
	list.add(A(13));

	list.start();

	while (list.next()) {

		std::cout << "List Element: " << list.get().value << "\n";

		if (list.get().value == 13) list.remove();
		else if (list.get().value == 5) list.remove();
	}

	std::cout << "\n";

	list.start();

	while (list.next())
		std::cout << "List Element: " << list.get().value << "\n";

	return 0;
}

      Output

      C:\Temp\SimpleList\Debug>simplelist
List Element: 13
List Element: 48
List Element: 24
List Element: 8
List Element: 4
List Element: 12
List Element: 5

List Element: 24
List Element: 8
List Element: 4
List Element: 12
List Element: 5


      Source

      The code was compiled and tested with Visual C++ 6.0 - it should work with other compilers but I haven't tested it. If you decide to use it, best of luck to you. It could probably benefit from a function to clear the list - just duplicate the destructor code.

      My Code Section