Self Managing Linked List in C++

A Node Only Class in C++ Implementing a Simple Linked List

Jun 13, 2007

A simple application of C++ programming using the example of a linked list that can add to either end and insert nodes without a container class.

Introduction

This article deals with an interesting variation on a typical C++ linked list class. It is lightweight, easy to understand, but limited in some aspects. Typically, when we create a linked list, we tend to think of it in terms of

The nodes are where the data is stored, and the container class manages the relationship between the nodes. This leads to code where we type something akin to:

CList * oList = new CList();
CNode * oNode = new CNode();
oList-Add(oNode);
delete oList();

This is all very well, but we can actually create a self-managing linked list that only requires a single constructor to create a node and a list, combined:

CListNode * oHead = new CListNode();

The simplicity of this approach is that we never need to worry about the container, but the downside is that all the logic needs to be at the node level, which leads to some strange abstractions. However, these abstractions (such as writing to a file) do not require any extra code, just that the code that would have been in the container is now in the node management class instead.

The Node Class

We are going to assume that the list contains a series of numbers, for the sake of clarity. If we wished to, we could use a user-defined data structure (struct), or a data class with appropriate overloaded operators (such as comparison and assignment operators), but this would make the examples cumbersome for a tutorial. The basic class definition would look something along the lines of:

class CListNode
{
private :
int nData;
CListNode * oNext;
CListNode * oPrevious;
public:
CListNode(int nData);
~CListNode();
CListNode * AddNode(CListNode * oNewNode);
CListNode * InsertNode(CListNode * oNewNode);
int GetData();
int SetData(int nData);
CListNode * GetNext();
CListNode * GetPrevious();
};

The first node created becomes the head of the list. However, should it become necessary to displace the head, then the CListNode class undertakes to return the new Head element.

Adding to the List

Inside the AddNode class, we need to implement a function to traverse the list, node by node. At the same time, the node needs to be aware that, if it is the last node in the list (assuming that the constructor has set oNext and oPrevious to NULL), it needs to add the new node after itself, and link it appropriately. The code to do this is implemented here:

CListNode * CListNode::AddNode( CListNode * oNewNode )
{
if (this-oNext == NULL)
{
oNewNode-SetPrevious(this);
this-SetNext(oNewNode);
return oNewNode;
}
this-GetNext()-AddNode(oNewNode);
}

This algorithm is semi-recursive in that it does not call itself, but a copy of itself which is part of another instantiation of the class. The result of successive calls to AddNode is a doubly linked list, where the head is never displaced. However, were we to want a sorted version, this would not be the case.

Self-Sorting

A self-sorting list is easy enough to write. The ::InsertNode member function is used to do this. It is identical to the AddNode function in theory - the nodes must be traversed until the new node can be inserted. If the new node is at the head of the list, then the head must be displaced. Based on simple integer comparison, we could use code such as:

CListNode * CListNode::InsertNode( CListNode * oNewNode )
{
if ((oNewNode-GetData() nData) || (this-oNext == NULL))
{
// Insert before
if (this-oPrevious == NULL)
{
// It's the head
this-SetPrevious(oNewNode);
oNewNode-SetNext(this);
return oNewNode;
}
else
{
oNewNode-SetNext(this);
this-GetPrevious()-SetNext(oNewNode);
oNewNode-SetPrevious(this-GetPrevious());
this-SetPrevious(oNewNode);
return NULL;
}
}
this-GetNext()-InsertNode(oNewNode);
}

We need to return NULL to avoid displacement of the head node. This has the downside that we cannot check whether the node has been correctly inserted, or even if it has been added at all.

List Destruction

To destroy the list, we destroy the head. The result is a chain reaction, causing the entire list to self-destruct:

CListNode::~CListNode()
{
CListNode * oNextNode = this-GetNext();
if ( oNextNode != NULL)
{
delete oNextNode;
}
}

This technique is a little dangerous, as an incorrect call to an improperly deleted node, where it is still linked into the list, will cause everything after the node to be lost. It should be used with caution, and if respected, works very well, and reasonably efficiently.

The copyright of the article Self Managing Linked List in C++ in Computer Programming Tutorials is owned by Guy Lecky-Thompson. Permission to republish Self Managing Linked List in C++ in print or online must be granted by the author in writing.