Singly Linked List

Intuition

Think of a treasure hunt. Each clue card tells you something and also tells you where the next card is hidden. You cannot jump straight to clue number seven; you have to follow cards one through six. But if the organiser wants to add a new clue between cards three and four, nobody has to move any cards around. They just rewrite card three to point at the new card, and make the new card point at card four.

A singly linked list is that chain of cards. Each node holds a value and a next reference. The list itself only remembers the head, the first node. The last node's next is null. Compared with an array you give up instant indexing (no list[7] in O(1)), and in return you gain cheap insertion and deletion anywhere you already have a pointer, plus the ability to grow without ever resizing or copying.

How it works step by step

Every operation is a small variation on walking the chain with a cur (or prev) pointer and then changing at most two next fields.

1. Insert at head: create a node, set node.next = head, then head = node. O(1).
2. Insert after a node `prev`: set node.next = prev.next first, then prev.next = node. Reversing the order makes prev.next point at the new node before you saved the rest of the list, and the rest is lost.
3. Insert at index i: walk i - 1 steps from the head to find prev, then do the insert-after step.
4. Delete by value: walk with prev until prev.next holds the value, then bypass it with prev.next = prev.next.next. A dummy node in front of the head means deleting the head needs no special case.
5. Search: walk from the head, comparing each value, until you find it or reach null.

Dry run

Start with the list 3 -> 7 -> 9 and apply five operations. The arrows show next pointers.

In step 2, node 7 is not destroyed explicitly. Nothing points to it any more, so in Java or Python the garbage collector reclaims it. In C or C++ you would have to free it yourself, after saving any pointer you still need.

Code

public class SinglyLinkedList {
    private static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    private Node head;
    private int size;

    public void addFirst(int val) {
        Node n = new Node(val);
        n.next = head;
        head = n;
        size++;
    }

    public void addLast(int val) {
        Node n = new Node(val);
        if (head == null) {
            head = n;
        } else {
            Node cur = head;
            while (cur.next != null) cur = cur.next;
            cur.next = n;
        }
        size++;
    }

    /** Inserts val so that it ends up at position index (0-based). */
    public void insertAt(int index, int val) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException("index " + index);
        if (index == 0) { addFirst(val); return; }
        Node prev = head;
        for (int i = 0; i < index - 1; i++) prev = prev.next;
        Node n = new Node(val);
        n.next = prev.next; // 1. new node grabs the rest of the list
        prev.next = n;      // 2. predecessor points at the new node
        size++;
    }

    /** Removes the first node holding val. Returns true if one was removed. */
    public boolean remove(int val) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node prev = dummy;
        while (prev.next != null && prev.next.val != val) prev = prev.next;
        if (prev.next == null) return false;
        prev.next = prev.next.next; // bypass the node
        head = dummy.next;          // head changes if we removed the first node
        size--;
        return true;
    }

    public int indexOf(int val) {
        int i = 0;
        for (Node cur = head; cur != null; cur = cur.next, i++) {
            if (cur.val == val) return i;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head; cur != null; cur = cur.next) sb.append(cur.val).append(" -> ");
        return sb.append("null").toString();
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(3); list.addLast(7); list.addLast(9);
        list.insertAt(1, 5);
        list.remove(7);
        list.addFirst(1);
        System.out.println(list + "  indexOf(9) = " + list.indexOf(9));
    }
}

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


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

    def add_first(self, val):
        self.head = Node(val, self.head)
        self.size += 1

    def add_last(self, val):
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1

    def insert_at(self, index, val):
        if not 0 <= index <= self.size:
            raise IndexError(index)
        if index == 0:
            self.add_first(val)
            return
        prev = self.head
        for _ in range(index - 1):
            prev = prev.next
        prev.next = Node(val, prev.next)  # new node takes prev.next first
        self.size += 1

    def remove(self, val):
        dummy = Node(0, self.head)
        prev = dummy
        while prev.next and prev.next.val != val:
            prev = prev.next
        if prev.next is None:
            return False
        prev.next = prev.next.next
        self.head = dummy.next
        self.size -= 1
        return True

    def index_of(self, val):
        for i, v in enumerate(self):
            if v == val:
                return i
        return -1

    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.val
            cur = cur.next


lst = SinglyLinkedList()
for x in (3, 7, 9):
    lst.add_last(x)
lst.insert_at(1, 5)
lst.remove(7)
lst.add_first(1)
print(list(lst), lst.index_of(9))  # [1, 3, 5, 9] 3

Time and space complexity

The rewiring itself is always constant time; what costs O(n) is finding the spot, because the only way to reach node i is to follow i pointers. Keeping a tail reference makes appending O(1), which is how linked-list queues work. Deleting the tail stays O(n), though, since you still need the node before it.

Edge cases

• Empty list: head is null; search returns -1, delete returns false, insert at 0 becomes the head.
• Deleting the head: handled by the dummy node, or by an explicit head = head.next branch.
• Deleting the only node: the list must end with head = null (and tail = null if you keep one).
• Insert at index size: equivalent to appending at the tail.
• Index out of range: validate before walking, or you will dereference null mid-walk.
• Duplicate values: decide whether remove deletes the first match or all of them.

Common mistakes

• Losing the next pointer. Writing prev.next = node before node.next = prev.next leaves the new node pointing at itself and orphans everything after it. Always save the old link first.
• Dereferencing null. Loops like while (cur.next.val != val) crash at the end of the list. Check cur.next != null first.
• Moving the head while traversing. Using head = head.next to walk the list destroys it. Walk with a separate cur.
• Forgetting to update `head` after deleting or inserting at position 0.
• Not updating `tail` and `size` in implementations that track them; they silently drift out of sync.
• Walking one step too far. To insert at index i you need the node at i - 1, not at i.

Variations and when to use it

A tail pointer makes the list a perfect O(1) queue. A circular list links the last node back to the head, useful for round-robin scheduling. A doubly linked list adds a prev pointer so you can delete any node in O(1) and walk backwards, at the cost of extra memory per node. Many classic interview tricks are built on singly linked lists: reversing with three pointers, finding the middle with slow and fast pointers, cycle detection with Floyd's algorithm, and merging two sorted lists.

Use a singly linked list when you mostly insert or remove at the front, when you need a stack or queue that never resizes, or when an interview problem simply hands you a ListNode. Prefer an array or ArrayList when you need random access or care about cache performance; contiguous memory is much faster to scan than nodes scattered across the heap.

Related LeetCode problems

• #206 Reverse Linked List — rewire each next backwards while saving the old next first.
• #328 Odd Even Linked List — maintain two chains and splice the even chain after the odd one.
• #2095 Delete the Middle Node of a Linked List — slow and fast pointers find the node before the middle, then bypass.
• #2130 Maximum Twin Sum of a Linked List — find the middle, reverse the second half, then walk both halves together.
• #203 Remove Linked List Elements — the dummy-node delete loop, removing every match.
• #19 Remove Nth Node From End of List — a gap of n between two pointers locates the predecessor in one pass.
• #21 Merge Two Sorted Lists — splice nodes from two lists onto a dummy tail.
• #141 Linked List Cycle — fast pointer moves two steps, slow moves one; they meet only if there is a cycle.

FAQ