Exploring the Singly Linked List

A singly linked list is one of the simplest and most common data structures in computer science.

The linked list is a collection of elements, each of which contains a data attribute as well a reference to other nodes. In the case of singly-linked lists, the reference points to the next element in the data structure and there is no way to tell what node came before it.

The linked list is dynamic in size i.e. the size of the structure is not decided at compile time.

Linked List example From the figure above, we can see that the first and last elements in the linked list are treated differently to the other element – we have the introduction of the terms Head and Tail.

In order for the linked list to work, we must keep a reference to the first node in the list, this is referred to as the head. Similarly, there has to be a way of denoting that the end of the linked list has been reached, this is done by setting the reference in the last node to be null.

The structure can now be traversed by starting at the head and following the references in each node until we hit a null, thus indicating that we have traversed the entire list.

Modifying a Linked List

There a many ways a linked list can be modified:

Adding an Element at the Head

Adding an element at the start of a linked list is an easy endeavour. To do this we must create a new node and assign the already existing head reference to be the next pointer for this node. The head pointer must now point to the added node as this is the first node in the structure.

Adding element at head

Code

An example C# implementation of this process can be found below. The newNode object represents a node that is to be added to the start of the linked list.

public void AddNodeAtHead(Object data)
{
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = head;

    head = toAdd;
}

Adding an Element at the Tail

The opposite, adding a node at the end of the linked list, referred to as the tail, is just as easy. To achieve this, a new node is created and the tail nodes reference will now point to the new node rather than NULL. To finish this task, the new tail has its reference changed to be null.

Adding a node to the tail

Code

An example C# implementation of this process can be found below. The newNode object represents a node that is to be added to the end of the linked list.

public void AddNodeAtTail(Object data)
{
        Node newNode = new Node();
        newNode.data = data;

        Node current = head;
        while (current.next != null)
        {
            current = current.next;
        }

        current.next = newNode;
}

Removing a Node From the Head

To remove an element from the head of a singly linked list, the reference stored in the head must be changed to reference the next node.

Code

An example C# implementation of this process can be found below. The newNode object represents a node that is to be added to the end of the linked list.

This code makes the assumption that there are already pre-existing elements in the linked list.

public void RemoveFromHead(Object data)
{
head = head.next;
}