Doubly Linked Lists

Going Both Ways

In the last section, we explored singly linked lists, which are like a one-way street. Each node knows what comes next, but has no idea what came before. This is great for moving forward, but what if you need to reverse course?

Enter the doubly linked list. It's a two-way street. Each node still has a pointer to the next node, but it also adds a second pointer to the previous node. This simple addition makes the data structure much more flexible.

Each node now holds three pieces of information: the data itself, a pointer to the next node, and a pointer to the previous node. The very first node's previous pointer points to null, and the very last node's next pointer also points to null, signaling the ends of the list.

The Two-Way Advantage

This bidirectional structure gives us two major advantages over singly linked lists.

1. You can traverse the list backwards. If you have a pointer to a node in the middle of the list, you can easily travel to the beginning, not just the end. This is impossible with a singly linked list without starting over from the head.

2. Deleting a node is more efficient. With a singly linked list, if you want to delete a specific node, you need a pointer to the node before it to update its next reference. This often means you have to traverse the list to find that preceding node. In a doubly linked list, the node you want to delete already knows its predecessor. You can access it directly through the previous pointer, update the pointers, and remove the node without an extra search.

To remove node B, you just need to tell A that its next node is now C, and tell C that its previous node is now A. Node B is then completely bypassed and can be removed.

Real-World Uses

You've likely used doubly linked lists without realizing it. They are perfect for implementing features like:

Browser History: The 'back' and 'forward' buttons in your web browser navigate through a list of pages you've visited.
Undo/Redo Functionality: In a text editor or image program, each action is a node. 'Undo' moves to the previous node, and 'Redo' moves to the next.
Music Playlists: Skipping to the 'next' or 'previous' song is a classic example of traversing a doubly linked list.

Implementation Basics

Implementing a doubly linked list starts with defining the node structure. Each node needs to store its data, a pointer to the next node, and a pointer to the previous one.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  // Pointer to the next node
        self.prev = None  // Pointer to the previous node

class DoublyLinkedList:
    def __init__(self):
        self.head = None // Points to the first node
        self.tail = None // Points to the last node

The list itself usually keeps track of both the head (the first node) and the tail (the last node). Having a pointer to the tail makes it very fast to add new items to the end of the list, another small but handy advantage.

A double linked list is a data structure that allows traversal in both directions.

Ready to check your understanding?

Quiz Questions 1/4

What is the primary structural difference between a node in a singly linked list and a node in a doubly linked list?

Quiz Questions 2/4

Which of these real-world software features is an ideal application for a doubly linked list?

While they use a bit more memory because of the extra pointer in each node, the flexibility of doubly linked lists makes them a powerful tool for many common programming problems.

Advanced Linked List Structures