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.rb

ListNode = Struct.new(:value, :next_idx)

values = [10, 20, 30, 40]
nodes = []
head = -1
tail = -1
i = 0
while i < values.length
	idx = nodes.length
	nodes << ListNode.new(values[i], -1)
	if head == -1
		head = idx
	else
		nodes[tail].next_idx = idx
	end
	tail = idx
	i = i + 1
end
cur = head
while cur != -1
	print "#{nodes[cur].value} -> "
	cur = nodes[cur].next_idx
end
puts "nil"

Complexity

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

Implementation notes

Ruby: a tiny ListNode = Struct.new(:value, :next_idx) stored in a plain Array arena. The integer next_idx field with -1 as the sentinel is the explicit "end-of-list" marker and lets the head / tail pointers update the chain without leaning on a recursive class reference graph or Ruby's Object#object_id.
The field is named next_idx rather than next because next is a Ruby keyword in iteration blocks; this keeps the struct usable without escaping or shadowing.
The replay never shows runtime references; nodes are labelled node(<value>) and the chain view is rendered as 10 -> 20 -> ... -> nil.
The arena is collected by Ruby's GC at scope exit, so the build step stays focused on wiring without an explicit free walk.

node chain Each `ListNode` carries an `Integer value` and an `Integer next_idx` into the node arena (`-1` is the end-of-list sentinel).