Node

The node is the most basic building block for many common data structures. It fulfils 2 major functions. First is that it provides a mechanism to contain a piece of data, for example, the integer value ‘3’. The second is that it provides means of connecting itself to other nodes via an object reference pointer, known as the ‘next’ pointer.

Node Chains

We will now look at nodes through an example. Say we have a first initial node containing the integer value 3, without any other nodes the next pointer will be set to null. Now, let's add a second node containing the integer value 5. We set the next pointer of the first node to our new node and hence we have created a chain!

This process can be repeated for many more nodes, let's now take a look at some code and see how a node object may be defined and how the linking process might take place.

As we discovered above, the node class has 2 responsibilities; It must contain a value, in this case, an integer and a link to the next node in the list.

public class Node {
    public int Value { get; set; }
    public Node Next { get; set; }
}

Let's start by creating the first node in our chain, we will allocate the value as ‘3’ and the pointer to null…

Node first = new Node { Value = 3 };

We can now go ahead and create the next node in the chain, this node will have the value of ‘5’…

Node middle = new Node { Value = 5 };

It is worth noting that we have only created two nodes and assigned values to them, the pointers are each set to null. We will want to set the next pointer of the first node to the middle.

first.next = middle;

This process can be repeated time and time again…

Node last = new Node { Value = 7 };
middle.next = last; 

Linked List

Now that we know how to chain together nodes of data, let's explore what it would take to make the leap to a functioning linked list. First, there are a few things we need to understand. A Linked list is a single chain of nodes with a well-defined starting point known as the list head as well as the last node in the list known as the tail. Linked lists provide operations such as add, remove, find and enumerate which allow the list items to managed, searched and enumerated. It is these function that holds the true power of a linked list, let's take a look at them...

Add to front

It all starts from an empty list, recall that a list will always begin with a head and a tail both initialised to null. The first step is to allocate a node, in our example above, we create a node with the value 3 and the next pointer set to null.

Node first = new Node { Value = 3 };

As this list currently only has a single item, we will point both the head and tail pointers to this node.

Head = first;
Tail = first;

Now the linked list has a node to begin the rest of the chain. Adding a second node is basically the same operation. We allocate a new node and point the head to it, connecting its next pointer to the node that used to be the head.

Node second = new Node { Value = 5 };
Head = second;
second.next = first;

Since we are adding the node the front of the list, we do not need to change the tail, that will remain as the node we added first.

Let's have a look at this code…

public void AddFirst(LinkedListNode node)
{
//shave off the head node so we don’t lose it
LinkedListNode temp = head;

//Point head to the new node
Head = node;

//insert the rest of the list behind the head
Head.Next = temp;

Count++;

if (Count == 1){
// if the list was empty the Head and Tail should
// both point to the new node
Tail = Head;
}
}

as you can see, this is a very efficient operation, the performance remains constant no matter how big the list is. This is a clear strength of the linked list

Add to rear

We've seen how useful it is to add a node to the front of the list, it is just as useful to add a node to the rear. It all starts from an empty list, with both head and tail pointers set to null. It's that tail pointer that's going to make this operation much easier. The first step is to allocate a node, in our example above, we create a node with the value 3 and the next pointer set to null.

Node first = new Node { Value = 3 };

As this list currently only has a single item, we will point both the head and tail pointers to this node.

Head = first;
Tail = first;

Now when a second node is created, the head pointer remains unchanged and the tail points to the new node. Having the tail pointer allows us to add a new node to the end very easily, without this pointer we would not be able to so easily access the end of the list. Let's have a look at the code for this operation…

public void AddLast(LinkedListNode node)
{
if (count == 0){
head = node;
} else {
tail.next = node
}

Tail = node;
count++;
}

There are only 2 cases we need to worry about: whether we are adding a node to an empty list or an existing node chain. If the list is empty, point the lists head pointer to the new node. If the list is not empty, we chain the being added to the end of the existing chain. In any case, the tail pointer should now make the tail point to the node being added and increment the counter which is keeping track of how many nodes are in the list.

Remove Items

Like add, nodes can be removed from either the front or the back of the list. Let's take a look at some code...

public void RemoveLast()
{
if (count != 0){
if (count == 1){
head = null;
tail = null;
}
else {
LinkedListNode current = head;
while (current.next != tail) {
current = current.next;
}
current.next = null;
tail = current;
}
count--;
}
}

Enumerate

Enumerating over nodes is not difficult, but is done so frequently that it is a good idea to take a look at it and familiarise yourself with the process. The key to enumerating over a linked list is to keep a pointer to the next node to enumerate. Let's take a look at some code…

public void Enumerate()
{
LinkedListNode current = head;
while (current != null)
{
System.out.println(current.value);
current = current.next;
}
}

We start with a node called current which is initially assigned the head. While current is not equal to null, the value of current is printed to the console and current is assigned to the next node in the chain. When current is assigned to a node which is null, the node chain has ended.

This approach could also be used to search for a particular node value, rather than printing the value, compare it with some other predefined value.

Doubly Linked List

What we’ve looked at so far is referred to as a Singly Linked List, it's called that because each node has a single link to the next node. This application works fine when we only need forward access to the chain but some times we may need both forward and backward access. There is a special implementation of the linked list where by each node has a link to both the next and previous nodes. This is known as a Doubly Linked List.

Modern Implementations

So far in this module we’ve spent our time discussing the linked list data structure and created a simple implementation. In the real world however, it would be unlikely to come across many situations where you would create linked list structure. Typically, you would use a language or framework that provides a linked list class which is already tested, performant and compatible with your application. Unless you have proven need for your own implementation, I recommend using the ones provided in your given language/framework.