数据结构学习笔记（2）——链表

机械工业出版社《数据结构与算法——Python语言实现》学习笔记。
绘图工具：ProcessOn

1 链表

主要介绍链表的数据结构及方法，省略详细实现。

1.1 单向链表

1.1.1 结构

要维护的数据结构：

• Node类：包含元素成员和指针域成员
• head指针：保存指向头节点的引用
• tail指针：保存指向尾节点的引用
• size：保存节点长度

1.1.2 单向链表头部插入元素

Algorithm add_first(L, e):
    newest = Node(e) #创建新节点
    newest.next = L.head #连接
    L.head = newest #更新head指针
    L.size = L.size + 1 #更新链表长度

1.1.3 单向链表尾部插入元素

Algorithm add_last(L, e):
    newest = Node(e) #创建新节点
    newest.next = None #新节点的next要设为None
    L.tail.next = newest #连接
    L.tail = newest #更新tail指针
    L.size = L.size + 1 #更新链表长度

1.1.4 从单向链表中删除元素

单向链表中想删除元素必须从头开始遍历，找到要删除节点的前一个节点，因此 删除尾部元素需要遍历整个链表 。
删除头部元素：

Algorithm add_first(L, e):
    if L.head is None then
        Indicate an error:the list is empty.
    L.head = L.next #更新head指针
    L.size = L.size - 1 #更新链表长度

1.2 循环链表

1.2.1 结构

一个循环链表可能并没有开始或者结束节点，但是必须为一个特定的节点维护一个引用（如上图的current），这样才能使用该链表

1.3 双向链表

1.3.1 结构

在单向链表中提到，由于单向链表的不对称性，删除尾部元素需要遍历整个链表，为了弥补这个缺陷，引入双向链表的概念：

要维护的数据结构：

• Node类：包含元素成员，pre前指针和next后指针
• header头节点，也称为头哨兵
• tailer尾节点，也称为尾哨兵
• size：保存节点长度

使用哨兵的好处：使除了哨兵之外的所有节点都处于两个节点之间，因此可以使用同样的方法处理所有节点的插入/删除操作。

1.3.2 添加节点操作

1.3.3 删除节点操作

1.4 位置链表

到目前为止介绍的链表都有一个共同的缺点：每个节点都没有索引，因此很难直接定位到序列中的某一个元素，然而，数组中标记位置的整型索引放到链表中并不适用，因此，我们定义了一个 含位置信息的列表ADT 和一个更简单的 位置 抽象数据类型，来描述列表中的某个位置。 改变列表的其他位置不会影响位置p。

位置实例是一个简单的对象，只支持以下方法：

• p.element(): 返回存储在位置p的元素。

位置列表ADT中，需要增加列表L所支持的访问器方法：

• L.first(): 返回L中第一个元素的位置。如果L为空，则返回None。
• L.last(): 返回L中最后一个元素的位置。如果L为空，则返回None。
• L.before§: 返回L中p紧邻的前面元素的位置。如果p为第一个位置，则返回None。
• L.before§: 返回L中p紧邻的后面元素的位置。如果p为最后一个位置，则返回None。
• L.is_empty(): 如果L列表不包含任何元素，返回True。
• len(L): 返回列表元素的个数。
• iter(L): 返回列表元素的前向迭代器。

位置列表ADT中，需要增加列表L所支持的更新方法：

• L.add_first(e): 在L的前面插入新元素e，返回新元素的位置。
• L.add_last(e): 在L的后面插入新元素e，返回新元素的位置。
• L.add_before(p,e): 在L中位置p之前插入一个新元素e，返回新元素的位置。
• L.add_after(p,e): 在L中位置p之后插入一个新元素e，返回新元素的位置。
• L.replace(p,e): 用元素e取代位置p处的元素，返回之前p位置处的元素。
• L.delete§: 删除并返回L中位置p处的元素，取消该位置。

2 基于链表的序列与基于数组的序列的对比

项目	基于数组的序列	基于链表的序列
访问元素	基于整数索引的时间复杂度为O(1)的访问方法	定位第k个元素要从起始位置或结束位置开始遍历链表
基本操作复杂度	较为简单（新索引计算、整数增量、在数组中为元素存储引用）	较为复杂（节点实例化、节点链接、整数增量）
存储比例	较少（对象引用）	较多（对象引用、链接各个节点的引用）
时间界限	动态数组扩张和收缩时存在“摊销”	为操作提供最坏情况的时间界限
插入/删除操作效率	在序列中间进行插入/删除操作代价较大（要循环替换所有后续元素）	在任意位置插入/删除操作的时间复杂度都为O(1)