原文：
zh.annas-archive.org/md5/66ae3d5970b9b38c5ad770b42fec806d译者：飞龙
第四章：列表和指针结构
我们已经在 Python 中讨论了列表，它们方便而强大。通常情况下，我们使用 Python 内置的列表实现来存储任何数据。然而，在本章中，我们将了解列表的工作原理，并将研究列表的内部。
Python 的列表实现非常强大，可以包含多种不同的用例。节点的概念在列表中非常重要。我们将在本章讨论它们，并在整本书中引用它们。因此，我们建议读者仔细学习本章的内容。
本章的重点将是以下内容：
- 理解 Python 中的指针
- 理解节点的概念和实现
- 实现单向、双向和循环链表。
技术要求
根据本章讨论的概念执行程序将有助于更好地理解它们。我们已经提供了本章中所有程序和概念的源代码。我们还在 GitHub 上提供了完整的源代码文件，链接如下：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter04。
我们假设您已经在系统上安装了 Python。
从一个例子开始
让我们先提醒一下指针的概念，因为我们将在本章中处理它们。首先，想象一下你有一所房子想要卖掉。由于时间不够，你联系了一个中介来寻找感兴趣的买家。所以，你拿起你的房子，把它带到中介那里，中介会把房子带给任何可能想要买它的人。你觉得这很荒谬？现在想象一下你有一些处理图像的 Python 函数。所以，你在这些函数之间传递高分辨率图像数据。
当然，你不会带着你的房子四处走动。你要做的是把房子的地址写在一张废纸上，递给中介。房子还在原地，但包含房子地址的纸条在传递。你甚至可以在几张纸上写下来。每张纸都足够小，可以放在你的钱包里，但它们都指向同一所房子。
事实证明，在 Python 领域情况并没有太大不同。那些大型图像文件仍然在内存中的一个地方。
你要做的是创建变量，保存这些图像在内存中的位置。这些变量很小，可以在不同的函数之间轻松传递。
这就是指针的好处——它们允许你用一个简单的内存地址指向一个潜在的大内存段。
你的计算机硬件中支持指针，这被称为间接寻址。
在 Python 中，你不会直接操作指针，不像其他一些语言，比如 C 或 Pascal。这导致一些人认为 Python 中不使用指针。这是大错特错。考虑一下在 Python 交互式 shell 中的这个赋值：
>>> s = set()
通常我们会说s是集合类型的变量。也就是说，s是一个集合。然而，这并不严格正确；变量s实际上是一个引用（一个安全指针）指向一个集合。集合构造函数在内存中创建一个集合，并返回该集合开始的内存位置。这就是存储在s中的内容。Python 隐藏了这种复杂性。我们可以安全地假设s是一个集合，一切都运行正常。
数组
数组是一系列数据的顺序列表。顺序意味着每个元素都存储在前一个元素的后面。如果你的数组非常大，而且内存不足，可能无法找到足够大的存储空间来容纳整个数组。这将导致问题。
当然，硬币的另一面是数组非常快速。由于每个元素在内存中紧随前一个元素，因此无需在不同的内存位置之间跳转。在选择在你自己的现实世界应用程序中列表和数组之间时，这可能是一个非常重要的考虑因素。
我们已经在第二章中讨论了数组，Python 数据类型和结构。我们看了数组数据类型，并讨论了可以对其执行的各种操作。
指针结构
与数组相反，指针结构是可以在内存中分散的项目列表。这是因为每个项目都包含一个或多个指向结构中其他项目的链接。这些链接的类型取决于我们拥有的结构类型。如果我们处理的是链表，那么我们将有指向结构中下一个（可能是上一个）项目的链接。在树的情况下，我们有父子链接以及兄弟链接。
指针结构有几个好处。首先，它们不需要顺序存储空间。其次，它们可以从小开始，随着向结构添加更多节点而任意增长。然而，指针的这种灵活性是有代价的。我们需要额外的空间来存储地址。例如，如果你有一个整数列表，每个节点都将占用空间来存储一个整数，以及额外的整数来存储指向下一个节点的指针。
节点
在列表（以及其他几种数据结构）的核心是节点的概念。在我们进一步讨论之前，让我们考虑一下这个想法。
首先，让我们考虑一个例子。我们将创建一些字符串：
>>> a = "eggs" >>> b = "ham" >>> c = "spam"
现在你有了三个变量，每个变量都有一个唯一的名称、类型和值。目前，没有办法显示这些变量之间的关系。节点允许我们展示这些变量之间的关系。节点是数据的容器，以及一个或多个指向其他节点的链接。链接就是指针。
一种简单类型的节点只有一个指向下一个节点的链接。正如我们所知道的指针，字符串实际上并没有存储在节点中，而是有一个指向实际字符串的指针。考虑下面的图表中的例子，其中有两个节点。第一个节点有一个指向存储在内存中的字符串（eggs）的指针，另一个指针存储着另一个节点的地址：
因此，这个简单节点的存储需求是两个内存地址。节点的数据属性是指向字符串eggs和ham的指针。
查找端点
我们已经创建了三个节点——一个包含eggs，一个ham，另一个spam。eggs节点指向ham节点，ham节点又指向spam节点。但是spam节点指向什么呢？由于这是列表中的最后一个元素，我们需要确保它的下一个成员有一个清晰的值。
如果我们使最后一个元素指向空，那么我们就清楚地表明了这一事实。在 Python 中，我们将使用特殊值None来表示空。考虑下面的图表。节点B是列表中的最后一个元素，因此它指向None：
最后一个节点的下一个指针指向None。因此，它是节点链中的最后一个节点。
节点类
这是我们迄今为止讨论的一个简单节点实现：
class Node: def __init__ (self, data=None): self.data = data self.next = None
Next指针初始化为None，这意味着除非你改变Next的值，否则节点将成为一个端点。这是一个很好的主意，这样我们就不会忘记正确终止列表。
你可以根据需要向节点类添加其他内容。只要记住节点和数据之间的区别。如果你的节点将包含客户数据，那么创建一个Customer类，并把所有数据放在那里。
您可能想要做的一件事是实现_str_方法，以便在将节点对象传递给打印时调用所包含对象的_str_方法：
def _str_ (self): return str(data)
其他节点类型
正如我们已经讨论过的，一个节点具有指向下一个节点的指针来链接数据项，但它可能是最简单的节点类型。此外，根据我们的需求，我们可以创建许多其他类型的节点。
有时我们想从节点A到节点B，但同时我们可能需要从节点B到节点A。在这种情况下，我们除了Next指针之外还添加了Previous指针：
从上图可以看出，我们除了数据和Next指针之外，还创建了Previous指针。还需要注意的是，B的Next指针是None，而节点A的Previous指针也是None，这表示我们已经到达了列表的边界。第一个节点A的前指针指向None，因为它没有前驱，就像最后一个项目B的Next指针指向None一样，因为它没有后继节点。
引入列表
列表是一个重要且流行的数据结构。列表有三种类型——单链表、双链表和循环链表。我们将在本章更详细地讨论这些数据结构。我们还将在接下来的小节中讨论各种重要操作，如append操作、delete操作以及可以在这些列表上执行的traversing和searching操作。
单链表
单链表是一种只有两个连续节点之间的指针的列表。它只能以单个方向遍历；也就是说，您可以从列表中的第一个节点到最后一个节点，但不能从最后一个节点移动到第一个节点。
实际上，我们可以使用之前创建的节点类来实现一个非常简单的单链表。例如，我们创建三个存储三个字符串的节点n1、n2和n3：
>>> n1 = Node('eggs') >>> n2 = Node('ham') >>> n3 = Node('spam')
接下来，我们将节点链接在一起，形成一个链：
>>> n1.next = n2 >>> n2.next = n3
要遍历列表，您可以像下面这样做。我们首先将current变量设置为列表中的第一个项目，然后通过循环遍历整个列表，如下面的代码所示：
current = n1 while current: print(current.data) current = current.next
在循环中，我们打印出当前元素，然后将current设置为指向列表中的下一个元素。我们一直这样做，直到我们到达列表的末尾。
然而，这种简单的列表实现存在几个问题：
- 程序员需要做太多的手动工作
- 这太容易出错了（这是第一点的结果）
- 列表的内部工作过于暴露给程序员
我们将在接下来的章节中解决所有这些问题。
单链表类
列表是一个与节点不同的概念。我们首先创建一个非常简单的类来保存我们的列表。我们从一个构造函数开始，它保存对列表中第一个节点的引用（在下面的代码中是tail）。由于这个列表最初是空的，我们将首先将这个引用设置为None：
class SinglyLinkedList: def __init__ (self): self.tail = None
追加操作
我们需要执行的第一个操作是向列表追加项目。这个操作有时被称为插入操作。在这里，我们有机会隐藏Node类。我们的列表类的用户实际上不应该与Node对象交互。这些纯粹是内部使用的。
第一次尝试append()方法可能如下所示：
class SinglyLinkedList: # ... def append(self, data): # Encapsulate the data in a Node node = Node(data) if self.tail == None: self.tail = node else: current = self.tail while current.next: current = current.next current.next = node
我们封装数据在一个节点中，以便它具有下一个指针属性。从这里开始，我们检查列表中是否存在任何现有节点（即self.tail是否指向一个Node）。如果是None，我们将新节点设置为列表的第一个节点；否则，我们通过遍历列表找到插入点，将最后一个节点的下一个指针更新为新节点。
考虑以下示例代码以追加三个节点：
>>> words = SinglyLinkedList() >>> words.append('egg') >>> words.append('ham') >>> words.append('spam')
列表遍历将按照我们之前讨论的方式进行。您将从列表本身获取列表的第一个元素，然后通过next指针遍历列表：
>>> current = words.tail >>> while current: print(current.data) current = current.next
更快的追加操作
在前一节中，追加方法存在一个大问题：它必须遍历整个列表以找到插入点。当列表中只有一些项目时，这可能不是问题，但当列表很长时，这将是一个大问题，因为我们需要每次遍历整个列表来添加一个项目。每次追加都会比上一次略慢。追加操作的当前实现速度降低了O(n)，这在长列表的情况下是不可取的。
为了解决这个问题，我们不仅存储了对列表中第一个节点的引用，还存储了对最后一个节点的引用。这样，我们可以快速地在列表的末尾追加一个新节点。追加操作的最坏情况运行时间现在从O(n)降低到了O(1)。我们所要做的就是确保前一个最后一个节点指向即将追加到列表中的新节点。以下是我们更新后的代码：
class SinglyLinkedList: def init (self): # ... self.tail = None def append(self, data): node = Node(data) if self.head: self.head.next = node self.head = node else: self.tail = node self.head = node
请注意正在使用的约定。我们追加新节点的位置是通过self.head。self.tail变量指向列表中的第一个节点。
获取列表的大小
我们希望能够通过计算节点的数量来获取列表的大小。我们可以通过遍历整个列表并在遍历过程中增加一个计数器来实现这一点：
def size(self): count = 0 current = self.tail while current: count += 1 current = current.next return count
这很好用。但是，列表遍历可能是一个昂贵的操作，我们应该尽量避免。因此，我们将选择另一种重写方法。我们在SinglyLinkedList类中添加一个 size 成员，在构造函数中将其初始化为0。然后我们在追加方法中将 size 增加一：
class SinglyLinkedList: def init (self): # ...
self.size = 0 def append(self, data): # ... self.size += 1
因为我们现在只是读取节点对象的 size 属性，而不是使用循环来计算列表中节点的数量，所以我们将最坏情况的运行时间从O(n)降低到了O(1)。
改进列表遍历
如果您注意到，在列表遍历的早期，我们向客户/用户公开了节点类。但是，希望客户端节点不要与节点对象进行交互。我们需要使用node.data来获取节点的内容，使用node.next来获取下一个节点。我们可以通过创建一个返回生成器的方法来访问数据。如下所示：
def iter(self): current = self.tail while current: val = current.data current = current.next yield val
现在，列表遍历变得简单得多，看起来也好得多。我们可以完全忽略列表之外有一个叫做节点的东西：
for word in words.iter(): print(word)
注意，由于iter()方法产生节点的数据成员，我们的客户端代码根本不需要担心这一点。
删除节点
您将在列表上执行的另一个常见操作是删除节点。这可能看起来很简单，但我们首先必须决定如何选择要删除的节点。它是由索引号还是由节点包含的数据来确定的？在这里，我们将选择根据节点包含的数据来删除节点。
以下是在从列表中删除节点时考虑的特殊情况的图示：
当我们想要删除两个节点之间的一个节点时，我们所要做的就是使前一个节点指向其下一个要删除的节点的后继节点。也就是说，我们只需将要删除的节点从链表中切断，并直接指向下一个节点，如前面的图所示。
delete()方法的实现可能如下所示：
def delete(self, data): current = self.tail prev = self.tail while current: if current.data == data: if current == self.tail: self.tail = current.next else: prev.next = current.next self.count -= 1 return prev = current current = current.next
删除节点的delete操作的时间复杂度为O(n)。
列表搜索
我们可能还需要一种方法来检查列表是否包含某个项目。由于我们之前编写的iter()方法，这种方法非常容易实现。循环的每次通过将当前数据与正在搜索的数据进行比较。如果找到匹配项，则返回True，否则返回False：
def search(self, data): for node in self.iter(): if data == node: return True return False
清除列表
我们可能需要快速清除列表；有一种非常简单的方法可以做到。我们可以通过简单地将指针头和尾清除为None来清除列表：
def clear(self): """ Clear the entire list. """ self.tail = None self.head = None
双向链表
我们已经讨论了单链表以及可以在其上执行的重要操作。现在，我们将在本节中专注于双向链表的主题。
双向链表与单链表非常相似，因为我们使用了将字符串节点串在一起的相同基本概念，就像在单链表中所做的那样。单链表和双链表之间唯一的区别在于，在单链表中，每个连续节点之间只有一个链接，而在双链表中，我们有两个指针——一个指向下一个节点，一个指向前一个节点。请参考以下节点的图表；有一个指向下一个节点和前一个节点的指针，它们设置为None，因为没有节点连接到这个节点。考虑以下图表：
单链表中的节点只能确定与其关联的下一个节点。然而，没有办法或链接可以从这个引用节点返回。流动的方向只有一种。
在双向链表中，我们解决了这个问题，并且不仅可以引用下一个节点，还可以引用前一个节点。考虑以下示例图表，以了解两个连续节点之间链接的性质。这里，节点A引用节点B；此外，还有一个链接返回到节点A：
由于存在指向下一个和前一个节点的两个指针，双向链表具有某些功能。
双向链表可以在任何方向进行遍历。在双向链表中，可以很容易地引用节点的前一个节点，而无需使用变量来跟踪该节点。然而，在单链表中，可能难以返回到列表的开始或开头，以便在列表的开头进行一些更改，而在双向链表的情况下现在非常容易。
双向链表节点
创建双向链表节点的 Python 代码包括其初始化方法、prev指针、next指针和data实例变量。当新建一个节点时，所有这些变量默认为None：
class Node(object): def __init__ (self, data=None, next=None, prev=None): self.data = data self.next = next self.prev = prev
prev变量引用前一个节点，而next变量保留对下一个节点的引用，data变量存储数据。
双向链表类
双向链表类捕获了我们的函数将要操作的数据。对于size方法，我们将计数实例变量设置为0；它可以用来跟踪链表中的项目数量。当我们开始向列表中插入节点时，head和tail将指向列表的头部和尾部。考虑以下用于创建类的 Python 代码：
class DoublyLinkedList(object): def init (self): self.head = None self.tail = None self.count = 0
我们采用了一个新的约定，其中self.head指向列表的起始节点，而self.tail指向添加到列表中的最新节点。这与我们在单链表中使用的约定相反。关于头部和尾部节点指针的命名没有固定的规则。
双链表还需要返回列表大小、向列表中插入项目以及从列表中删除节点的功能。我们将在以下子部分中讨论并提供关于双链表的重要功能和代码。让我们从附加操作开始。
附加操作
append操作用于在列表的末尾添加元素。重要的是要检查列表的head是否为None。如果是None，则表示列表为空，否则列表有一些节点，并且将向列表添加一个新节点。如果要向空列表添加新节点，则应将head指向新创建的节点，并且列表的尾部也应通过head指向该新创建的节点。经过这一系列步骤，头部和尾部现在将指向同一个节点。以下图示了当向空列表添加新节点时，双链表的head和tail指针：
以下代码用于将项目附加到双链表：
def append(self, data): """ Append an item to the list. """ new_node = Node(data, None, None) if self.head is None: self.head = new_node self.tail = self.head else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node self.count += 1
上述程序的If部分用于将节点添加到空节点；如果列表不为空，则将执行上述程序的else部分。如果要将新节点添加到列表中，则新节点的前一个变量应设置为列表的尾部：
new_node.prev = self.tail
尾部的下一个指针（或变量）必须设置为新节点：
self.tail.next = new_node
最后，我们更新尾部指针以指向新节点：
self.tail = new_node
由于附加操作将节点数增加一，因此我们将计数器增加一：
self.count += 1
以下图示了向现有列表附加操作的可视表示：
删除操作
与单链表相比，双链表中的删除操作更容易。
与单链表不同，我们需要在遍历整个列表的整个长度时始终跟踪先前遇到的节点，双链表避免了整个步骤。这是通过使用前一个指针实现的。
在双链表中，delete操作可能会遇到以下四种情况：
- 未找到要删除的搜索项在列表中
- 要删除的搜索项位于列表的开头
- 要删除的搜索项位于列表的末尾
- 要删除的搜索项位于列表的中间
要删除的节点是通过将数据实例变量与传递给方法的数据进行匹配来识别的。如果数据与节点的数据变量匹配，则将删除该匹配的节点。以下是从双链表中删除节点的完整代码。我们将逐步讨论此代码的每个部分：
def delete(self, data): """ Delete a node from the list. """ current = self.head node_deleted = False if current is None: #Item to be deleted is not found in the list node_deleted = False elif current.data == data: #Item to be deleted is found at starting of list self.head = current.next self.head.prev = None node_deleted = True elif self.tail.data == data: #Item to be deleted is found at the end of list. self.tail = self.tail.prev self.tail.next = None node_deleted = True else: while current: #search item to be deleted, and delete that node if current.data == data: current.prev.next = current.next current.next.prev = current.prev node_deleted = True current = current.next if node_deleted: self.count -= 1
最初，我们创建一个node_deleted变量来表示列表中被删除的节点，并将其初始化为False。如果找到匹配的节点并随后删除，则将node_deleted变量设置为True。在删除方法中，current变量最初设置为列表的head（即指向列表的self.head）。请参阅以下代码片段：
def delete(self, data): current = self.head node_deleted = False ...
接下来，我们使用一组if...else语句来搜索列表的各个部分，找出具有指定数据的节点，该节点将被删除。
首先，我们在head节点处搜索要删除的数据，如果在head节点处匹配数据，则将删除该节点。由于current指向head，如果current为None，则表示列表为空，没有节点可以找到要删除的节点。以下是其代码片段：
if current is None: node_deleted = False
但是，如果current（现在指向头部）包含正在搜索的数据，这意味着我们在head节点找到了要删除的数据，那么self.head被标记为指向current节点。由于现在head后面没有节点了，self.head.prev被设置为None。考虑以下代码片段：
elif current.data == data: self.head = current.next self.head.prev = None node_deleted = True
同样，如果要删除的节点位于列表的“尾部”，我们通过将其前一个节点指向None来删除最后一个节点。这是双向链表中“删除”操作的第三种可能情况，搜索要删除的节点可能在列表末尾找到。self.tail被设置为指向self.tail.prev，self.tail.next被设置为None，因为后面没有节点了。考虑以下代码片段：
elif self.tail.data == data: self.tail = self.tail.prev self.tail.next = None node_deleted = True
最后，我们通过循环整个节点列表来搜索要删除的节点。如果要删除的数据与节点匹配，则删除该节点。要删除节点，我们使用代码current.prev.next = current.next使current节点的前一个节点指向当前节点的下一个节点。在那之后，我们使用current.next.prev = current.prev使current节点的下一个节点指向current节点的前一个节点。考虑以下代码片段：
else while current: if current.data == data: current.prev.next = current.next current.next.prev = current.prev node_deleted = True current = current.next
为了更好地理解双向链表中的删除操作的概念，请考虑以下示例图。在下图中，有三个节点，A，B和C。要删除列表中间的节点B，我们实质上会使A指向C作为其下一个节点，同时使C指向A作为其前一个节点：
进行此操作后，我们得到以下列表：
最后，检查node_delete变量以确定是否实际删除了节点。如果删除了任何节点，则将计数变量减少1，这可以跟踪列表中节点的总数。以下代码片段减少了删除任何节点时的计数变量1：
if node_deleted: self.count -= 1
列表搜索
在双向链表中搜索项目与在单向链表中的方式类似。我们使用iter()方法来检查所有节点中的数据。当我们遍历列表中的所有数据时，每个节点都与contain方法中传递的数据进行匹配。如果我们在列表中找到项目，则返回True，表示找到了该项目，否则返回False，这意味着在列表中未找到该项目。其 Python 代码如下：
def contain(self, data): for node_data in self.iter(): if data == node_data: return True return False
双向链表中的追加操作具有运行时间复杂度O(1)，删除操作具有复杂度O(n)。
循环列表
循环链表是链表的特殊情况。在循环链表中，端点彼此相连。这意味着列表中的最后一个节点指向第一个节点。换句话说，我们可以说在循环链表中，所有节点都指向下一个节点（在双向链表的情况下还指向前一个节点），没有结束节点，因此没有节点将指向Null。循环列表可以基于单向链表和双向链表。在双向循环链表的情况下，第一个节点指向最后一个节点，最后一个节点指向第一个节点。考虑以下基于单向链表的循环链表的图示，其中最后一个节点C再次连接到第一个节点A，从而形成循环列表：
下图显示了基于双向链表的循环链表概念，其中最后一个节点C通过next指针再次连接到第一个节点A。节点A也通过previous指针连接到节点C，从而形成一个循环列表：
在这里，我们将看一个单链表循环列表的实现。一旦我们理解了基本概念，实现双链表循环列表应该是直截了当的。
我们可以重用我们在子节中创建的节点类——单链表。事实上，我们也可以重用大部分SinglyLinkedList类的部分。因此，我们将专注于循环列表实现与普通单链表不同的方法。
Python 数据结构和算法实用指南（二）（2）https://developer.aliyun.com/article/1507554
