3. 链表

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

单链表

3.1 单向链表

单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点，而最后一个节点的链接域则指向一个空值。

单向链表

1. 表元素域elem用来存放具体的数据。

2. 链接域next用来存放下一个节点的位置（python中的标识）

3. 变量p指向链表的头结点（首节点）的位置，从p出发能找到表中的任意节点。

3.1.1 节点实现

节点实现

3.1.2 单链表的操作

is_empty() 链表是否为空

length() 链表长度

travel() 遍历整个链表

add(item) 链表头部添加元素

append(item) 链表尾部添加元素

insert(pos,item) 指定位置添加元素

remove(item) 删除节点

search(item) 查找节点是否存在

3.1.3 单链表的实现

单链表1

头部添加元素

头部添加元素示意图

头部添加元素代码

尾部添加元素

尾部添加元素代码

指定位置添加元素

单链表指定位置添加元素示意图

单链表指定位置添加元素代码

删除节点

单链表删除节点示意图

单链表删除节点及查找节点代码

3.1.4 链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大，但对于存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

链表和顺序表的比较

注意虽然表面看起来复杂度都是O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作，只能通过拷贝和覆盖的方法进行。