Doubly Linked List: Operations and Use Cases

Basic Operations on Doubly Linked Lists

Doubly linked lists support essential operations, made efficient by their bidirectional links. Let’s explore them with simple analogies.

Traversal

Traversal involves visiting each node to process its data. With doubly linked lists, you can:

• Move Forward: Start at the head, process the data, and follow the next pointer until reaching the tail (where next is null). It’s like walking a trail from start to finish.
• Move Backward: Begin at the tail, process the data, and follow the previous pointer until hitting the head (where previous is null). This is like retracing your steps.

This flexibility is perfect for tasks requiring data access in both directions.

Insertion

Adding a new node is like linking a new piece into a chain. There are three main methods:

At the Beginning

• Create a new node with the data.
• Point its next pointer to the current head.
• If the list isn’t empty, set the current head’s previous pointer to the new node.
• Make the new node the head.

This is quick and doesn’t require traversing the list.

At the End

• Create a new node.
• If the list is empty, it becomes the head.
• Otherwise, find the last node (where next is null), link its next pointer to the new node, and set the new node’s previous pointer to the last node.
• Update the tail to the new node.

With a tail pointer, this is fast; otherwise, traversal is needed.

At a Specific Position

• Create a new node.
• Traverse to the target position.
• Link the new node’s next pointer to the following node and its previous pointer to the current node.
• Adjust the surrounding nodes’ pointers to include the new node.

This keeps the chain intact by updating both directions.

Deletion

Removing a node is like unlinking a chain segment. Here’s how:

From the Beginning

• If the list isn’t empty, move the head to the next node.
• Set the new head’s previous pointer to null.
• Free the old head’s memory.

This is straightforward and fast.

From the End

• If the list isn’t empty, locate the last node.
• Set the second-last node’s next pointer to null, making it the new tail.
• Free the old tail’s memory.

A tail pointer speeds this up.

From a Specific Position

• Traverse to the node to remove.
• Link the previous node’s next pointer to the following node.
• Link the following node’s previous pointer to the previous node.
• Free the removed node’s memory.

This ensures the list remains connected.

Finding the Length

To count nodes, start at the head, increment a counter for each node, and follow the next pointers until reaching the tail. This takes O(n) time, as every node must be visited, similar to counting links in a chain.

Time Complexities:

Note: O(1) applies when positions are known (e.g., head or tail); traversal raises it to O(n).

Advanced Operations

Doubly linked lists also handle more advanced tasks:

• Searching: Traverse forward or backward to find a value, taking O(n) time.
• Reversing: Swap each node’s next and previous pointers, then swap head and tail, in O(n) time.
• Sorting: Rearrange nodes (e.g., via merge sort) in O(n log n) time, though less common.

These are popular in interviews. Check our Top DSA Interview Questions.

Use Cases for Doubly Linked Lists

Doubly linked lists shine in real-world scenarios:

• Text Editors: Store actions for undo (previous) and redo (next).
• Caches: Enable fast addition/removal in systems like LRU caches.
• Browser History: Navigate back and forth between pages.
• Music Playlists: Skip forward or backward in apps like Spotify.
• Deques: Support efficient operations at both ends.

Explore these in our Web Development course.