Mastering Singly and Doubly Linked Lists in Python

You want to learn about Linked Lists—a fundamental linear data structure where elements (called nodes) are connected via pointers/references, rather than being stored in contiguous memory (like arrays). Each node contains two parts: data (the value stored) and a pointer/reference to the next node (and optionally the previous node for doubly linked lists).

Linked Lists excel at dynamic data operations (insertions/deletions) and are used in applications like queues, stacks, and hash tables. Unlike arrays, they don’t require preallocated memory and can grow/shrink dynamically.

Core Types of Linked Lists

1. Singly Linked List (SLL)

Nodes only have a next pointer (each node points to the next node; last node points to None).
Traversal is only possible in one direction (from head to tail).
Simplest implementation but limited functionality.

2. Doubly Linked List (DLL)

Nodes have both next and previous pointers.
Traversal is possible in both directions (forward and backward).
More flexible but requires extra memory for the previous pointer.

3. Circular Linked List (CLL)

Last node points back to the first node (instead of None).
Can be singly or doubly linked.
Useful for applications requiring cyclic access (e.g., round-robin scheduling).

Key Terminology

Head: The first node of the linked list (starting point for traversal).
Tail: The last node of the linked list (points to None in SLL/DLL, or head in CLL).
Node: Basic unit containing data and pointers.
Empty List: Head is None (no nodes).

Singly Linked List Implementation (Python)

We’ll start with the most common type—Singly Linked List—with core operations: insert, delete, search, traverse, and reverse.

Full Implementation

python

运行

class Node:
    """Node class to represent each element in the linked list."""
    def __init__(self, data):
        self.data = data  # Value stored in the node
        self.next = None  # Pointer to the next node (initially None)

class SinglyLinkedList:
    """Singly Linked List implementation with core operations."""
    def __init__(self):
        self.head = None  # Head of the list (initially empty)
    
    def traverse(self):
        """Traverse the list and return all data as a list (for easy visualization)."""
        result = []
        current = self.head
        while current:  # Iterate until current is None (end of list)
            result.append(current.data)
            current = current.next
        return result
    
    def insert_at_beginning(self, data):
        """Insert a new node at the start of the list."""
        new_node = Node(data)
        new_node.next = self.head  # New node points to current head
        self.head = new_node  # Update head to the new node
    
    def insert_at_end(self, data):
        """Insert a new node at the end of the list."""
        new_node = Node(data)
        if not self.head:  # If list is empty, new node becomes head
            self.head = new_node
            return
        # Traverse to the last node
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node  # Last node points to new node
    
    def insert_after(self, target_data, new_data):
        """Insert a new node after the first occurrence of target_data."""
        current = self.head
        # Find the target node
        while current:
            if current.data == target_data:
                new_node = Node(new_data)
                new_node.next = current.next  # New node points to target's next
                current.next = new_node  # Target points to new node
                return
            current = current.next
        print(f"Target data {target_data} not found in the list.")
    
    def delete_node(self, target_data):
        """Delete the first node containing target_data."""
        # Case 1: List is empty
        if not self.head:
            print("List is empty—nothing to delete.")
            return
        # Case 2: Target is the head node
        if self.head.data == target_data:
            self.head = self.head.next  # Update head to next node
            return
        # Case 3: Target is in the middle/end
        current = self.head
        while current.next:
            if current.next.data == target_data:
                current.next = current.next.next  # Skip the target node
                return
            current = current.next
        print(f"Target data {target_data} not found in the list.")
    
    def search(self, target_data):
        """Search for target_data and return True if found, False otherwise."""
        current = self.head
        while current:
            if current.data == target_data:
                return True
            current = current.next
        return False
    
    def reverse(self):
        """Reverse the linked list in place."""
        prev = None  # Previous node (initially None)
        current = self.head  # Current node (starts at head)
        while current:
            next_node = current.next  # Store next node (before overwriting)
            current.next = prev  # Reverse current node's pointer
            prev = current  # Move prev to current node
            current = next_node  # Move current to next node
        self.head = prev  # Update head to the new first node (original last node)

# Test the Singly Linked List
if __name__ == "__main__":
    # Initialize empty list
    sll = SinglyLinkedList()
    
    # Insert nodes
    sll.insert_at_end(10)
    sll.insert_at_beginning(5)
    sll.insert_at_end(20)
    sll.insert_after(10, 15)
    print("After insertions:", sll.traverse())  # Output: [5, 10, 15, 20]
    
    # Search
    print("Is 15 present?", sll.search(15))  # Output: True
    print("Is 25 present?", sll.search(25))  # Output: False
    
    # Delete node
    sll.delete_node(10)
    print("After deleting 10:", sll.traverse())  # Output: [5, 15, 20]
    
    # Reverse list
    sll.reverse()
    print("After reversing:", sll.traverse())  # Output: [20, 15, 5]

Doubly Linked List Implementation (Python)

DLL adds a prev pointer to each node, enabling bidirectional traversal and easier insertions/deletions at both ends.

Full Implementation

python

运行

class DoublyNode:
    """Node class for Doubly Linked List (has prev and next pointers)."""
    def __init__(self, data):
        self.data = data
        self.prev = None  # Pointer to previous node
        self.next = None  # Pointer to next node

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None  # Track tail for O(1) insertions at end
    
    def traverse_forward(self):
        """Traverse from head to tail."""
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result
    
    def traverse_backward(self):
        """Traverse from tail to head (unique to DLL)."""
        result = []
        current = self.tail
        while current:
            result.append(current.data)
            current = current.prev
        return result
    
    def insert_at_end(self, data):
        """Insert at end (O(1) time, thanks to tail pointer)."""
        new_node = DoublyNode(data)
        if not self.head:  # Empty list
            self.head = new_node
            self.tail = new_node
            return
        # Link new node to tail
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node  # Update tail
    
    def delete_from_end(self):
        """Delete from end (O(1) time)."""
        if not self.head:
            print("List is empty—nothing to delete.")
            return
        if self.head == self.tail:  # Only one node
            self.head = None
            self.tail = None
            return
        # Move tail to previous node and remove link
        self.tail = self.tail.prev
        self.tail.next = None

# Test the Doubly Linked List
if __name__ == "__main__":
    dll = DoublyLinkedList()
    dll.insert_at_end(10)
    dll.insert_at_end(20)
    dll.insert_at_end(30)
    
    print("Forward traversal:", dll.traverse_forward())  # Output: [10, 20, 30]
    print("Backward traversal:", dll.traverse_backward())  # Output: [30, 20, 10]
    
    dll.delete_from_end()
    print("After deleting from end:", dll.traverse_forward())  # Output: [10, 20]

Time and Space Complexity

Singly Linked List

Operation	Time Complexity	Explanation
Traverse	O(n)	Must visit all nodes.
Insert at Beginning	O(1)	Directly update head (no traversal).
Insert at End	O(n)	Must traverse to last node (unless tail is tracked).
Insert After Target	O(n)	May need to traverse to find target.
Delete Node	O(n)	May need to traverse to find target (and its predecessor).
Search	O(n)	Must traverse until target is found.
Reverse	O(n)	Traverse once to reverse pointers.

Doubly Linked List (with Tail Pointer)

Operation	Time Complexity	Explanation
Insert at Beginning	O(1)	Update head and prev pointers.
Insert at End	O(1)	Use tail pointer (no traversal).
Delete from Beginning	O(1)	Update head and prev pointers.
Delete from End	O(1)	Use tail pointer (no traversal).
Traverse (Forward/Back)	O(n)	Must visit all nodes.

| Space Complexity (Both Types) | O(n) | Stores n nodes, each with data and pointers. |

Linked List vs. Array (Key Differences)

Feature	Linked List	Array
Memory Allocation	Dynamic (non-contiguous)	Static (contiguous, fixed size)
Insertions/Deletions	O(1) (at head/tail for DLL) or O(n)	O(n) (shift elements)
Random Access	O(n) (must traverse)	O(1) (direct index access)
Memory Overhead	Higher (stores pointers)	Lower (only data)
Resizing	Easy (no preallocation)	Hard (need to reallocate and copy)

Pros and Cons of Linked Lists

Pros

Dynamic Size: Grows/shrinks as needed—no need to predefine size (unlike arrays).
Efficient Insertions/Deletions: O(1) time for insertions/deletions at the head (SLL) or both ends (DLL) (no element shifting).
Flexible Memory Usage: Uses memory only for existing nodes (no wasted space from preallocation).
Foundation for Other Data Structures: Powers stacks, queues, hash tables, and graphs (adjacency lists).

Cons

No Random Access: Cannot access elements by index—must traverse from head/tail (O(n) time).
Higher Memory Overhead: Each node stores extra pointers (prev/next), increasing memory usage.
Slower Traversal: Cache performance is poor (non-contiguous memory) compared to arrays (contiguous memory).
Complex Implementation: DLL/CLL require managing more pointers (prone to bugs like broken links).

Real-World Applications of Linked Lists

Data Structures: Stacks, queues, and hash tables (chaining to resolve collisions) use linked lists.
Web Browsers: Back/forward navigation (DLL—each page is a node with prev/next pointers).
Music Players: Playlists (insert/delete songs efficiently; traverse forward/backward with DLL).
Operating Systems: Process scheduling (CLL for round-robin scheduling of processes).
Graphs: Adjacency list representation (each node points to its neighbors via linked lists).
Database Indexing: Some databases use linked lists for dynamic indexing (e.g., B+ trees).