Doubly Linked List Operations

By now, you are introduced to the structure of a doubly linked list and how each node stores two references: one to the next node and one to the previous node.

You have already implemented the core linked list operations for singly linked lists, including traversal, insertion, and deletion. The overall ideas behind these operations remain the same in a doubly linked list. However, because each node now stores an additional Prev reference, some extra reference updates are required to keep the structure consistent.

Let’s revisit the three core operations and understand how they work in a doubly linked list, and what changes they entail compared to singly linked lists.

Traversal in a doubly linked list

Traversal in a doubly linked list is primarily the same as traversal in a singly linked list. The process begins at the head node and repeatedly follows the Next reference until the end of the list is reached.

As in a singly linked list, a temporary reference, such as current, is used during traversal so that the head reference remains unchanged. At each step, the data stored in the current node can be processed, such as printing the value or comparing it with a target.

The main difference is that a doubly linked list also supports backward traversal, because each node stores a reference to the previous node.

In summary:

• Forward traversal works exactly like it does in a singly linked list by following the Next references.

• Backward traversal becomes possible by following the Prev references.

Backward traversal

To traverse backward in a doubly linked list:

1. First move to the last node in the list.

2. Process the data stored in the current node.

3. Move to the previous node using current = current.Prev;.

4. Repeat this process until current becomes null, which indicates that the beginning of the list has been passed.

Let’s look at the following interactive visualizer for doubly linked list traversal.