3. Linked Lists

🧸 ELI5: Instead of an egg carton, imagine a treasure hunt. Each clue (node) tells you two things: the treasure at this spot, and where to find the next clue. You can't jump straight to clue #5 — you must follow clue #1 → #2 → #3 → #4 → #5.

🌍 Real life: A conga line / train cars — each car is only connected to the one behind and in front. A scavenger hunt. Your browser history's "back" chain (kind of).

📝 Pseudocode:

node = { value, next }
head -> node(1) -> node(2) -> node(3) -> null

function printAll(head):
    current = head
    while current != null:
        print(current.value)
        current = current.next

🐹 Go:

package main

import "fmt"

type Node struct {
	Value int
	Next  *Node
}

func printAll(head *Node) {
	for cur := head; cur != nil; cur = cur.Next {
		fmt.Println(cur.Value)
	}
}

func main() {
	third := &Node{Value: 3}
	second := &Node{Value: 2, Next: third}
	first := &Node{Value: 1, Next: second}
	printAll(first) // 1, 2, 3
}

🇨 C (deep dive: real-life-c-guide.md §18.1) — this is the language linked lists were born in; a Node here is a malloc'd block plus a pointer, nothing more:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *node_new(int value, Node *next) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = next;
    return n;
}

void print_all(Node *head) {
    for (Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d\n", cur->value);
    }
}

void list_free(Node *head) {   // unlike Go, nothing frees this for you — Section 10.3
    while (head) { Node *next = head->next; free(head); head = next; }
}

int main(void) {
    Node *third = node_new(3, NULL);
    Node *second = node_new(2, third);
    Node *first = node_new(1, second);
    print_all(first); // 1, 2, 3
    list_free(first);
    return 0;
}

⏱️ Complexity: Access by position = O(n) (follow the clues one by one). Insert at the front = O(1) (just point to a new first clue) — much faster than an array's O(n) shift.