数据结构与算法（Python语言版）课件 第11章 链表

第11章链表2025/6/111链表的特点单链表双链表链式栈

11.1链表的特点2025/6/112链表是由若干个节点组成，这些节点形成的逻辑结构是线性结构，节点的存储结构是链式存储，即节点的物理地址不必是依次相邻的。对于单链表，每个结点含有一个数据，并含有下一个节点的地址。对于双链表，每个节点含有一个数据，并含有上一个节点的地址和下一个结点的地址2025/6/11311.1链表的特点图示意的是有5个节点的双链表（省略了上一个节点的地址箭头示意）。注意，链表的节点序号是从0开始，每个节点的序号等于它前面的节点的个数。链表中的节点的物理地址不必是相邻的，因此，链表的优点是不需要占用一块连续的内存存储空间。2025/6/11411.1链表的特点

●删除头、尾节点的复杂度O(1)删除前面所示意5个节点的的链表的头节点(大象-节点)后的示意图。2025/6/1155.1链表的特点

●查询头、尾节点的复杂度O(1)查询狮子和鳄鱼的时间复杂度都是O(1)。2025/6/11611.1链表的特点

●链表添加头、尾节点的复杂度O(1)链表添加新的尾节点（企鹅-节点），根据链表保存的尾节点的地址，找到尾节点（鳄鱼-节点），将这个尾节点中的下一个节点的引用设置成新添加的节点（企鹅-节点）的地址，将添加的新节点（企鹅-节点）中的上一个节点的地址设置成鳄鱼-节点的地址，将添加的新节点（企鹅-节点）中的下一个节点的地址设置成null，即让新添加的节点成为尾结点。2025/6/11711.1链表的特点●查询中间节点的时间复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存地址链接在一起。

2025/6/11811.1链表的特点●删除中间节点的复杂度O(n)链表的节点的物理地址不是相邻的，节点通过互相保存地址链接在一起。

2025/6/11911.1链表的特点●插入中间节点的复杂度O(n)

插入新节点后，新链表中的节点序号按新的链表长度从0开始排列。11.2单链表2025/6/1110Python没有提供实现链表的类（这一点与C++和Java不同），如果用户程序需要链表就需要编写创建链表的类。2025/6/111111.2单链表ch11_1.py例1单链表与约瑟夫问题ch11_1.py中的LinkedData类是单链表数据结构，提供的方法也只是11.1节的叙述中提到的最基本的操作，例如添加头节点、删除头节点、返回头节点中的数据等。但特点是LinkedData类有一个旋转链表的方法，本例用该LinkedData类提供的此方法可以很容易地解决约瑟夫问题.

11.3双链表2025/6/1112双链表的每个节点含有一个数据，并含有上一个节点的地址和下一个结点的地址，比单链表有更好的效率。例如按索引查询节点时，双链表的效率是单链表的二倍。Python的collections模块中的deque类（见第7章的7.2节）是基于双链表的双端队列，可以在队列的两端进行高效的插入和删除操作。2025/6/111311.3双链表例子18双链表与淘汰赛ch11_2.py

2025/6/111411.3双链表例子18双链表与淘汰赛ch11_2.py（如果剩下1个队，相当于该轮空、自动晋级）11.4链式栈2025/6/1115

2025/6/111611.4链式栈例子18链式栈与回文串ch11_3.pych11_3.py