Singly linked lists

Arrays are fantastic — until you keep changing them in the middle.

In the arrays post, we saw that inserting in the middle requires shifting every element after the insertion point — O(n) work. If your array is [10, 20, 30, 40, 50] and you want to insert 25 after 20, everything from 30 onward has to slide right by one slot.

A singly linked list attacks that exact pain point with a different layout. Instead of one contiguous block of memory, you store separate little objects called nodes. Each node knows its own value and where the next node lives. Think of it like a chain: each link only knows the next link, not the whole chain.

That sounds wonderfully flexible — and it is. Once you’re standing at the right place, insertion and deletion are just pointer updates, not mass shifting. But linked lists are not “better arrays.” They trade away fast indexing, cache-friendly memory access, and simple layout in exchange for cheaper rewiring.

So the goal of this post is not just “learn the code.” It’s to build the right mental model: what a node is, how pointers move, why reversal works, and where linked lists actually shine in interview questions and real systems.

What is a singly linked list?

A singly linked list is a sequence of nodes. Each node stores two things:

1. a value like 10 or "apple"
2. a reference (or pointer) to the next node

The list itself does not store everything in one contiguous chunk the way an array does. Instead, the nodes can live in completely different places in memory. What keeps the structure together is the chain of pointers.

You also keep one special reference called head. The head tells you where the list starts. If you lose head, you lose the list.

The final node has nowhere else to go, so its next pointer is null (or None in Python). That null marker is how traversal knows when to stop.

graph LR
  H[head] --> N1["10 | next"]
  N1 --> N2["20 | next"]
  N2 --> N3["30 | next"]
  N3 --> X["null"]

This “only knows the next node” rule is what makes the list singly linked. You can move forward, but not backward. That one detail explains a huge amount of linked list behavior:

• to find the 4th node, you must walk through the 1st, 2nd, and 3rd
• to insert in the middle, you need the node before the insertion point
• to delete a node cleanly, you usually need its predecessor

Compared with the memory post, arrays are about predictable addresses, while linked lists are about following references. Arrays win on direct access and cache locality. Linked lists win when rewiring is more important than indexing.

Node class implementation

The cleanest way to start is with a Node class. A node contains the value and a pointer to the next node. Then a LinkedList object simply stores the head.

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


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

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    LinkedList() {
        this.head = null;
    }
}

struct Node {
    int val;
    Node* next;

    Node(int v) : val(v), next(nullptr) {}
};

struct LinkedList {
    Node* head;

    LinkedList() : head(nullptr) {}
};

In Python, next=None means a newly created node does not point anywhere yet. In Java and C++, the same idea is null or nullptr.

The empty-list case is simple: self.head = None. The moment you insert your first node, head changes from None to that new node.

Traversal

Traversal means “walk through the list one node at a time.”

Because a singly linked list has no indexing formula like arrays do, the only way to reach later nodes is to start at head and keep following next.

def print_list(head):
    current = head

    while current:
        print(current.val)
        current = current.next

Here’s what each line is doing:

• current = head starts your walk at the first node
• while current: keeps going until current becomes None
• print(current.val) uses the current node
• current = current.next moves forward one hop

If the list is 10 → 20 → 30 → 40, traversal visits those values in order. There is no skipping directly to 30 unless you follow 10 to 20, then 20 to 30.

That gives linked-list traversal:

• Time: O(n)
• Space: O(1) extra space because you only keep one pointer like current

This is a good place to connect to fast and slow pointers: almost every linked list trick is built on top of plain traversal plus careful pointer movement.

Insertion at the head

Head insertion is the happiest linked list operation. No shifting. No scanning. Just three steps:

1. create the new node
2. point new_node.next to the current head
3. move head to the new node

def insert_head(self, val):
    new_node = Node(val)
    new_node.next = self.head
    self.head = new_node

Suppose the list is 20 → 30 → 40, and you want 10 in front:

• make node 10
• set 10.next = 20
• update head = 10

Now the list is 10 → 20 → 30 → 40.

That’s O(1) time. You never look at the rest of the list. Compare that with arrays: remember how array insertion at index 0 required shifting every element? Linked lists avoid that because the structure is held together by pointers, not by physical position in a memory block.

Insertion in the middle

Middle insertion is where beginners first feel both the strength and the limitation of singly linked lists.

If you want to insert 30 into 10 → 20 → 40 → 50, you do not go to 40 first. You go to the node before the insertion point — 20.

Then you rewire in this order:

1. new_node.next = prev.next
2. prev.next = new_node

def insert_after(prev, val):
    if prev is None:
        return

    new_node = Node(val)
    new_node.next = prev.next
    prev.next = new_node

Why that order? Because if you overwrite prev.next too early, you lose the rest of the list.

Concrete example:

• original: 10 → 20 → 40 → 50
• prev is the node with value 20
• create 30
• point 30.next to 40
• change 20.next to 30

Result: 10 → 20 → 30 → 40 → 50

The full operation is:

• O(n) to find prev
• O(1) to insert once you’re there

And because the list is singly linked, you cannot go backward if you overshoot. That’s why interview solutions often say “find the previous node” instead of “find the insertion index.”

Deletion

Deletion is the same rewiring idea in reverse.

To delete a node in the middle, you usually find the node before it. If prev.next is the target, then deleting the target means:

def delete_after(prev):
    if prev is None or prev.next is None:
        return

    target = prev.next
    prev.next = target.next

Imagine the list 10 → 20 → 30 → 40 → 50, and you want to remove 30:

• find prev = 20
• target = 30
• set 20.next = 40

Now the chain from head skips over 30, so the effective list becomes 10 → 20 → 40 → 50.

Two important notes:

• Special case: if you’re deleting the head, there is no previous node. You simply do head = head.next.
• Memory management: in Python and Java, the garbage collector eventually reclaims the removed node once nothing points to it. In C/C++, you must free/delete that node yourself.

The costs are:

• O(n) to find the node before the target
• O(1) to perform the actual delete

The dummy-head trick

Head operations are annoying because they keep forcing a special case:

• “if deleting the first node…”
• “if inserting at position 0…”

The dummy-head trick fixes that. You create one extra node that always sits before the real list.

graph LR
  D["dummy"] --> N1["10"]
  N1 --> N2["20"]
  N2 --> N3["30"]
  N3 --> X["null"]

Now even the original head has a predecessor: the dummy node. That means insertions and deletions can work uniformly with prev.next.

def remove_value(head, target):
    dummy = Node(0, head)
    prev = dummy

    while prev.next and prev.next.val != target:
        prev = prev.next

    if prev.next:
        prev.next = prev.next.next

    return dummy.next

Notice how there’s no separate “delete the head” branch. If the first real node contains target, then prev is just the dummy node, and prev.next = prev.next.next still works.

This pattern shows up constantly in interviews because it removes edge-case clutter and makes your code easier to reason about.

Reversing a linked list

This is the linked list interview question.

If you can explain reversal clearly, you understand singly linked lists at a deep level.

The challenge is that every arrow currently points forward, but you want them all to point backward. The safe iterative solution uses three pointers:

• prev — the part you’ve already reversed
• curr — the node you’re currently processing
• next_node — the saved pointer to the unreversed remainder

def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

Let’s walk through 10 → 20 → 30 → 40 → 50.

Step 1: start

• prev = None
• curr = 10

Nothing has been reversed yet.

Step 2: process 10

• save next_node = 20
• flip 10.next = None
• move prev = 10
• move curr = 20

Now the reversed part is just 10 → null.

Step 3: process 20

• save next_node = 30
• flip 20.next = 10
• move prev = 20
• move curr = 30

Now the reversed part is 20 → 10 → null.

Step 4: keep repeating

Each iteration takes one node from the unreversed side and moves it to the front of the reversed side:

• after 30: 30 → 20 → 10
• after 40: 40 → 30 → 20 → 10
• after 50: 50 → 40 → 30 → 20 → 10

When curr becomes None, you’re done. At that point, prev is the new head, so you return it.

The crucial idea is: save next_node before changing curr.next. If you reverse the arrow first and forget to save the old next pointer, you cut yourself off from the rest of the list.

This iterative solution is:

• Time: O(n)
• Space: O(1)

Recursive reversal

There is also a recursive version that looks elegant:

def reverse_recursive(head):
    if head is None or head.next is None:
        return head

    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

It works by reversing the smaller list starting at head.next, then making the next node point back to head.

The tradeoff is space: recursion uses the call stack, so the extra space is O(n) instead of O(1). That is why the iterative three-pointer version is the standard interview answer.

Complexity comparison: arrays vs singly linked lists

Common mistakes

When to use linked lists vs arrays

Use linked lists when:

• you expect frequent insertions and deletions near known positions
• the size is hard to predict up front
• random indexing is not important
• you naturally think in terms of nodes and rewiring

Use arrays when:

• you need frequent random access like arr[5000]
• you want fast, cache-friendly iteration
• the data is mostly appended, scanned, or indexed
• you care about lower constant factors in real code

In modern production code, arrays/vectors/lists from the standard library are usually more common than hand-built linked lists. That is because contiguous memory is very friendly to CPUs. Linked lists still matter in specific places, though:

• LRU cache internals
• undo/redo systems
• polynomial arithmetic
• interview problems built around pointer reasoning

So the right lesson is not “linked lists are everywhere.” It’s “linked lists teach you how pointer-based structures behave.”

Practice problems

• Reverse Linked List (#206) - Easy
• Merge Two Sorted Lists (#21) - Easy
• Remove Nth Node From End of List (#19) - Medium
• Add Two Numbers (#2) - Medium
• Delete Node in a Linked List (#237) - Medium

Key takeaways

1. A singly linked list is a chain of nodes where each node stores a value and a pointer to the next node.
2. The head pointer is everything — lose it, and you lose access to the list.
3. Traversal and search are usually O(n) because you must walk node by node.
4. Insertion and deletion become cheap once you’re already at the right previous node.
5. The dummy-head trick makes many edge cases cleaner by guaranteeing every real node has a predecessor.
6. The standard reversal pattern is prev, curr, next_node; learn it until you can explain it out loud.

What’s next

Next, we’ll extend these ideas to doubly and circular linked lists — where nodes have both prev and next pointers, and the last node can loop back to the first.