Linked List - Bash DSA

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

Canonical input values=(10 20 30 40) yields 10 -> 20 -> 30 -> 40 -> null.

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'

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.