Python数据结构之链表详解 _链表

0. 学习目标在顺序存储方式中，根据数据元素的序号就可随机存取表中任何一个元素，但同时在插入和删除运算需要移动大量的元素，造成算法效率较低。解决此缺陷的一个办法是：对线性表采用链式存储方式。在链表存储方式中，在逻辑上相邻的数据元素在存储空间中不一定相邻，数据元素的逻辑次序是通过链表中指针链接实现的。本节将介绍链式存储结构的特点以及各种基本操作的实现。通过本节学习，应掌握以下内容：
线性表的链式存储及实现方法
链表基本操作的实现
利用链表的基本操作实现复杂算法
1. 线性表的链式存储结构链式存储结构用于存放线性表中的元素的存储单元在内存中可以是连续的，也可以是零散分布的。由于线性表中各元素间存在着线性关系，为了表示元素间的这种线性关系，链式存储结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。采用链式存储结构表示的线性表简称链表 (Linked List) 。
1.1 指针相关概念在继续进行讲解前，我们首先来了解指针的相关概念，以便更好的理解链表。假设我们需要处理一个大型数据文件，这一文件已经被读取保持在内存中，当我们在函数间传递文件时，并不会直接传递整个文件，我们需要创建变量来保存文件在内存中的位置，这些变量很小，很容易在不同的函数之间传递。
使用指针的好处之一就是可以用一个简单的内存地址就可以指向一个更大的内存地址段。计算机硬件中存在对指针的支持，称为间接寻址。
与 C 语言等不同，在 Python/ target=_blank class=infotextkey>Python 中，我们不需要直接操作指针，但这并不意味着 Python 中不使用指针。例如赋值语句 l = list([1, 2, 3])，我们通常会说 l 是列表类型的变量，或者直接说 l 是一个列表，但这并不准确，变量 l 是对列表的引用(指针)，list 构造函数在内存中的创建一个 list 并返回该 list 起始的内存位置，这就是存储在 l 中的内容，Python 隐藏了这种复杂性。
1.2 指针结构每个指针结构都包含一个或多个指向结构中其他元素的链接，这些链接的类型取决于我们创建的数据类型，例如在链表中，我们将链接到结构中的下一个或上一个元素。
指针结构具有如下优点：

不需要连续的顺序存储空间
可以快速添加或删除结点，在常数时间内扩展结构空间

但指针的这种灵活性是有代价的，即需要额外的空间来存储地址。例如有一个整数线性表，我们在每个结点中不仅需要存储一个整数数据，同时还需要一个额外空间用于存储指向下一个结点的指针。
1.3 结点一个结点是一个数据容器，以及一个或多个指向其它结点的链接，链接就是一个指针。一种简单的结点只有到下一个结点的链接。假如我们有一个包含水果清单的链表，我们知道字符串实际上并不存储在结点中，而是有一个指向实际字符串的指针，如下图所示，其中包含两个结点，第一个结点有一个指向存储在内存中的字符串 (Apple) 的指针和一个存储下一个结点地址的指针，因此，这个简单结点的存储要求是两个内存地址，包括数据域和指针域：

文章插图

我们还需要考虑的一个问题是，最后一个结点的指针域，我们需要确保每个结点的指针域都指向一个明确的值。如果我们要明确让最后一个结点的指针域不指向任何内容，那么在 Python 中，我们需要使用特殊值 None 来表示什么都没有。如下图所示，链表的最后一个结点的指针域指向 None：

文章插图

1.4 结点类接下来，我们将实现上述结点结构：

class Node:def __init__(self, data=https://www.isolves.com/it/cxkf/yy/Python/2022-07-29/None):self.data = dataself.next = None

Next 指针初始化为 None，这意味着默认结点为端点，除非更改 Next 的值，这样可以确保正确终止链表。我们也可以根据需要向结点类添加其他内容，例如我们可以创建一个 Fruit 类，用于存储不同水果售价信息等数据，并使用数据域链接到 Fruit 类的实例。为了能够打印节点信息，我们需要重载 str 方法：