Linked Lists — Core Concepts

Why linked lists matter

Linked lists are a foundational data structure in computer science. While Python’s built-in list (a dynamic array) covers most use cases, understanding linked lists teaches you about pointers, memory layout, and the tradeoffs between sequential and linked storage. They also appear constantly in coding interviews and are the backbone of structures like LRU caches, undo systems, and memory allocators.

Singly linked list

Each node stores data and a reference to the next node:

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def prepend(self, data):
        self.head = Node(data, self.head)
    
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)
    
    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

Doubly linked list

Each node has references to both the next and previous nodes, enabling traversal in both directions:

class DNode:
    def __init__(self, data, prev_node=None, next_node=None):
        self.data = data
        self.prev = prev_node
        self.next = next_node

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, data):
        new_node = DNode(data, prev_node=self.tail)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
    
    def prepend(self, data):
        new_node = DNode(data, next_node=self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node
    
    def delete_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

Doubly linked lists allow O(1) deletion when you have a reference to the node — no need to find the previous node first.

Performance comparison

Operation	Linked list	Python list (array)
Access by index	O(n)	O(1)
Prepend	O(1)	O(n)
Append	O(1) with tail pointer	O(1) amortized
Insert in middle	O(1) if at node	O(n) due to shifting
Delete in middle	O(1) if at node	O(n) due to shifting
Search	O(n)	O(n)
Memory per element	Higher (data + pointers)	Lower (contiguous)

When to use linked lists in Python

Use a linked list when:

• You need frequent insertions or deletions at both ends (though collections.deque is better).
• You are implementing data structures that require node references (LRU cache, skip list).
• You need to splice lists together in O(1) — cutting and joining linked lists is cheap.

Use a Python list when:

• You need random access by index.
• Memory efficiency matters (arrays have no pointer overhead).
• You iterate more than you insert or delete.

In practice, Python’s list and collections.deque cover most scenarios. Custom linked lists are mainly useful for learning and for specialized structures.

The sentinel node trick

A sentinel (dummy) node at the head simplifies edge cases by eliminating special handling for an empty list:

class SentinelLinkedList:
    def __init__(self):
        self.sentinel = Node(None)  # dummy head
    
    def prepend(self, data):
        self.sentinel.next = Node(data, self.sentinel.next)
    
    def delete(self, data):
        current = self.sentinel
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

No more if not self.head checks — the sentinel is always there.

Common misconception

“Linked lists are obsolete because we have dynamic arrays.” In Python specifically, that is mostly true — list is almost always better. But linked lists remain essential as building blocks for other structures (hash map chaining, graph adjacency lists, LRU caches with O(1) eviction) and for understanding how memory and references work.

One thing to remember: Linked lists trade random access speed for insertion and deletion flexibility. In Python, reach for list or deque first, but know how linked lists work — they will appear in interviews, library internals, and specialized data structures.