Build a Singly Linked List

Construct a singly linked list by allocating one node per value and chaining next references. Establishes the node + head + tail model used by every later linked-list lesson.

Algorithm

Canonical input [10, 20, 30, 40] builds the chain head -> 10 -> 20 -> 30 -> 40 -> nil with one node appended per step.

Basic Implementation

basic.rs

struct ListNode {
	value: i32,
	next: Option<usize>,
}

fn main() {
	let values = [10, 20, 30, 40];
	let mut nodes: Vec<ListNode> = Vec::new();
	let mut head: Option<usize> = None;
	let mut tail: Option<usize> = None;
	for i in 0..values.len() {
		let idx = nodes.len();
		nodes.push(ListNode { value: values[i], next: None });
		if head.is_none() {
			head = Some(idx);
		} else {
			let t = tail.unwrap();
			nodes[t].next = Some(idx);
		}
		tail = Some(idx);
	}
	let mut cur = head;
	while let Some(idx) = cur {
		print!("{} -> ", nodes[idx].value);
		cur = nodes[idx].next;
	}
	println!("nil");
}

Complexity

Time: O(n) with a tail pointer
Space: O(n) for the chain

Implementation notes

Rust: a small struct ListNode { value: i32, next: Option<usize> } stored in a Vec<ListNode> arena. Option<usize> is the explicit "end-of-list" sentinel and lets the head / tail pointers update the chain without unsafe pointer juggling or Rc<RefCell<...>> borrowing dances.
The replay never shows runtime addresses; nodes are labelled node(<value>) and the chain view is rendered as 10 -> 20 -> ... -> nil.
The arena is dropped at scope exit, so the build step stays focused on wiring without an explicit free walk.

node chain Each `ListNode` carries an `i32 value` and an `Option<usize> next` index into the node arena.