Linked List Insertion and Deletion: Head, Middle and Tail

Inserting into the middle of an array means shifting every element after the gap. A linked list does the same job by rewriting two pointers, whatever its length. That contrast is the headline, and it is half true: the splice itself is O(1), but only once you hold the node before the gap, and getting there is a walk. Interview questions on linked lists are almost all about that walk, the order of the two writes, and the edge cases at the head and the tail.

The problem it solves

A singly linked list is a chain of nodes, each holding a value and a next reference, with None after the last one. It is the right structure when items are added and removed in the middle, at positions you already hold:

• LRU caches unlink a node and move it to the front on every access.
• Undo histories, playlists and free lists splice entries in and out without copying.
• Queues and stacks built from scratch add at one end and remove at the other.

An array keeps elements contiguous, so an insert at index i moves n - i elements. A linked list never moves a node; it only changes which node points at which.

The intuition

Insert after a node is two writes: point the new node at whatever came next, then point the predecessor at the new node. The order matters. Write the predecessor first and its old next, the only reference to the rest of the list, is gone.

Delete after a node is one write: node.next = node.next.next. The skipped node is no longer reachable from the head, so it is out of the list; in Python the garbage collector reclaims it once nothing else refers to it.

Everything else is about finding the predecessor and handling the ends:

• At the head there is no predecessor, so the head itself changes and the function must return the new head.
• At position i you walk i steps first: O(i).
• At the tail you walk the whole list, unless you keep a tail pointer, which then must be updated on every change at the end.
• A dummy head, a throwaway node placed before the real head, gives every real node a predecessor, so the head stops being a special case.

Two classic variations use the same surgery. Remove the nth node from the end walks two pointers n apart, so when the leading one runs off the end, the trailing one sits just before the target. Delete a node when you only hold that node has no predecessor at all; the trick is to copy the next node's value into it and delete the next node instead, which is impossible for the tail.

Watch it run

The animation runs the lesson's code on 1 → 3. We want a 2 in between, and we already hold the node it goes after. fresh = Node(2) is allocated wherever memory had room; it is not in the list yet, and its next is empty. fresh.next = node.next points the newcomer at the rest of the list first, while that address is still readable: one link write. Then node.next = fresh, the second write; overwriting in the other order would have thrown away the only reference to the 3. Done: 1 → 2 → 3 in two assignments, and nodes 1 and 3 never moved, which is O(1) whatever the list's length. Deleting is the mirror image. delete_after(head) targets the node the head points at, and node.next = node.next.next makes the predecessor skip straight over it, one more write. Nothing points at the 2 any more, so it is out of the list: no shifting, no resizing, just pointer surgery.

The code

The lesson's splice, the head and position cases with a dummy head, delete by value, and what the wrong write order does:

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

def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)                  # insert at the head: O(1)
    return head

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

def insert_after(node, value):
    fresh = Node(value)
    fresh.next = node.next                    # 1. the newcomer takes over the old link
    node.next = fresh                         # 2. the predecessor points at it

def delete_after(node):
    node.next = node.next.next                # skip straight over one node

def insert_at(head, i, value):
    """Insert so the value ends up at index i (0 = new head). Returns the head."""
    dummy = Node(None, head)                  # every real node now has a predecessor
    prev = dummy
    for _ in range(i):
        prev = prev.next                      # the O(i) walk to the predecessor
    insert_after(prev, value)
    return dummy.next

def delete_value(head, value):
    """Remove every node holding value, including the head. Returns the head."""
    dummy = Node(None, head)
    prev = dummy
    while prev.next:
        if prev.next.value == value:
            delete_after(prev)                # stay put: the new next may match too
        else:
            prev = prev.next
    return dummy.next

head = from_list([1, 3])
insert_after(head, 2)
print(to_list(head))                          # [1, 2, 3]
delete_after(head)
print(to_list(head))                          # [1, 3]
head = insert_at(head, 0, 0)                  # a new head, no special case
head = insert_at(head, 3, 4)                  # at the tail
print(to_list(head))                          # [0, 1, 3, 4]
print(to_list(delete_value(from_list([7, 7, 1, 7, 2, 7]), 7)))   # [1, 2]

broken = from_list([1, 3])
fresh = Node(2)
broken.next = fresh                           # wrong order: the 3 is now unreachable
fresh.next = broken.next                      # ...and fresh points at itself
print(fresh.next is fresh, broken.next.next.value)               # True 2

Two interview variations: removing the nth node from the end in one pass, and deleting a node you hold without its predecessor:

def remove_nth_from_end(head, n):
    """One pass: the lead pointer starts n + 1 steps ahead of the trailing one."""
    dummy = Node(None, head)
    lead = trail = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead, trail = lead.next, trail.next
    delete_after(trail)                       # trail sits just before the target
    return dummy.next

def delete_this_node(node):
    """No predecessor: become the next node, then unlink it. Not for the tail."""
    if node.next is None:
        raise ValueError("cannot delete the tail without its predecessor")
    node.value = node.next.value
    node.next = node.next.next

print(to_list(remove_nth_from_end(from_list([1, 2, 3, 4, 5]), 2)))  # [1, 2, 3, 5]
print(to_list(remove_nth_from_end(from_list([1]), 1)))               # []
lst = from_list([4, 5, 1, 9])
delete_this_node(lst.next)                    # we only hold the node with 5
print(to_list(lst))                           # [4, 1, 9]

Checked on 3,000 seeded random lists against a brute force: Python's own list with insert, del and a comprehension:

import random

rng = random.Random(31)
ok = True
for _ in range(3_000):
    values = [rng.randint(0, 5) for _ in range(rng.randint(0, 12))]
    i, v = rng.randint(0, len(values)), rng.randint(0, 5)
    ref = values[:i] + [v] + values[i:]                     # brute force: list.insert
    ok &= to_list(insert_at(from_list(values), i, v)) == ref
    ok &= to_list(delete_value(from_list(values), v)) == [x for x in values if x != v]
    if values:
        n = rng.randint(1, len(values))
        ref = values[:]
        del ref[len(ref) - n]                               # brute force: del by index
        ok &= to_list(remove_nth_from_end(from_list(values), n)) == ref
        if len(values) > 1:
            k = rng.randint(0, len(values) - 2)             # any node but the tail
            head = from_list(values)
            node = head
            for _ in range(k):
                node = node.next
            delete_this_node(node)
            ok &= to_list(head) == values[:k] + values[k + 1:]
print(ok)                                                   # True

The complexity

• Insert or delete after a node you hold: O(1) time, two writes or one.
• At the head: O(1), and the head changes.
• At index i or by value: O(i) or O(n) for the walk; the splice is still O(1).
• At the tail: O(n) without a tail pointer, O(1) with one for inserts. Deleting the tail of a singly linked list stays O(n), because the new tail's predecessor must be found; a doubly linked list fixes that.
• Space: O(1) extra. The Big-O cheat sheet puts these next to arrays.

Where it goes wrong

• Writing the predecessor first. The rest of the list is lost, as the broken example shows.
• Forgetting that the head can change. A function that deletes or inserts at index 0 must return the new head, and callers must use it. The dummy head removes this whole class of bugs.
• Advancing after a delete. In delete-by-value, moving prev forward after unlinking skips the next node, so two adjacent matches leave one behind.
• Dereferencing None. node.next.next fails when node is the last node. Check before splicing.
• Losing the tail pointer. If you keep one, deleting the last node must update it too.

When it shows up in interviews

Directly, as "remove nth node from end", "remove linked list elements" or "delete node in a linked list", and as the building block of harder problems: reversing a list, merging two sorted lists and the LRU cache. "Linked list vs array?" is a common warm-up, and the honest answer includes the walk.

How to say it in an interview

"Once I hold the predecessor, inserting is two pointer writes, new node's next first and then the predecessor's next, and deleting is one write that skips the node, both O(1). Finding the predecessor is the O(n) part. I'll use a dummy node before the head so inserting or deleting at position zero needs no special case, and return dummy.next as the new head. For remove nth from end I'd keep two pointers n plus one apart, so the trailing one stops right before the target, in one pass and O(1) space."