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 -> null with one node appended per step.

Basic Implementation

basic.lua

local values = {10, 20, 30, 40}
local nodes = {}
local head = -1
local tail = -1
local i = 1
while i <= #values do
	local idx = #nodes + 1
	nodes[idx] = {value = values[i], next_idx = -1}
	if head == -1 then
		head = idx
	else
		nodes[tail].next_idx = idx
	end
	tail = idx
	i = i + 1
end
local cur = head
while cur ~= -1 do
	io.write(tostring(nodes[cur].value) .. " -> ")
	cur = nodes[cur].next_idx
end
io.write("null\n")

Complexity

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

Implementation notes

Lua: a tiny table node {value = ..., next_idx = ...} stored in a plain integer-keyed nodes 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 metatables or a recursive table reference graph.
The replay never shows runtime references; nodes are labelled node(<value>) and the chain view is rendered as 10 -> 20 -> ... -> null.
The arena is collected by Lua's GC at scope exit, so the build step stays focused on wiring without an explicit free walk.

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