Linked Lists

After this lesson, you will be able to: Implement singly, doubly, and circular linked lists from scratch, and know exactly when a linked list beats an array and when it does not.

A linked list trades the array's fast random access for fast insertion and deletion. Understanding that single tradeoff tells you everything about when to reach for one.

Prerequisites:Arrays and Dynamic Arrays

What a linked list is

Instead of one contiguous block, a linked list is a chain of nodes scattered anywhere in memory. Each node holds a value and a pointer to the next node. To find the 5th element you must start at the head and follow 5 pointers. There is no address math, so access is O(n). But to insert a new node, you just rewire two pointers, which is O(1) once you are at the spot.

A singly linked list in Python

Implement it by hand. This is a classic interview ask.

python

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

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

    def prepend(self, value):       # O(1): new head
        node = Node(value)
        node.next = self.head
        self.head = node
        self.size += 1

    def find(self, value):          # O(n): must walk the chain
        current = self.head
        while current:
            if current.value == value:
                return current
            current = current.next
        return None

    def to_list(self):
        out, current = [], self.head
        while current:
            out.append(current.value)
            current = current.next
        return out

Singly vs doubly vs circular

A singly linked list has next pointers only, so you can move forward but not back. A doubly linked list adds a prev pointer in each node, so you can walk both directions and delete a node in O(1) if you already have a reference to it. A circular linked list points the last node back to the first, useful for round-robin scheduling and buffers that wrap. Doubly linked lists power things like browser history and LRU caches.

Try it: reverse a linked list

The single most common linked-list interview question. Do it before looking at any solution.

1
1. Keep three pointers: prev (start None), current (start head), and next.
2
2. In a loop: save next = current.next, point current.next back to prev.
3
3. Advance: prev = current, current = next.
4
4. When current is None, prev is the new head.
5
5. Test it on [1,2,3,4] and confirm you get [4,3,2,1].

Common mistakes only experienced devs catch

Losing the rest of the list by reassigning current.next before saving the next node (always save next first). Forgetting to update the tail pointer when you maintain one. Off-by-one errors at the head and tail (the boundaries are where linked-list bugs live). Reaching for a linked list in production for performance when an array would be faster due to cache locality. Creating a cycle by accident and then looping forever (use Floyd's tortoise-and-hare to detect cycles).

←Arrays and Dynamic Arrays

Back to Data Structures

Stacks→