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

Basic Implementation

basic.scala

import scala.collection.mutable.ArrayBuffer

class ListNode(var value: Int, var next: Int)

object Main {
	def main(args: Array[String]): Unit = {
		val values = Array(10, 20, 30, 40)
		val nodes = ArrayBuffer.empty[ListNode]
		var head = -1
		var tail = -1
		for (i <- values.indices) {
			val idx = nodes.length
			nodes += new ListNode(values(i), -1)
			if (head == -1) {
				head = idx
			} else {
				nodes(tail).next = idx
			}
			tail = idx
		}
		var cur = head
		while (cur != -1) {
			print(s"${nodes(cur).value} -> ")
			cur = nodes(cur).next
		}
		println("nil")
	}
}

The canonical values [10, 20, 30, 40] become one node per value. The head pointer names the first node; the tail pointer names the last node appended.

Step 1 - First node

After appending 10, both head and tail point at the same node.

Step 2 - Append through 30

Each append changes the old tail's next pointer, then moves tail to the new node.

Step 3 - Final chain

Appending 40 gives the lesson's pinned chain: head -> 10 -> 20 -> 30 -> 40 -> null.

Complexity

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

Implementation notes

Scala: a tiny class ListNode(var value: Int, var next: Int) stored in a scala.collection.mutable.ArrayBuffer[ListNode] arena. The integer next 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 Scala's List cons-cell idiom or a case class recursive reference graph.
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 the JVM GC at scope exit, so the build step stays focused on wiring without an explicit free walk.

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