Linked Lists

A linked list is a chain of nodes where each node holds a value and a pointer to the next node. Unlike arrays, elements are scattered in memory — you can’t jump to the nth element without walking from the head.

Why It Matters

Linked lists teach pointer manipulation, which is foundational for understanding trees, graphs, and memory management. They also appear in language runtimes and OS kernels.

Types

Type	Structure	Use
Singly linked	node → node → node → None	Simple, one direction
Doubly linked	None ← node ⇄ node ⇄ node → None	Traverse both ways
Circular	node → node → node → (back to head)	Round-robin, buffers

Operations

Operation	Singly	Doubly
Access by index	O(n)	O(n)
Insert at head	O(1)	O(1)
Insert at tail	O(n) or O(1) with tail ptr	O(1)
Delete at head	O(1)	O(1)
Delete by value	O(n)	O(n) search + O(1) remove
Search	O(n)	O(n)

Code Example

class Node:
    __slots__ = ('val', 'next')
    def __init__(self, val, next_node=None):
        self.val = val
        self.next = next_node
 
class LinkedList:
    def __init__(self):
        self.head = None
        self._size = 0
 
    def prepend(self, val):
        self.head = Node(val, self.head)
        self._size += 1
 
    def append(self, val):
        if not self.head:
            self.head = Node(val)
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = Node(val)
        self._size += 1
 
    def delete(self, val):
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            self._size -= 1
            return
        cur = self.head
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
                self._size -= 1
                return
            cur = cur.next
 
    def find(self, val):
        cur = self.head
        while cur:
            if cur.val == val:
                return cur
            cur = cur.next
        return None
 
    def __len__(self):
        return self._size
 
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.val
            cur = cur.next
 
# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
assert list(ll) == [1, 2, 3]
assert len(ll) == 3
ll.delete(2)
assert list(ll) == [1, 3]

Arrays vs Linked Lists

	Array	Linked List
Memory	Contiguous (cache-friendly)	Scattered (cache-hostile)
Access by index	O(1)	O(n)
Insert at front	O(n)	O(1)
Memory overhead	None (just data)	Pointer per node

In practice, arrays (Python lists) are almost always faster due to cache effects, even for insert-heavy workloads. Use linked lists when you need O(1) insert/delete at known positions (e.g., LRU cache with a doubly linked list + hash table).

Related

• Arrays — contiguous alternative
• Stacks and Queues — often implemented with linked lists
• Hash Tables — use linked lists for collision chaining
• Trees and Binary Search Trees — nodes with two pointers instead of one