beginnerintermediateadvanced

Data Structures & Algorithms · Section 13

Linked Lists

Level: beginner
Read: 95 min
Concepts: 11

Singly and doubly linked nodes, the O(1)-splice-vs-O(n)-access trade-off that defines the structure, plain traversal, reversing a list with three tracking pointers, Floyd's cycle detection and middle-finding, merging two sorted lists, removing the Nth node from the end, the dummy-node trick that removes head-of-list special cases, and when a hand-rolled linked list is (and mostly is not) the right tool.

What is true here

A linked list trades a Python list's O(1) random access for O(1) insert/delete at a node you already hold a reference to.
Reversing, cycle detection, and middle-finding are all variations on tracking two or three pointers through one traversal.
A dummy node before head removes "is this the head?" as a special case from insert and delete alike.
A hand-rolled linked list is rarely the production answer in Python — list and deque already cover its use cases, usually faster.

What you will be able to do

Build a singly and a doubly linked list, and traverse either one correctly
Reverse a linked list in place using the three-pointer technique, without losing the rest of the list
Apply Floyd's fast/slow pointer to detect a cycle and to find the middle of a list in one pass
Use a dummy node to remove head-of-list special cases from insert, delete, and the Nth-from-end pattern

Concepts

From node-and-pointer basics and the O(1)-vs-O(n) trade-off they create, through traversal, reversal, and the fast/slow pointer patterns, to merging, Nth-from-end removal, the dummy-node trick, and when to actually reach for a hand-rolled list.

Singly linked list — node with value + next

corebeginner

Instead of one contiguous block like a list, a singly linked list is a chain of separate nodes — each one holds its own value plus a pointer to the NEXT node, ending in None.

Think of it as

There is no single memory block to index into. The list is really just node 1 pointing at node 2 pointing at node 3, and so on until a node points at None. To reach node 5, you must walk through nodes 1 through 4 first — there is no shortcut in.

What we're doing: Build a small linked list by hand and traverse it, collecting every value into a plain Python list.

singly_linked_list.pypython

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


head = Node(1, Node(2, Node(3)))

values = []
node = head
while node:
    values.append(node.value)
    node = node.next
print(values)

7: Node(1, Node(2, Node(3))) builds the chain inside out — the innermost Node(3) is built first, then wrapped by Node(2), then Node(1).
8: node starts at head and is reassigned to node.next every iteration — the loop stops the instant node becomes None.

Output

[1, 2, 3]

Why this works: Node(1, Node(2, Node(3))) wires up head.next to the node holding 2, and that node's next to the node holding 3, whose own next defaults to None — walking .value then .next three times collects every value before the loop hits None and stops.

Collecting the node itself instead of node.value

Wrong

python

def to_list_wrong(head):
    values = []
    node = head
    while node:
        values.append(node)          # appends the NODE, not node.value
        node = node.next
    return values


head = Node(1, Node(2, Node(3)))
result = to_list_wrong(head)
print(result[0] == head)
print(result[0].value)

Better

python

def to_list(head):
    values = []
    node = head
    while node:
        values.append(node.value)
        node = node.next
    return values

What you see: to_list_wrong(head) returns a list of Node objects, not their values — result[0] is literally the same object as head (True), and reading it needs .value to see anything meaningful.

Why: The loop variable node walks the chain correctly, but appending node itself instead of node.value collects a list of Node objects — real data, technically, but not the values the function promised to collect.

Remember: A linked list is a chain of nodes, not a block of memory — head is the only way in, and every node is only reachable by following .next from something that came before it.

Was this helpful?

Doubly linked list — node with prev + next

standardbeginner

A doubly linked list node carries TWO pointers instead of one — next forward and prev backward — so the list can be walked in either direction.

Think of it as

Every node knows both its neighbors, not just the one ahead of it. That means a node can be removed in O(1) given only a reference to it — node.prev.next = node.next and node.next.prev = node.prev — with no need to also track down its predecessor first, unlike a singly linked list.

What we're doing: Build a small doubly linked list and walk it forward from the head and backward from the tail.

doubly_linked_list.pypython

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


def build_doubly(values):
    head = tail = None
    for v in values:
        node = DNode(v, prev=tail)
        if tail:
            tail.next = node
        else:
            head = node
        tail = node
    return head, tail


head, tail = build_doubly([1, 2, 3])

forward = []
node = head
while node:
    forward.append(node.value)
    node = node.next

backward = []
node = tail
while node:
    backward.append(node.value)
    node = node.prev

print(forward)
print(backward)

3: Each node stores prev alongside next — the backward link that a singly linked list does not have.

Output

[1, 2, 3]
[3, 2, 1]

Why this works: Walking from head following .next visits the list in insertion order, [1, 2, 3]. Walking from tail following .prev retraces the exact same chain backward, [3, 2, 1] — the same nodes, either direction, because every node carries both pointers.

Remember: A doubly linked list trades one extra pointer per node for O(1) removal of any known node, and the ability to walk backward — a singly linked list gives you neither.

Was this helpful?

Why linked lists give O(1) insert/delete at a known position but O(n) access by index

corebeginner

Inserting or deleting at a node you already have a reference to is just relinking a couple of pointers — O(1), no matter how long the list is. Reaching the k-th node has no shortcut: the only way in is to walk from the head, one .next at a time — O(n).

Think of it as

A Python list can jump straight to index k because its elements sit at a computable memory offset. A linked list has no such offset — the only path to any node is through every node before it. Insertion is the opposite trade: once you are already standing at a node, splicing a new one next to it touches a fixed, small number of pointers, regardless of whether that node is the 1st or the 100,000th.

What we're doing: Insert a new node right after a given node reference, then find a value by walking to a given index.

insert_and_access.pypython

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


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


def value_at_index(head, index):
    node = head
    for _ in range(index):
        node = node.next
    return node.value


head = Node(1, Node(2, Node(4)))
second = head.next
insert_after(second, 3)

values = []
node = head
while node:
    values.append(node.value)
    node = node.next
print(values)
print(value_at_index(head, 2))

7: insert_after touches exactly two pointers — the new node's next, and the known node's next — regardless of where in the list `node` sits.
12: value_at_index has no shortcut: it walks one node at a time, index times, to reach the target.
13: Same cost whether index is 0 or 1,000,000 — there is no computable offset to jump to, unlike a Python list.

Output

[1, 2, 3, 4]
3

Why this works: insert_after(second, 3) splices a new node holding 3 between 2 and 4, giving 1 → 2 → 3 → 4 — two pointer writes, whether the list had 3 nodes or 3 million. value_at_index(head, 2) then walks from head two steps to confirm the value at that position is 3.

Building the new node's next AFTER overwriting the old link

Wrong

python

def insert_after_wrong(node, value):
    node.next = Node(value)   # drops whatever used to come after `node`


head = Node(1, Node(2, Node(4)))
second = head.next
insert_after_wrong(second, 3)

values = []
node = head
while node:
    values.append(node.value)
    node = node.next
print(values)

Better

python

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

What you see: insert_after_wrong(second, 3) on 1 → 2 → 4 produces [1, 2, 3] — node 4 vanishes entirely, not just skipped.

Why: Node(value) with no next argument defaults to None, discarding whatever node.next used to point at. Inserting means relinking THROUGH the new node — its next must be set to the old next before the predecessor is overwritten, or everything after the insertion point becomes unreachable.

Remember: A linked list trades O(n) random access for O(1) insert/delete at a node you already hold a reference to — and always relink the new node's own pointer before you overwrite the old one.

Was this helpful?

Traversal

referencebeginner

Visiting every node means starting at head and following .next until you reach None — there is no other way in, and no way to start from the middle without already holding a reference to it.

traversal.pypython

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


head = Node(1, Node(2, Node(3)))

node = head
while node is not None:
    print(node.value)
    node = node.next

Remember: Every linked-list algorithm is traversal plus one extra idea — start at head, follow .next, stop at None.

Reversing a linked list (iterative and recursive)

corebeginner

Reversing means walking the list once, and at each node, flipping .next to point BACKWARD instead of forward — three variables track this: prev (the reversed portion built so far), curr (the node being flipped), and a saved copy of curr.next so the forward link is not lost the moment it is overwritten.

Think of it as

Picture peeling nodes off the front of the original list and stacking them onto a new, reversed list one at a time. prev is the head of that growing reversed stack. Before curr.next gets overwritten to point at prev, its original value has to be saved somewhere — next_node — or the rest of the original list is lost the instant the pointer is flipped.

What we're doing: Reverse a linked list in place, one node at a time, using three tracking pointers.

reverse_list.pypython

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


def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev


def to_values(head):
    values = []
    node = head
    while node:
        values.append(node.value)
        node = node.next
    return values


head = Node(1, Node(2, Node(3, Node(4))))
reversed_head = reverse_list(head)
print(to_values(reversed_head))

4: next_node saves curr.next BEFORE it gets overwritten — this is the line that protects the rest of the list.
5: curr.next = prev is the actual flip — curr now points backward, at the reversed portion built so far.
6: prev advances to curr — the reversed portion grows by one node.
7: curr advances to the saved next_node — the original forward chain, still intact for the next iteration.

Output

[4, 3, 2, 1]

Why this works: 1 → 2 → 3 → 4 flips one link per iteration: after all four nodes are processed, prev points at what used to be the tail (4), and every node's .next now points at the node that used to come before it — exactly the reverse order.

Overwriting curr.next before saving it

Wrong

python

def reverse_list_wrong(head):
    prev = None
    curr = head
    while curr:
        curr.next = prev       # overwrites curr.next before it's saved
        next_node = curr.next  # too late — this is now `prev`, not the real next node
        prev = curr
        curr = next_node
    return prev


head = Node(1, Node(2, Node(3, Node(4))))
reversed_head = reverse_list_wrong(head)
print(to_values(reversed_head))

Better

python

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

What you see: reverse_list_wrong(head) on 1 → 2 → 3 → 4 returns just [1] — nodes 2, 3 and 4 are all lost.

Why: curr.next is overwritten to point backward BEFORE the real forward link is captured. The moment curr.next = prev runs on the first node, the only reference to the rest of the list is gone — next_node then reads back prev (None), not the real next node, so the loop stops after a single iteration.

Reverse Linked ListeasyLeetCode
Exactly the example above — the three-pointer iterative reversal.
Reverse Linked List IImediumLeetCode
The same reversal, applied only to a sub-section of the list — locate the boundaries first, then splice the reversed piece back in.

Remember: Save curr.next before you touch it, flip curr.next to point at prev, then advance both prev and curr — do those three steps in any other order and the rest of the list is lost.

Was this helpful?

Detecting a cycle (Floyd's fast/slow pointer)

standardintermediate

Move two pointers through the list at different speeds — one node at a time, and two nodes at a time. If they ever land on the same node, the list loops back on itself; if the fast one hits the end first, it does not.

Think of it as

slow moves one node at a time, fast moves two. If the list ends cleanly, fast (or fast.next) hits None first and the loop stops. If there is a cycle, fast can never escape it — it keeps lapping the loop faster than slow, and the gap between them shrinks by one node every step, until they land on the exact same node.

What we're doing: Detect whether a linked list loops back on itself, and confirm a normal, non-cyclic list reports no cycle.

has_cycle.pypython

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


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


a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
c.next = a  # cycle: node c points back to node a

clean = Node(1, Node(2, Node(3)))

print(has_cycle(a))
print(has_cycle(clean))

8: while fast and fast.next guards against fast running off the end of a genuinely non-cyclic list.
10: slow is fast checks object identity — the same node, not just an equal value.

Output

True
False

Why this works: a → b → c → a loops forever, so fast keeps circling inside it and eventually lands on the same node as slow. clean has a real end (None), so fast.next becomes None before slow and fast ever meet.

Remember: fast moves two nodes for every one of slow's — if a cycle exists, that gap can only shrink to zero, never skip past it, so they are guaranteed to meet.

Was this helpful?

Finding the middle of a list in one pass

standardintermediate

Move a slow pointer one node at a time and a fast pointer two nodes at a time — when fast reaches the end, slow is standing exactly halfway, without ever counting the list's length.

Think of it as

The same fast/slow shape as cycle detection, asking a different question. fast covers ground twice as fast as slow — so by the time fast has reached the end, slow has covered exactly half the distance, which means slow is standing at the middle.

What we're doing: Find the middle node of both an odd-length and an even-length list in a single pass.

middle_of_list.pypython

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


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


odd = Node(1, Node(2, Node(3, Node(4, Node(5)))))
even = Node(1, Node(2, Node(3, Node(4))))

print(middle_value(odd))
print(middle_value(even))

8: slow advances one node; fast advances two — fast reaches the end after exactly half as many steps as a full traversal would take.

Output

3
3

Why this works: On the 5-node list, fast runs out of room after 2 steps, leaving slow at node 3 — the true middle. On the 4-node list, there is no single true middle; slow lands on node 3, the second of the two middle nodes (2 and 3) — the standard result for this loop shape.

Remember: fast covers twice the distance slow does — when fast runs out of list, slow is standing exactly halfway, in one pass, no length count needed.

Was this helpful?

Merging two sorted linked lists

standardintermediate

Walk both sorted lists at once, always splicing the smaller of the two current nodes onto the result and advancing that list — the same two-pointer merge idea used on arrays, but relinking existing nodes instead of copying values into a new one.

Think of it as

Same idea as merging two sorted arrays with two pointers, but instead of writing into a new array, the smaller node is spliced directly onto the result by relinking .next — no extra storage beyond the nodes that already exist. A dummy node gives the result list a stable starting point to build onto.

What we're doing: Merge two sorted linked lists into one sorted list by relinking nodes, without allocating new ones.

merge_sorted_lists.pypython

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


def merge_sorted(a, b):
    dummy = Node(None)
    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 if a else b
    return dummy.next


def to_values(head):
    values = []
    node = head
    while node:
        values.append(node.value)
        node = node.next
    return values


list_a = Node(1, Node(3, Node(5)))
list_b = Node(2, Node(4, Node(6)))
merged = merge_sorted(list_a, list_b)
print(to_values(merged))

7: dummy gives tail somewhere to point before either real head is known to be the smaller one.
12: Once either a or b runs out, the loop ends — tail.next = a if a else b attaches whichever list still has nodes left.

Output

[1, 2, 3, 4, 5, 6]

Why this works: At each step the smaller of a.value and b.value is spliced onto tail, and that list advances — 1, 2, 3, 4, 5 are picked off alternately from list_a and list_b, and once list_a runs out after 5, the remaining node 6 from list_b is attached whole.

Remember: Splice the smaller head onto the result and advance that list — reuse the nodes that already exist instead of building new ones, and a dummy node removes the "which head goes first?" special case.

Was this helpful?

Removing the Nth node from the end (two-pointer with a gap)

coreintermediate

Send fast n steps ahead first, then move fast and slow together, one step at a time, keeping that n-node gap. When fast falls off the end, slow is sitting exactly one node before the one that needs removing.

Think of it as

The list's length is not known up front, and there is no way to count backward from the end directly. Opening an n-node gap between two pointers and then walking them together turns 'n from the end' into 'a position both pointers can agree on without ever counting the whole list twice' — one pass to open the gap, one more to walk it closed.

What we're doing: Remove the 2nd node from the end of a 5-node list, using a dummy node and a two-pointer gap.

remove_nth_from_end.pypython

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


def remove_nth_from_end(head, n):
    dummy = Node(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next


def to_values(head):
    values = []
    node = head
    while node:
        values.append(node.value)
        node = node.next
    return values


head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
result = remove_nth_from_end(head, 2)
print(to_values(result))

8: fast is sent n steps ahead of slow first — both start at dummy, so the gap between them is exactly n nodes.
9: Once fast reaches the last real node (fast.next is None), slow has landed exactly one node before the target — the gap held steady the whole way.
12: slow.next = slow.next.next detaches the target node by skipping over it — a single relink, no shifting.

Output

[1, 2, 3, 5]

Why this works: The 2nd node from the end of 1 → 2 → 3 → 4 → 5 is 4. Opening a 2-node gap and walking both pointers together lands slow on node 3 exactly when fast runs out of list — slow.next.next skips past 4, leaving 1 → 2 → 3 → 5.

Removing the head itself, with no dummy node to land on

Wrong

python

def remove_nth_from_end_wrong(head, n):
    fast = slow = head
    for _ in range(n):
        fast = fast.next
    while fast and fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head


head = Node(1, Node(2, Node(3)))
result = remove_nth_from_end_wrong(head, 3)
print(to_values(result))

Better

python

def remove_nth_from_end(head, n):
    dummy = Node(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

What you see: remove_nth_from_end_wrong(head, 3) on 1 → 2 → 3 returns [1, 3] — node 2 disappears instead of node 1, and node 1, which should have been removed, is still there.

Why: With n equal to the whole list length, the node to remove is the head itself — but slow starts AT head, with no node before it to land on. slow never moves before the removal line runs, so slow.next.next ends up deleting node 2 instead, and the function still returns the unchanged head. A dummy node before head fixes this by giving slow a valid "one before the head" position to start from.

Remove Nth Node From End of ListmediumLeetCode
Exactly the example above — a dummy node plus a two-pointer gap of size n.
Middle of the Linked ListeasyLeetCode
A different question, but the same fast/slow shape — no gap needed here, since "the middle" does not require counting from the end.

Remember: Open an n-node gap from a dummy node, walk both pointers together until fast runs out, then skip over slow.next — the dummy node is what makes removing the head itself work like every other case.

Was this helpful?

Dummy/sentinel head node trick (avoids edge-case branching)

standardintermediate

Create one throwaway node that points at the real head, and do every insert/delete relative to IT instead of head directly — that way, removing or inserting at the head needs no special case, because there is always a real node before whatever position you are working on.

Think of it as

A dummy node sits one slot before the real head, so "the node before position i" always exists, even when i is 0. Every insert or delete becomes the same operation — modify some_node.next — with no separate branch for "what if this is the head?" Return dummy.next at the end to get the real, possibly-changed, head.

What we're doing: Remove every node matching a target value — including the head — using one code path, no special case for the head.

dummy_node.pypython

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


def remove_value(head, target):
    dummy = Node(0, head)
    prev = dummy
    while prev.next:
        if prev.next.value == target:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next


def to_values(head):
    values = []
    node = head
    while node:
        values.append(node.value)
        node = node.next
    return values


head = Node(1, Node(2, Node(1, Node(3))))
result = remove_value(head, 1)
print(to_values(result))

8: dummy is created pointing at the real head — prev starts here, one slot before node 1.
10: The exact same branch handles removing the head (prev is dummy) and removing any other node (prev is a real node) — no separate case for either.

Output

[2, 3]

Why this works: Both 1s are removed, including the one at the very front — prev.next = prev.next.next runs identically whether prev is the dummy node (removing the head) or a real node further in. dummy.next then reads off whatever the real head ends up being, which in this case is 2.

Remember: A dummy node one slot before head turns "is this the head?" from a branch you have to write into a case that just falls out of the same code as everything else.

Was this helpful?

When Python programmers actually use a hand-rolled linked list vs just a list or deque

referencebeginner

Almost never, in production code. Python's list and deque already give O(1) or O(n) exactly where a linked list would, usually with better constant factors — a hand-rolled linked list mainly exists to demonstrate pointer manipulation itself, in an interview or a course.

Remember: Reach for list or deque first, always — a hand-rolled linked list earns its place only when you need to splice nodes directly, or you are demonstrating pointer manipulation itself.

Was this helpful?

Spotted a mistake on this page? Tell us.

Read Sheet