Linked Structures

Insert at Head

Insert a new first node by pointing it at the old head and then moving the head pointer.

Algorithm

Basic Implementation

Basic.java 
public class Basic {
    static class Node {
        int value;
        Node next;
        Node(int value) { this.value = value; }
        Node(int value, Node next) { this.value = value; this.next = next; }
    }
    static String render(Node head) {
        StringBuilder out = new StringBuilder();
        Node cursor = head;
        while (cursor != null) {
            if (out.length() > 0) out.append(" -> ");
            out.append(cursor.value);
            cursor = cursor.next;
        }
        return out.append(" -> null").toString();
    }
    public static void main(String[] args) {
        Node head = new Node(20, new Node(30));
        Node newHead = new Node(10);
        newHead.next = head;
        head = newHead;
        System.out.println(render(head));
    }
}

Head insertion changes only two references: the new node points at the old head, then head moves to the new node.

Step 1 - Old first node

Before insertion, head points at node(20).

Original chain before inserting 10 at the head.headnode(20)node(30)null

Step 2 - New node links to old head

Set new.next to the old first node before moving head.

node(10) is allocated and points at the old head node(20).headnode(10)newnode(20)old headnode(30)null

Step 3 - Head moves to the new node

The final chain has 10 first: 10 -> 20 -> 30 -> null.

After insertion, head points at node(10).headnode(10)node(20)node(30)null

Complexity

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

Implementation notes

  • Keep the explicit node and pointer/reference operations; array shortcuts hide the linked-list state this lesson is meant to replay.
  • The final output prints the chain in a deterministic a -> b -> null form for cross-language comparison.
old head The previous first node becomes the second node.
constant-time insert Only the new node and head pointer change.