Circularly and Doubly Linked Lists

What Are Circularly Linked Lists?

In the last post, we explored singly linked lists and their implementation. Singly linked lists consist of nodes that contain data and a reference to the next node in the list. Singly linked lists have two special properties, head which defines the start point of the list and tail which defines the endpoint of the list.

A circularly linked list removes the idea of a start and end point of the list and instead assumes a cyclic view of it. This means that instead of the list ending, it will loop round to the node that was previously at the start or end.

Design of the Circularly Linked List

The design of a circularly linked list is very similar to that of a normal singly linked list. In a circularly linked list, the tail node has a reference to the head node instead of a null value, thus causing the traversal to loop around.

A Circularly linked list This change means that the head node can actually be located from the tail, thus eliminating the need to store a separate reference for the head. The head can now be found by looking at the next property of the tail node.

By not storing a reference to the head node, we can save space and simplify the code.

What Are Doubly Linked Lists?

Until now, the data structures outlined have only been able to travel in one direction: forwards. The singly linked list and circularly linked list are able to traverse forwards as they have a reference to the next node in the list.

This approach does come with its drawbacks. For example, although we are able to easily delete a node from the start (head) of the list, it isn’t currently possible to delete a node from the end of the list without extra properties, nor is it possible to delete a node from a position within the list.

A doubly linked list addresses the above issues by providing an additional reference, this reference holds the node that appears before the current. Now that the nodes have references going forwards and backwards, the linked list can be traversed in both directions. For the purposes of this explanation, the forwards reference will be called next and the backwards one will be called prev.

Doubly Linked list In the figure above, it can be seen that the head and tail properties of the linked list have been removed. In their place stands the header and trailer nodes – these are referred to as sentinels and do not actually contain any data but exist to simplify the code.

For example, with the header and trailer sentinels, it can be assumed that every new node insert will always happen between two other nodes. This assumption means that a generalised insertion method can be written instead of having separate ones for the start and end of the list.

Inserting With a Doubly Linked List

When inserting a new node into a doubly linked list, the next and prev properties of the new node should point to the next and previous nodes in relation to that new node. Additionally, the forwards (next) reference of the preceding node should be updated to point to the new node as was as the prev reference of the node after the new one.

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 linked list.

public void AddBetween(Object data, Node before, Node after) { Node newNode = new Node(); newNode.data = data; newNode.prev = before; newNode.next = after;

  before.next = newNode;
    after.prev  = newNode

    head = toAdd;
}

Doubly linked list insert Adding a node to a doubly linked list

Deleting a Node Within a Doubly Linked List

When deleting a node from a doubly linked list the same consideration for the nodes neighbours must be made, the next pointer of the node before the target needs to be updated to point to the node after the target. Opposite is required of the node that comes after the target.

List deleting Removing a name from a doubly linked list Although the node isn’t explicitly deleted, any references to it are removed and this will lead to it being reclaimed by the system.

Code

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

public void RemoveNode(Node target)

public void RemoveNode(Node target) { Node before = target.prev; Node after = target.next;

    before.next = after;
    after.prev = before;
}