Doubly Linked List: Definition, Example, and Use Cases

A doubly linked list is a data structure where each element (node) contains a value and two links: one to the next node and one to the previous node. This allows easy navigation forwards and backwards through the list.

How It Works

Imagine a train where each carriage is connected to the one before it and the one after it. In a doubly linked list, each node is like a carriage that knows about the carriage in front and the one behind. This means you can move forward or backward through the list easily.

Each node stores three things: the data it holds, a link to the next node, and a link to the previous node. When you add or remove nodes, you update these links to keep the list connected in both directions.

Example

This example shows how to create a simple doubly linked list in Python, add nodes, and print the list forwards and backwards.

python

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    def print_forward(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next
        print()

    def print_backward(self):
        current = self.head
        if not current:
            return
        while current.next:
            current = current.next
        while current:
            print(current.data, end=' ')
            current = current.prev
        print()

# Usage
my_list = DoublyLinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print('Forward:')
my_list.print_forward()
print('Backward:')
my_list.print_backward()

Output

Forward:
10 20 30 
Backward:
30 20 10 

When to Use

Use a doubly linked list when you need to move easily in both directions through a list of items. This is helpful in applications like web browsers (to go back and forward between pages), music playlists (to skip forward or backward), or undo/redo features in software.

They are also useful when you need to insert or delete items from the middle of a list efficiently, as you can update links without starting from the beginning.

Key Points

• Each node has two links: one to the next node and one to the previous node.
• Allows traversal forwards and backwards.
• Insertion and deletion are efficient if you have the node reference.
• Uses more memory than singly linked lists because of the extra link.

Key Takeaways

A doubly linked list lets you move forward and backward through nodes easily.

Each node stores data plus links to both the next and previous nodes.

It is useful for applications needing two-way navigation or efficient insertions/deletions.

Doubly linked lists use more memory than singly linked lists due to extra links.