Linked Structures

Linked List

Build

Build a singly linked list by appending nodes one at a time, tracking head and tail indices so each append stays O(1). Then traverse from head to print the chain.

Algorithm

Basic Implementation

basic.sh 
#!/usr/bin/env bash
set -euo pipefail
values=(10 20 30 40)
node_value=()
node_next=()
head=-1
tail=-1
i=0
while [ "$i" -lt "${#values[@]}" ]; do
	idx=${#node_value[@]}
	node_value[idx]=${values[i]}
	node_next[idx]=-1
	if [ "$head" -eq -1 ]; then
		head=$idx
	else
		node_next[tail]=$idx
	fi
	tail=$idx
	i=$((i + 1))
done
cur=$head
while [ "$cur" -ne -1 ]; do
	printf '%d -> ' "${node_value[cur]}"
	cur=${node_next[cur]}
done
printf 'null\n'

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.

Start of the chain: head and tail both reach node(10).headtailnode(10)null

Step 2 - Append through 30

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

After appending 20 and 30: tail names node(30).headnode(10)node(20)node(30)tailnull

Step 3 - Final chain

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

Complete linked list for [10, 20, 30, 40].headnode(10)node(20)node(30)node(40)tailnull

Complexity

  • Time: O(n)
  • Space: O(n)

Implementation notes

  • Bash: parallel arrays node_value and node_next indexed by integer (with -1 as the sentinel) keep the structural moves visible without leaning on Bash 5's namerefs or external linked data structures. The replay reads pure integer indices and literal node(value) strings instead of internal references.
  • head=-1 and tail=-1 use -1 as the null sentinel so the branch test is a plain integer compare ([ "$head" -eq -1 ]).
  • The traversal step uses printf '%d -> ' followed by a null terminator so the chain prints with the same value -> value -> null shape as the language-neutral lesson spec.
arena of nodes A `node_value` array and a `node_next` array store the list as parallel arrays of values and successor indices. `-1` is the sentinel for "no node".
head and tail pointers `head` and `tail` are integer indices into the arena. The first append sets `head`; every later append patches the previous `tail`'s `next_idx` to the new node.