链表是什么

数组是一整排连号的座位，内存里紧挨着，所以按下标能一步跳到。链表不一样：节点散落在内存各处，靠每个节点手里的一张「纸条」（指针）记着下一个节点在哪，串成一条线。

优点是插入删除只改几张纸条，不用像数组那样挪动一大片元素；缺点是想取第 $k$ 个只能从头顺着纸条一个个走，做不到一步到位。

struct Node {
    int val;      // 这个节点存的值
    Node* next;   // 指向下一个节点的指针（那张纸条）
};
Node* head;       // 头指针，抓住整条链的第一个节点

复杂度对比：链表按位置访问 $O(n)$、数组 $O(1)$；链表在已知位置插入删除 $O(1)$、数组 $O(n)$。

理解要点：链表不占用一段连续内存，它是一堆分散节点用指针连起来的逻辑序列。一旦丢了头指针，整条链就找不到了，所以 head 一定要保管好。信息学考试里链表常用来做栈、队列、邻接表和约瑟夫问题。