Build a Linked List

Construct a singly linked list by appending one node at a time. The list is modeled as parallel (idx, val, next_idx) rows; the printed output follows the next_idx chain until it hits the null sentinel.

Algorithm

Canonical input values=(10 20 30 40) finishes after four appends; the printed list is 10 -> 20 -> 30 -> 40 -> null.

Basic Implementation

basic.sql

.mode list
.headers off
CREATE TABLE values_in(pos INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO values_in(pos, val) VALUES (0, 10), (1, 20), (2, 30), (3, 40);

CREATE TABLE node(idx INTEGER PRIMARY KEY, val INTEGER, next_idx INTEGER);
INSERT INTO node(idx, val, next_idx)
SELECT pos, val,
       CASE WHEN pos + 1 < (SELECT COUNT(*) FROM values_in)
            THEN pos + 1 ELSE NULL END
FROM values_in;

WITH RECURSIVE walk(idx, line) AS (
  SELECT idx, CAST(val AS TEXT) || ' -> '
  FROM node WHERE idx = 0
  UNION ALL
  SELECT node.idx, walk.line || CAST(node.val AS TEXT) || ' -> '
  FROM walk JOIN node ON node.idx = (SELECT next_idx FROM node WHERE idx = walk.idx)
  WHERE (SELECT next_idx FROM node WHERE idx = walk.idx) IS NOT NULL
)
SELECT line || 'null' FROM walk ORDER BY idx DESC LIMIT 1;

Complexity

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

Implementation notes

SQL: the input is staged in values_in(pos, val) so the INSERT INTO node projection can set each row's next_idx to pos + 1 (or NULL at the tail) in one statement. This mirrors the imperative "append" loop without leaning on triggers.
The traversal is a WITH RECURSIVE walk(idx, line) CTE that threads next_idx from 0 until it hits NULL. The accumulated line carries the printable "v -> " segments forward, and the final SELECT ... || 'null' adds the canonical sentinel suffix.
ORDER BY idx DESC LIMIT 1 picks the row produced after the longest walk; that row holds the complete "10 -> 20 -> 30 -> 40 -> null" line emitted by every other DSA book in the cohort.

tail append Each new node attaches to the previous tail via its `next_idx` pointer. The head row's `idx` stays fixed once written.

null sentinel The final node's `next_idx` is `NULL`, which prints as `null` at the end of the chain.