2.1 线性表的定义与特点

线性表的特点：

• 有序性：表中元素有先后次序。
• 一对一：除首元素外每个元素有且仅有一个直接前驱；除末元素外每个元素有且仅有一个直接后继。
• 有限性：元素个数有限；同质性：元素数据类型相同。

线性表的基本运算包括：初始化、求表长、按值查找、按位查找、插入、删除、输出、判空、销毁等。

2.2 顺序表（顺序存储）

设每个元素占 l 个存储单元，LOC(aᵢ)=LOC(a₁)+(i−1)×l。因此支持随机存取，按位查找的时间复杂度为 O(1)。

顺序表插入与删除

• 插入（在第 i 位插入）：需将第 i 至第 n 位元素后移一位，平均移动 n/2 次，时间复杂度 O(n)。
• 删除（删除第 i 位元素）：需将第 i+1 至第 n 位元素前移一位，平均移动 (n−1)/2 次，时间复杂度 O(n)。

typedef struct{
  ElemType data[MaxSize];
  int length;
} SqList;

// 在第 i 位（1≤i≤length+1）插入元素 e
int ListInsert(SqList &L, int i, ElemType e){
  if(i<1 || i>L.length+1) return 0;
  for(int j=L.length; j>=i; j--)
    L.data[j]=L.data[j-1];   // 后移
  L.data[i-1]=e;
  L.length++;
  return 1;
}

2.3 链表（链式存储）

链式存储不要求逻辑相邻的元素物理相邻，通过指针指示元素间的逻辑关系。每个结点 = 数据域 + 指针域。

1. 单链表

每个结点含一个指向后继的指针 next。head 为头指针，尾结点 next 为 NULL。顺序存取，不支持随机存取，按位查找 O(n)。

typedef struct LNode{
  ElemType data;
  struct LNode *next;
} LNode, *LinkList;

单链表插入结点（在 p 之后插入 s）的核心两步：

s->next = p->next;   // ① s 指向 p 的原后继
p->next = s;         // ② p 指向 s

2. 双链表

每个结点含 prior 和 next 两个指针，分别指向前驱和后继。插入删除需修改双向指针，但可双向遍历。

// 在 p 之后插入 s（四步）
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

3. 循环链表

将单链表尾结点的 next 指向头结点（或首元结点），形成环，称为循环单链表。判空条件由 head->next==head 决定，判表尾由 p->next==head 决定。双链表也可循环化。

2.4 顺序表与链表对比

2.5 静态链表

借助数组描述链表，结点中含有 data 与 cur（游标，存下一结点的数组下标）。以数组下标代替指针实现链式逻辑，又称游标实现法。

• 优点：在 不支持指针 的语言中实现链表；插入删除只需修改游标，无需移动元素。
• 缺点：需预先分配较大连续空间；仍存在表长上限。

2.6 单链表插入与删除动画

观察在 a2 与 a3 之间插入新结点 X，再删除 X 的完整指针变化过程。— 虚线 表示新建/将要建立的指针，— 红色 表示将被断开的指针。