2.3.1 单链表：结点地址不连续，逻辑次序仍连续

单链表把元素分成数据域和指针域：

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

next 保存后继结点地址，最后一个结点的 next 为 NULL。结点可散落在内存中，链由指针维持，因此扩展容量灵活，却失去了按位随机访问。

带头结点与不带头结点必须分清。带头结点时，头指针指向一个不存放普通元素的哨兵；第一个数据结点是 head->next，空表条件是 head->next==NULL。不带头结点时，头指针直接指向第一个数据结点，空表是 head==NULL。头结点让首位插入、删除与中间位置使用同一套指针规则。

求第 $i$ 个元素必须从头沿链走 $i-1$ 步，时间 $O(n)$。若已持有某结点指针，在其后插入只改常数个指针，是 $O(1)$；若题目只给位序，还要先定位前驱，整体为 $O(n)$。

陪做：带头结点的链 H -> 4 -> 9 -> NULL。H 不是第 1 个元素，表长是 2；第 2 个数据结点需从 H 走两条 next 边。画图时用方框表示结点、箭头表示地址关系，不要把地址大小误当逻辑先后。

错解反馈：把 head==NULL 当所有带头链表的空表条件，会把已创建的空表误判；说链表“插入永远 $O(1)$”漏掉了定位前驱；把头指针与头结点混为一物，则无法解释指针变量和堆上结点的区别。

迁移练习：不带头结点的链表在首部插入 x 应怎样改指针？答案 new->next=head; head=new;，因此函数必须能更新调用者的头指针。独立验收：能分别画出两种空表和一个含两元素的状态，并写出第 $i$ 个结点的定位步数。