Linked List in Python: Singly and Doubly

A linked list is a chain of small objects called nodes. Each node stores a value and a reference to the next node. The last node points to None. Unlike a Python list, the items are not stored side by side. You reach them by following the links one by one from the first node, the head.

In everyday Python you will mostly use the built-in list. Linked lists are still worth learning, because they are a favourite interview topic and they teach you how references work. This guide builds a singly linked list and a doubly linked list from scratch, then solves the classic problems: reverse a list, find the middle, detect a cycle and merge two sorted lists. All the output shown is real.

The idea: nodes and links

Picture a treasure hunt where each clue tells you where to find the next one. Each box below is a node, and the arrow is the next reference:

head
 |
 [1 | next] --> [2 | next] --> [3 | next] --> None

A node is just a small class with two attributes. Here we link three of them by hand and then walk the chain until we fall off the end:

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

a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c

node = a
while node:
    print(node.value, end=" ")
    node = node.next
print()
print(c.next)

Output

1 2 3 
None

The loop while node: keeps going until node is None. This “walk with a pointer” pattern is the basis of everything else in this post. (If it feels strange that a.next = b links the objects instead of copying them, see Mutable vs Immutable in Python: names and attributes hold references.)

A singly linked list class

Managing nodes by hand gets tiring, so we wrap them in a class. It keeps the head, and also a tail and a size so that adding at the end and asking for the length are both instant:

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def append(self, value):            # O(1) thanks to the tail pointer
        node = Node(value)
        if self.head is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def prepend(self, value):           # O(1)
        node = Node(value, self.head)
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def find(self, value):              # O(n)
        node = self.head
        while node:
            if node.value == value:
                return node
            node = node.next
        return None

    def remove(self, value):            # O(n): find it, then skip over it
        prev, node = None, self.head
        while node:
            if node.value == value:
                if prev is None:
                    self.head = node.next
                else:
                    prev.next = node.next
                if node is self.tail:
                    self.tail = prev
                self.size -= 1
                return True
            prev, node = node, node.next
        return False

    def __iter__(self):
        node = self.head
        while node:
            yield node.value
            node = node.next

    def __len__(self):
        return self.size

    def __repr__(self):
        if self.head is None:
            return "None"
        return " -> ".join(str(v) for v in self) + " -> None"

ll = LinkedList()
for x in [10, 20, 30]:
    ll.append(x)
ll.prepend(5)
print(ll)
print(len(ll), ll.find(20).value, ll.find(99))
print(list(ll))

Output

5 -> 10 -> 20 -> 30 -> None
4 20 None
[5, 10, 20, 30]

__iter__ makes the list work in a for loop and in list(), and __repr__ prints the arrows. (Both are dunder methods, see Python Inheritance and Dunder Methods.)

Removing and inserting

To delete a node, you make the node before it skip over it: prev.next = node.next. That is why remove above walks with two pointers, prev and node. Three cases need care: the head, the middle and the tail:

ll = LinkedList()
for x in [1, 2, 3, 4]:
    ll.append(x)

print(ll.remove(3), ll)      # middle
print(ll.remove(1), ll)      # head
print(ll.remove(4), ll)      # tail
print(ll.remove(99))         # not there
ll.append(9)                 # the tail pointer is still right
print(ll, len(ll))

Output

True 1 -> 2 -> 4 -> None
True 2 -> 4 -> None
True 2 -> None
False
2 -> 9 -> None 2

Inserting works the other way round. Once you hold a node, putting a new one after it is just two pointer changes, and nothing else needs to move. That is O(1), and it is the main advantage over a Python list, where inserting shifts everything after that position:

def insert_after(node, value):
    node.next = Node(value, node.next)

head = build([1, 2, 4])
insert_after(head.next, 3)
print(to_list(head))

Output

[1, 2, 3, 4]

The order of the two steps inside insert_after matters. Node(value, node.next) first points the new node at the rest of the chain, and only then is node.next redirected to the new node. Do it the other way round and the rest of the chain is lost.

Reversing a linked list

The most asked linked list question. Walk the chain once and flip each arrow so that it points backwards. You need three variables: prev (the reversed part so far), head (the node being handled) and nxt (the saved rest of the chain):

def reverse(head):
    prev = None
    while head:
        nxt = head.next      # remember the rest of the chain
        head.next = prev     # flip the arrow
        prev = head          # step forward
        head = nxt
    return prev

print(to_list(reverse(build([1, 2, 3, 4]))))

Output

[4, 3, 2, 1]

Watching the reversed part grow makes it clear:

head = build([1, 2, 3])
prev = None
while head:
    nxt = head.next
    head.next = prev
    prev = head
    head = nxt
    print("reversed so far:", to_list(prev))

Output

reversed so far: [1]
reversed so far: [2, 1]
reversed so far: [3, 2, 1]

It runs in O(n) time and O(1) extra space, since it only rewires the existing nodes. The line nxt = head.next is essential: once the arrow is flipped, the rest of the chain would be unreachable without it.

Finding the middle (slow and fast pointers)

How do you find the middle of a list you cannot index, without counting it first? Use two pointers. The slow one moves one step at a time, the fast one moves two. When the fast one reaches the end, the slow one is in the middle:

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.value

print(middle(build([1, 2, 3, 4, 5])))
print(middle(build([1, 2, 3, 4])))

Output

3
3

For an even number of nodes this returns the second of the two middle nodes. It is one pass and O(1) space. This is the same two-pointer thinking as in Two Pointers in Python.

Detecting a cycle

What if the last node points back to an earlier node? A loop that follows next would run forever. Floyd’s cycle detection uses the same slow and fast pointers: if there is a cycle, the fast pointer eventually laps the slow one and they meet. If there is no cycle, the fast pointer reaches None:

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

head = build([1, 2, 3, 4])
print(has_cycle(head))

tail = head
while tail.next:
    tail = tail.next
tail.next = head.next        # the last node points back to the second one
print(has_cycle(head))

Output

False
True

Storing every visited node in a set also works, but costs O(n) memory. The two-pointer version needs none.

Merging two sorted lists

Given two sorted chains, build one sorted chain by always taking the smaller front node. A temporary dummy node at the start saves you from special-casing the first node:

def merge(a, b):
    dummy = Node(0)
    tail = dummy
    while a and b:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a or b       # attach whatever is left
    return dummy.next

print(to_list(merge(build([1, 4, 6]), build([2, 3, 7, 8]))))

Output

[1, 2, 3, 4, 6, 7, 8]

No new nodes are created, the existing ones are relinked. It is O(n + m) and it is the merge step of merge sort (see Sorting Algorithms in Python).

Doubly linked list

In a doubly linked list every node has both next and prev. You can walk in both directions, and, more importantly, if you hold a node you can remove it without searching for its predecessor:

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        return node

    def remove(self, node):              # O(1): no searching needed
        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

    def forward(self):
        node = self.head
        while node:
            yield node.value
            node = node.next

    def backward(self):
        node = self.tail
        while node:
            yield node.value
            node = node.prev

d = DoublyLinkedList()
a, b, c, e = [d.append(x) for x in "abcd"]
print(list(d.forward()), list(d.backward()))
d.remove(b)
print(list(d.forward()), list(d.backward()))
d.remove(a)
d.remove(e)
print(list(d.forward()), list(d.backward()))

Output

['a', 'b', 'c', 'd'] ['d', 'c', 'b', 'a']
['a', 'c', 'd'] ['d', 'c', 'a']
['c'] ['c']

The cost is one extra reference per node and a few more pointers to keep in sync. Real programs use doubly linked lists for an LRU cache (a dictionary for lookup plus a doubly linked list for recency order), browser history and undo systems. Python’s own collections.deque is built from linked blocks (see Queue and Deque in Python Explained).

Linked list vs Python list

A Python list is an array of references, so jumping to position i is instant. A linked list is the opposite: fast changes at a known position, slow lookups. Python lists are also stored in one block, which computers read very quickly, so in real Python code a list usually wins even where a linked list looks better on paper. Use a linked list to learn, to pass interviews, and when you truly need constant-time splicing. For a queue, use a deque. More about these costs in Time Complexity of Python Data Structures.

Common mistakes

• Losing the head. If you move head while walking, use a separate variable like node, or you can no longer reach the start.
• Changing a link before saving the next one. In reversal and insertion, store nxt first.
• Forgetting None checks. node.next.next fails with AttributeError if node.next is None. Check while node and node.next.
• Forgetting the empty list and one-node list. Test both, plus removing the head and the tail.
• Forgetting to update tail or size. Every method that changes the ends must keep them right.
• Creating a cycle by accident. A loop over a chain with a cycle never ends.

Try it yourself

Work out each answer first, then open the solution. The Node class and the build and to_list helpers from above are assumed.

1. Write length(head) that counts the nodes.

def length(head):
    count = 0
    while head:
        count += 1
        head = head.next
    return count

print(length(build([7, 8, 9])), length(None))

3 0

2. Remove duplicates from a sorted linked list.

def dedupe(head):
    node = head
    while node and node.next:
        if node.value == node.next.value:
            node.next = node.next.next
        else:
            node = node.next
    return head

print(to_list(dedupe(build([1, 1, 2, 3, 3, 3, 4]))))

[1, 2, 3, 4]

3. Return the 2nd node from the end without knowing the length.

def nth_from_end(head, n):
    lead = trail = head
    for _ in range(n):
        lead = lead.next
    while lead:
        lead = lead.next
        trail = trail.next
    return trail.value

print(nth_from_end(build([1, 2, 3, 4, 5]), 2))

4

4. Why is prepend O(1) on a linked list but O(n) for insert(0, x) on a Python list?

Run these in our free Python compiler.

Frequently asked questions

What is a linked list in Python?

A linked list is a chain of node objects, each holding a value and a reference to the next node. Python has no built-in linked list type, so you write a Node class yourself.

What is the difference between a linked list and a list in Python?

A Python list is an array: fast access by index, slow insertion at the front. A linked list is a chain of nodes: fast insertion and removal next to a known node, slow access by position.

What is the difference between singly and doubly linked lists?

A singly linked list has only a next link, so you move in one direction. A doubly linked list also has prev, so you can move both ways and remove a known node in O(1).

How do you reverse a linked list in Python?

Walk through the list and flip each node’s next to point to the previous node, keeping prev, head and a saved nxt. It takes O(n) time and O(1) space.

How do you detect a cycle in a linked list?

Use two pointers, one moving one step and one moving two steps. If they ever meet, there is a cycle. If the fast one reaches None, there is not.

Are linked lists used in real Python programs?

Rarely. Python lists and deque cover most needs. Linked lists matter for interviews and as the building block of structures such as LRU caches.

Related reading

• Queue and Deque in Python Explained – a queue that is fast at both ends.
• Two Pointers Technique in Python – the slow and fast idea on lists and strings.
• Binary Tree in Python: Traversals Explained – nodes with two links instead of one.
• Time Complexity of Python Data Structures – where each operation is cheap or costly.