Python linked list O1 insert/remove

Python

linked list

data structures

algorithm efficiency

O(1) operations

Python linked list O1 insert/remove

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms Data Structures Python

Introduction

A linked list supports O(1) insertion and removal at the head (and tail, if doubly linked) because these operations only update a constant number of pointers. Python does not have a built-in linked list class, but collections.deque provides O(1) append and pop at both ends. For a custom implementation, a doubly linked list with sentinel nodes gives the cleanest O(1) operations and simplifies edge case handling.

Singly Linked List

python

1class Node:
2    def __init__(self, data):
3        self.data = data
4        self.next = None
5
6class SinglyLinkedList:
7    def __init__(self):
8        self.head = None
9
10    def insert_at_head(self, data):
11        """O(1) - Insert at the beginning."""
12        new_node = Node(data)
13        new_node.next = self.head
14        self.head = new_node
15
16    def remove_from_head(self):
17        """O(1) - Remove and return the first element."""
18        if self.head is None:
19            raise IndexError("remove from empty list")
20        data = self.head.data
21        self.head = self.head.next
22        return data
23
24    def __iter__(self):
25        current = self.head
26        while current:
27            yield current.data
28            current = current.next
29
30# Usage
31ll = SinglyLinkedList()
32ll.insert_at_head(3)
33ll.insert_at_head(2)
34ll.insert_at_head(1)
35print(list(ll))  # [1, 2, 3]
36
37ll.remove_from_head()  # Returns 1
38print(list(ll))  # [2, 3]

Insertion and removal at the head are O(1) because they only modify the head pointer.

Doubly Linked List

A doubly linked list allows O(1) operations at both ends:

python

1class DNode:
2    def __init__(self, data):
3        self.data = data
4        self.prev = None
5        self.next = None
6
7class DoublyLinkedList:
8    def __init__(self):
9        # Sentinel nodes eliminate edge cases
10        self.head = DNode(None)  # dummy head
11        self.tail = DNode(None)  # dummy tail
12        self.head.next = self.tail
13        self.tail.prev = self.head
14        self._size = 0
15
16    def insert_at_head(self, data):
17        """O(1) - Insert after the dummy head."""
18        self._insert_after(self.head, data)
19
20    def insert_at_tail(self, data):
21        """O(1) - Insert before the dummy tail."""
22        self._insert_after(self.tail.prev, data)
23
24    def remove_from_head(self):
25        """O(1) - Remove the first real node."""
26        if self._size == 0:
27            raise IndexError("remove from empty list")
28        return self._remove_node(self.head.next)
29
30    def remove_from_tail(self):
31        """O(1) - Remove the last real node."""
32        if self._size == 0:
33            raise IndexError("remove from empty list")
34        return self._remove_node(self.tail.prev)
35
36    def _insert_after(self, node, data):
37        new_node = DNode(data)
38        new_node.prev = node
39        new_node.next = node.next
40        node.next.prev = new_node
41        node.next = new_node
42        self._size += 1
43
44    def _remove_node(self, node):
45        node.prev.next = node.next
46        node.next.prev = node.prev
47        self._size -= 1
48        return node.data
49
50    def __len__(self):
51        return self._size
52
53    def __iter__(self):
54        current = self.head.next
55        while current != self.tail:
56            yield current.data
57            current = current.next
58
59# Usage
60dll = DoublyLinkedList()
61dll.insert_at_tail(1)
62dll.insert_at_tail(2)
63dll.insert_at_tail(3)
64print(list(dll))  # [1, 2, 3]
65
66dll.remove_from_head()  # Returns 1
67dll.remove_from_tail()  # Returns 3
68print(list(dll))  # [2]

O(1) Removal by Node Reference

The key advantage of a doubly linked list is O(1) removal when you have a direct reference to the node:

python

1class DoublyLinkedList:
2    # ... (same as above)
3
4    def remove_node(self, node):
5        """O(1) - Remove a specific node by reference."""
6        if node is self.head or node is self.tail:
7            raise ValueError("cannot remove sentinel nodes")
8        node.prev.next = node.next
9        node.next.prev = node.prev
10        self._size -= 1
11        return node.data
12
13# Usage: O(1) removal with a stored reference
14dll = DoublyLinkedList()
15dll.insert_at_tail(1)
16node_b = DNode(2)  # Keep a reference
17dll._insert_after(dll.head.next, 2)
18# To use remove_node, store the actual node reference during insertion

This pattern is used in LRU caches where a hash map stores node references for O(1) lookup and the linked list maintains order.

LRU Cache Example

An LRU cache combines a dictionary (O(1) lookup) with a doubly linked list (O(1) reorder and eviction):

python

1class LRUCache:
2    def __init__(self, capacity):
3        self.capacity = capacity
4        self.cache = {}  # key -> node
5        self.head = DNode(None)
6        self.tail = DNode(None)
7        self.head.next = self.tail
8        self.tail.prev = self.head
9
10    def get(self, key):
11        if key not in self.cache:
12            return -1
13        node = self.cache[key]
14        self._move_to_front(node)
15        return node.data[1]  # (key, value)
16
17    def put(self, key, value):
18        if key in self.cache:
19            node = self.cache[key]
20            node.data = (key, value)
21            self._move_to_front(node)
22        else:
23            if len(self.cache) >= self.capacity:
24                # Evict least recently used (tail)
25                lru = self.tail.prev
26                self._remove(lru)
27                del self.cache[lru.data[0]]
28
29            node = DNode((key, value))
30            self._add_to_front(node)
31            self.cache[key] = node
32
33    def _add_to_front(self, node):
34        node.prev = self.head
35        node.next = self.head.next
36        self.head.next.prev = node
37        self.head.next = node
38
39    def _remove(self, node):
40        node.prev.next = node.next
41        node.next.prev = node.prev
42
43    def _move_to_front(self, node):
44        self._remove(node)
45        self._add_to_front(node)
46
47# Usage
48cache = LRUCache(2)
49cache.put(1, "a")
50cache.put(2, "b")
51print(cache.get(1))   # "a" — moves key 1 to front
52cache.put(3, "c")     # Evicts key 2 (least recently used)
53print(cache.get(2))   # -1 (evicted)

Using collections.deque

Python's deque provides O(1) append and pop at both ends:

python

1from collections import deque
2
3d = deque()
4
5# O(1) operations
6d.append(1)       # Add to right: deque([1])
7d.appendleft(0)   # Add to left:  deque([0, 1])
8d.append(2)       # Add to right: deque([0, 1, 2])
9
10d.pop()           # Remove from right: returns 2
11d.popleft()       # Remove from left:  returns 0
12
13# With max length (automatic eviction)
14d = deque(maxlen=3)
15d.append(1)  # [1]
16d.append(2)  # [1, 2]
17d.append(3)  # [1, 2, 3]
18d.append(4)  # [2, 3, 4] — 1 is evicted from the left

deque is implemented as a doubly linked list of fixed-size blocks, giving O(1) at both ends.

Operation Complexity Comparison

Operation	Singly Linked	Doubly Linked	deque	list
Insert at head	O(1)	O(1)	O(1)	O(n)
Insert at tail	O(n)	O(1)	O(1)	O(1) amortized
Remove from head	O(1)	O(1)	O(1)	O(n)
Remove from tail	O(n)	O(1)	O(1)	O(1)
Remove by reference	O(n)	O(1)	N/A	N/A
Access by index	O(n)	O(n)	O(n)	O(1)

Common Pitfalls

Forgetting to update both prev and next pointers: In a doubly linked list, every insertion or removal must update pointers in both directions. Missing one pointer creates a broken list that appears to work in one traversal direction but fails in the other.
Not using sentinel nodes: Without dummy head and tail nodes, every insertion and removal must check for None (empty list, single-element list). Sentinel nodes eliminate these edge cases and simplify the code.
O(n) removal without a node reference: Removing a value from a linked list by searching for it is O(n), not O(1). O(1) removal requires a direct reference to the node, typically stored in a hash map.
Using Python list as a linked list: list.insert(0, x) is O(n) because it shifts all elements. Use deque.appendleft() for O(1) head insertion or implement a proper linked list.
Memory overhead: Each linked list node stores two pointer references (16+ bytes each) in addition to the data. For small data like integers, the overhead can be several times larger than the data itself. Use deque or arrays when memory efficiency matters.

Summary

Singly linked lists support O(1) insert/remove at the head only
Doubly linked lists support O(1) insert/remove at both head and tail
O(1) removal by node reference requires a doubly linked list and a stored reference to the node
Use sentinel (dummy) head and tail nodes to eliminate edge cases
collections.deque provides O(1) operations at both ends and is the preferred choice for most use cases
The LRU cache pattern combines a hash map with a doubly linked list for O(1) lookup, insertion, and eviction

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Python linked list O1 insert/remove

Data Structures & Algorithms practice on Codemia

Introduction

Singly Linked List

Doubly Linked List

O(1) Removal by Node Reference

LRU Cache Example

Using collections.deque

Operation Complexity Comparison

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia