Doubly Linked List

Definition

A doubly linked list is a linked data structure in which each node contains three parts: the data field, a pointer to the next node, and a pointer to the previous node. The first node’s previous pointer is null, and the last node’s next pointer is null.

A basic node structure can be represented as:

[prev | data | next]

For example, a doubly linked list with elements 10, 20, and 30 can be represented as:

NULL <- [10] <-> [20] <-> [30] -> NULL

Here:

prev of the first node is NULL
next of the last node is NULL
each middle node connects to both neighboring nodes

This structure allows movement in both directions and makes it easier to access neighboring nodes during insertion and deletion.

Main Content

1. Structure of a Doubly Linked List

Node components

Each node has three fields:
data stores the actual value
prev points to the previous node
next points to the next node

Head and tail references

head points to the first node
tail points to the last node
These references make traversal and insertion at both ends efficient.

A small example:

head
  |
  v
NULL <- [A] <-> [B] <-> [C] -> NULL
                           ^
                           |
                          tail

In this structure:

node A has prev = NULL
node B links both to A and C
node C has next = NULL

This organization allows the list to be expanded or reduced without shifting elements, unlike arrays.

2. Traversal in Both Directions

Forward traversal

Start from head and follow the next pointers until NULL is reached.

Backward traversal

Start from tail and follow the prev pointers until NULL is reached.

Forward traversal example:

NULL <- [10] <-> [20] <-> [30] <-> [40] -> NULL

Sequence:

Start at 10
Move to 20
Move to 30
Move to 40

Backward traversal example:

Start at 40
Move to 30
Move to 20
Move to 10

This two-way movement is one of the biggest advantages of a doubly linked list. It is particularly useful when the last accessed element is near the end of the list or when both directions of navigation are required.

3. Insertion and Deletion Operations

Insertion

A new node can be inserted at the beginning, end, or middle by changing a few pointers.
At the beginning: update the new node’s next and the old head’s prev
At the end: update the new node’s prev and the old tail’s next
In the middle: reconnect surrounding nodes to include the new node

Deletion

A node can be removed more easily because the node itself already has a pointer to the previous node.
If deleting a node in the middle, update both neighboring links
If deleting the first or last node, update head or tail accordingly

Example of inserting 25 between 20 and 30:

Before:
NULL <- [10] <-> [20] <-> [30] -> NULL

After:
NULL <- [10] <-> [20] <-> [25] <-> [30] -> NULL

Example of deleting 20:

Before:
NULL <- [10] <-> [20] <-> [30] -> NULL

After:
NULL <- [10] <-> [30] -> NULL

Because each node stores both neighboring links, deletion does not require searching for the previous node separately, which is a major improvement over singly linked lists.

Working / Process

1. Create a node

Allocate memory for a new node.
Store the required data in the node.
Set its prev and next pointers appropriately.

2. Link the node into the list

If the list is empty, make the new node both head and tail.
If inserting at the beginning, connect the new node to the old head.
If inserting at the end, connect the new node to the old tail.
If inserting in the middle, update the neighboring nodes so the new node is placed correctly.

3. Traverse, update, or remove nodes

To traverse forward, move using next.
To traverse backward, move using prev.
To delete a node, reconnect its previous and next neighbors, then free the node.

A simple insertion process example for adding node X between A and B:

Before:
[A] <-> [B]

After:
[A] <-> [X] <-> [B]

The pointers are adjusted like this:

A.next = X
X.prev = A
X.next = B
B.prev = X

This precise pointer manipulation is what makes the doubly linked list efficient and flexible.

Advantages / Applications

Two-way traversal

You can move both forward and backward through the list, which is not possible in a singly linked list.

Efficient insertion and deletion

Especially useful when the node position is already known, because links can be updated directly without shifting elements.

Useful in real-world systems

Common applications include browser back/forward history, undo/redo functionality, playlists, navigation systems, and implementation of deques.

Doubly linked lists are especially valuable when frequent insertions and deletions occur in the middle of the structure, or when backward movement is necessary. However, they require extra memory for the prev pointer in every node, so they are chosen when their flexibility is more important than memory savings.

Summary

A doubly linked list is a linked structure where each node connects to both the previous and next node.
It supports traversal in both directions and simplifies insertion and deletion operations.
It is commonly used in applications that need flexible navigation and dynamic updates.
Important terms to remember: node, head, tail, prev pointer, next pointer, traversal, insertion, deletion.