Insert at Head - Rust DSA

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

Algorithm

Basic Implementation

basic.rs

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

fn node(value: i32, next: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { value, next }))
}

fn render(head: &Option<Box<Node>>) -> String {
    let mut parts: Vec<String> = Vec::new();
    let mut cursor = head.as_ref();
    while let Some(node) = cursor {
        parts.push(node.value.to_string());
        cursor = node.next.as_ref();
    }
    parts.join(" -> ") + " -> null"
}

fn delete_value(head: Option<Box<Node>>, target: i32) -> Option<Box<Node>> {
    match head {
        Some(mut n) => {
            if n.value == target {
                n.next
            } else {
                n.next = delete_value(n.next, target);
                Some(n)
            }
        }
        None => None,
    }
}

fn main() {
    let mut head = node(20, node(30, None));
    let mut new_head = Box::new(Node { value: 10, next: None });
    new_head.next = head;
    head = Some(new_head);
    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).

Step 2 - New node links to old head

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

Step 3 - Head moves to the new node

The final chain has 10 first: 10 -> 20 -> 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.