A chain of somewheres.

// "Linked list" without any malloc per node. The arena owns the
// storage; indices play the role of pointers.
//
// This is how serious systems do it: the OS scheduler, the Linux
// kernel's task_struct list, ECS game engines, lock-free queues.
struct Arena {
    nodes: Vec<Node>,
}

#[derive(Clone, Copy)]
struct NodeId(usize);

struct Node {
    value: i32,
    next: Option<NodeId>,
}

impl Arena {
    fn push(&mut self, value: i32, after: Option<NodeId>) -> NodeId {
        let id = NodeId(self.nodes.len());
        self.nodes.push(Node { value, next: None });
        if let Some(prev) = after {
            self.nodes[id.0].next = self.nodes[prev.0].next;
            self.nodes[prev.0].next = Some(id);
        }
        id
    }
}

// Three reasons this layout is usually faster than the heap version:
//  1. One contiguous Vec: far better cache behaviour on iteration.
//  2. One allocation amortised, not one per node.
//  3. Indices are 32-bit; pointers are 64-bit. Half the metadata.

#include <stdint.h>

// Same idea in C: nodes live in one array, "pointers" are 32-bit indices.
#define ARENA_CAP 1024
#define NIL UINT32_MAX

typedef struct {
    int      value;
    uint32_t next;       // index into arena, or NIL
} ANode;

static ANode    arena[ARENA_CAP];
static uint32_t arena_len = 0;

uint32_t a_alloc(int value, uint32_t after) {
    uint32_t id = arena_len++;
    arena[id].value = value;
    arena[id].next  = NIL;
    if (after != NIL) {
        arena[id].next     = arena[after].next;
        arena[after].next  = id;
    }
    return id;
}

use std::collections::HashMap;

/* Each block is a linked list node. */
struct Block {
    header:       BlockHeader,
    transactions: Vec<Transaction>,
}

struct BlockHeader {
    version:     u32,
    prev_hash:   [u8; 32], // the linked list pointer
    merkle_root: [u8; 32],
    timestamp:   u32,
    bits:        u32,
    nonce:       u32,
}

/* The blockchain: a hash map for O(1) lookup
 * plus a linked list structure via prev_hash. */
struct Blockchain {
    blocks: HashMap<[u8; 32], Block>,
    tip:    [u8; 32],
}

impl Blockchain {
    fn walk_backwards(&self) -> Vec<&Block> {
        let mut chain  = Vec::new();
        let mut cursor = Some(self.tip);
        let genesis    = [0u8; 32];

        while let Some(hash) = cursor {
            // follow the prev_hash pointer,
            // same as node = node.next in a regular list
            match self.blocks.get(&hash) {
                None        => break,
                Some(block) => {
                    chain.push(block);
                    let ph = block.header.prev_hash;
                    cursor = if ph == genesis {
                        None           // genesis: end of chain
                    } else {
                        Some(ph)       // follow the pointer
                    };
                }
            }
        }
        chain
        // Rust: prev_hash is a [u8; 32] value type,
        // not a raw pointer. HashMap returns Option:
        // no null dereference possible, safe to any depth.
    }

    /* Verify chain integrity: every prev_hash must
     * resolve to a real block in the map.
     * This is what every Bitcoin node does on startup. */
    fn verify_integrity(&self) -> bool {
        for (_stored_hash, block) in &self.blocks {
            let ph = &block.header.prev_hash;
            if *ph == [0u8; 32] { continue; } // genesis
            match self.blocks.get(ph) {
                None    => return false, // broken link
                Some(_) => { /* link valid, continue */ }
            }
        }
        true
    }
}

/* The Bitcoin blockchain vs a memory linked list:
 *
 *   Regular list:  node->next  = memory address
 *   Blockchain:    block.prev  = SHA-256d(prev_header)
 *
 *   Regular list:  change node -> only breaks if
 *                  the parent checks pointer validity
 *   Blockchain:    change block -> hash changes ->
 *                  every later block's prev_hash
 *                  fails verification ->
 *                  the whole network rejects the fork
 *
 * The list is singly linked.
 * You walk it backwards: tip -> ... -> genesis.
 * Inserts happen only at the tip (mining a block).
 * Deletes never happen (immutable append-only).
 *
 * A linked list, made tamper-evident by replacing
 * memory addresses with cryptographic hashes.
 * That is the entire blockchain data structure. */

#include <stdint.h>
#include <string.h>

/* A Bitcoin block header - 80 bytes.
 * The linked list node of the blockchain. */
typedef struct __attribute__((packed)) {
    uint32_t version;
    uint8_t  prev_hash[32]; /* the next pointer */
                            /* except it is a hash */
                            /* not a memory address */
    uint8_t  merkle_root[32];
    uint32_t timestamp;
    uint32_t bits;
    uint32_t nonce;
} BlockHeader;

/* Walk the blockchain backwards from tip to genesis.
 * Same shape as walking a singly linked list.
 * Except prev_hash is looked up in a database
 * not dereferenced as a pointer. */
void walk_chain(
    const BlockHeader *tip,
    BlockHeader *(*find_by_hash)(const uint8_t[32])
) {
    const BlockHeader *current = tip;
    uint8_t genesis[32] = {0}; /* all-zero hash */

    while (current != NULL) {
        /* process block... */
        if (memcmp(current->prev_hash,
                   genesis, 32) == 0) break;
        /* follow the "pointer" */
        current = find_by_hash(current->prev_hash);
        /* in a regular linked list:
         *   current = current->next;
         * here:
         *   current = database_lookup(current->prev_hash);
         * same shape. different mechanism.
         * same O(n) to walk the whole chain. */
    }
}

/* The linked list property that matters:
 * change any block -> its hash changes ->
 * the next block's prev_hash no longer matches ->
 * the chain is broken from that point onward ->
 * every node rejects it.
 *
 * This is why you cannot rewrite Bitcoin history.
 * Not because of trust.
 * Because of linked list pointer integrity.
 * Enforced by SHA-256 instead of the OS. */