【2.3】链表

• 通过指针把它的一串存储结点链接成一个链
• 存储结点由两部分组成:
• 数据域 + 指针域(后继地址)

一、分类

(根据链接方式和指针多寡)

二、单链表(singly linked list)

2.1 简单的单链表

• 整个单链表: head
• 第一个结点: head
• 空表判断: head == NULL
• 当前结点 a1:curr

2.2 带头结点的单链表

• 整个单链表: head
• 第一个结点: head->next，head ≠ NULL
• 空表判断: head->next == NULL ；当前结点a1:fence->next (curr 隐含)

2.3 单链表的结点类型

2.4 单链表类定义

2.5 查找单链表中第 i 个结点

2.6 单链表的插入

2.7 单链表插入算法

2.8 单链表的删除

从链表中删除结点 x

1. 用 p 指向元素 x 的结点的前驱结点
2. 删除元素为 x 的结点
3. 释放 x 占据的空间

2.9 单链表删除算法

2.10 单链表上运算的分析

对一个结点操作，必先找到它，即用一个指针指 向它

找单链表中任一结点，都必须从第一个点开始

p = head;
while (没有到达) p = p->next;

单链表的时间复杂度 𝑂(𝑛）

• 定位:𝑂(𝑛)
• 插入:𝑂(𝑛) +𝑂(1)
• 删除:𝑂(𝑛) +𝑂(1)

三、双链表(double linked list)

为弥补单链表的不足,而产生双链表

• 单链表的 next 字段仅仅指向后继结点，不能有效地找 到前驱, 反之亦然
• 增加一个指向前驱的指针

3.1 双链表及其结点类型的说明

3.2 双链表插入过程(注意顺序)

3.3 删除过程

三、循环链表 (circularly linked list)

将单链表或者双链表的头尾结点链接起来，就是一个循 环链表

不增加额外存储花销，却给不少操作带来了方便

• 从循环表中任一结点出发，都能访问到表中其他结点

四、讨论

4.1 链表的边界条件

• 几个特殊点的处理
• 头指针处理
• 非循环链表尾结点的指针域保持为 NULL
• 循环链表尾结点的指针回指头结点
• 链表处理
• 空链表的特殊处理
• 插入或删除结点时指针勾链的顺序
• 指针移动的正确性： 插入| 查找或遍历

4.2 思考

• 带表头与不带表头的单链表?
• 处理链表需要注意的问题?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟