Linked List - Bash DSA

Walk a singly linked list once, rewiring each node's next to point at the previous node. Returns the new head, which is the old tail.

Algorithm

Canonical input is the chain 1 -> 2 -> 3 -> 4 -> 5 -> null built through five add_node calls.

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
node_value=()
node_next=()
last_idx=-1

add_node() {
	local value=$1
	local next_idx=$2
	local idx=${#node_value[@]}
	node_value[idx]=$value
	node_next[idx]=$next_idx
	last_idx=$idx
}

add_node 5 -1;   n5=$last_idx
add_node 4 "$n5"; n4=$last_idx
add_node 3 "$n4"; n3=$last_idx
add_node 2 "$n3"; n2=$last_idx
add_node 1 "$n2"; head=$last_idx

prev=-1
cursor=$head
while [ "$cursor" -ne -1 ]; do
	next_idx=${node_next[cursor]}
	node_next[cursor]=$prev
	prev=$cursor
	cursor=$next_idx
done
head=$prev
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(1)

Implementation notes

Bash: command substitution $(add_node ...) runs in a subshell, so the add_node function mutates the node_value / node_next globals directly and reports the new index through a last_idx global. The caller pattern add_node ...; n_k=$last_idx keeps the arena consistent without leaning on Bash 5 namerefs.
-1 is the null sentinel; the rewire loop runs while [ "$cursor" -ne -1 ].
The replay shows each step's cursor, prev, saved next_idx, and a one-line list view that updates as nodes flip.

three-pointer rewire Keep `prev`, `cursor`, and `next_idx` integers. At each step: save `next_idx`, flip `cursor.next = prev`, then advance `prev = cursor` and `cursor = next_idx`.

tail becomes head After the loop, `prev` is the new head. The reversed chain prints as `5 -> 4 -> 3 -> 2 -> 1 -> null`.