您已经看到了 Python 中的列表。它们既方便又强大。通常，每当需要在列表中存储某些内容时，都可以使用 python 的内置列表实现。然而，在本章中，我们更感兴趣的是了解列表是如何工作的。所以我们要研究列表的内部结构。您会注意到，有不同类型的列表。
Python 的列表实现被设计为功能强大，并且包含了几个不同的用例。我们将对列表的定义更加严格。节点的概念对于列表非常重要。我们将在本章中讨论它们，但这一概念将以不同的形式在本书的其余部分重新出现。
本章的重点如下：
- 理解 Python 中的指针
- 处理节点的概念
- 实现单链表、双链表和循环链表
在这一章中，我们将处理相当多的指针。因此，提醒自己这些是什么可能是有用的。首先，想象你有一栋房子想卖掉。由于时间不够，您需要联系代理商以找到感兴趣的买家。所以你把房子拿起来交给经纪人，经纪人会把房子交给任何想买房子的人。你说可笑？现在假设您有一些处理图像的 Python 函数。因此，在函数之间传递高分辨率图像数据。
当然，你不能带着你的房子到处走。你要做的就是把房子的地址写在一张废纸上，交给经纪人。房子仍在原处，但包含房子方向的便条被传递。你甚至可以把它写在几张纸上。每一个都足够小，可以放进你的钱包，但它们都指向同一所房子。
事实证明，Python 领域的情况并没有太大的不同。这些大型图像文件保留在内存中的一个位置。您要做的是创建变量，将这些图像的位置保存在内存中。这些变量很小，很容易在不同的函数之间传递。
这就是指针的最大好处：它们允许您用一个简单的内存地址指向一个潜在的大内存段。
计算机硬件中存在对指针的支持，称为间接寻址。
在 Python 中，与其他一些语言（如 C 或 Pascal）不同，您不直接操作指针。这导致一些人认为 Python 中没有使用指针。没有比这更离谱的了。在 Python 交互式 shell 中考虑这个任务：
>>> s = set()我们通常会说s是集合类型的变量。也就是说，s是一套。然而，这并不是绝对正确的。变量s相当于一个集合的引用（一个“安全”指针）。集合构造函数在内存中的某个位置创建集合，并返回该集合开始的内存位置。这就是存储在s中的内容。
Python 对我们隐藏了这种复杂性。我们可以放心地假设s是一个集合，并且一切正常。
数组是数据的顺序列表。顺序意味着每个元素存储在内存中前一个元素之后。如果您的阵列非常大，并且内存不足，则可能无法找到足够大的存储空间来容纳整个阵列。这将导致问题。
当然，硬币的另一面是阵列速度非常快。由于每个元素都是内存中前一个元素的后续元素，因此不需要在不同的内存位置之间跳转。在您自己的实际应用程序中选择列表和数组时，这一点非常重要。
与数组相反，指针结构是可以在内存中展开的项的列表。这是因为每个项目都包含一个或多个指向结构中其他项目的链接。这些链接的类型取决于我们的结构类型。如果我们处理的是链表，那么我们将拥有指向结构中下一个（可能是上一个）项的链接。在树的情况下，我们有父子链接以及兄弟链接。在基于平铺的游戏中，游戏地图由六角组成，每个节点将链接到最多六个相邻的地图单元。
指针结构有几个好处。首先，它们不需要顺序存储空间。其次，当您向结构中添加更多节点时，它们可以从小处开始任意增长。
然而，这是有代价的。如果您有一个整数列表，那么每个节点将占用一个整数的空间，以及一个用于存储指向下一个节点的指针的额外整数。
列表（以及其他一些数据结构）的核心是节点的概念。在我们进一步讨论之前，让我们先考虑一下这个想法。
首先，我们将创建几个字符串：
>>> a = "eggs"
>>> b = "ham"
>>> c = "spam"现在有三个变量，每个变量都有一个唯一的名称、类型和值。我们没有一种方式来说明变量之间的相互关系。节点允许我们这样做。节点是数据的容器，以及到其他节点的一个或多个链接。链接是指针。
一种简单的节点类型是只有到下一个节点的链接的节点。
当然，知道我们如何处理指针后，我们意识到这并不完全正确。该字符串实际上并不存储在节点中，而是指向实际字符串的指针：
因此，这个简单节点的存储要求是两个内存地址。节点的数据属性是指向字符串eggs和ham的指针。
我们创建了三个节点：一个包含鸡蛋，一个包含火腿，另一个包含垃圾邮件。鸡蛋节点指向火腿节点，火腿节点又指向垃圾邮件节点。但是垃圾邮件节点指向什么？因为这是列表中的最后一个元素，所以我们需要确保它的下一个成员有一个值来说明这一点。
如果我们让最后一个元素没有指向任何东西，那么我们就把这个事实弄清楚了。在 python 中，我们将使用特殊值None表示无：
最后一个节点的下一个点指向“无”。因此，它是节点链中的最后一个节点。
下面是我们到目前为止讨论的一个简单的节点实现：
class Node:
def __init__(self, data=None):
self.data = data
self.next = None Do not confuse the concept of a node with Node.js, a server-side technology implemented in JavaScript.
next指针初始化为None，这意味着除非您更改next的值，否则节点将成为端点。这是一个好主意，这样我们就不会忘记正确终止列表。
您可以在node类中添加您认为合适的其他内容。只需确保记住节点和数据之间的区别。如果您的节点将包含客户数据，那么创建一个Customer类并将所有数据放在那里。
您可能要做的一件事是实现__str__方法，以便在将节点对象传递到打印时调用包含对象的__str__方法：
def __str__(self):
return str(data) 我们假设节点具有指向下一个节点的指针。这可能是最简单的节点类型。但是，根据我们的需求，我们可以创建许多其他类型的节点。
有时我们希望从 A 转到 B，但同时从 B 转到 A。在这种情况下，我们在下一个指针的基础上添加上一个指针：
从图中可以看出，我们让最后一个和第一个节点都指向None，以表示我们已经到达列表端点的边界。第一个节点的上一个指针指向 None，因为它没有前置节点，正如最后一个项目的下一个指针指向None，因为它没有后续节点。
您也可能正在为基于互动程序的游戏创建互动程序。在这种情况下，可以使用北、南、东和西，而不是上一个和下一个。指针的类型有很多种，但原理是一样的。地图末尾的瓷砖将指向None：
你可以把这个带到你需要的地方。如果你需要能够移动西北、东北、东南和西南，你所要做的就是将这些指针添加到你的node类中。
单链表是两个连续节点之间只有一个指针的列表。它只能沿单个方向遍历，也就是说，可以从列表中的第一个节点移动到最后一个节点，但不能从最后一个节点移动到第一个节点。
实际上，我们可以使用前面创建的node类来实现一个非常简单的单链表：
>>> 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 以指向列表中的下一个元素。我们一直这样做，直到我们到达列表的末尾。
但是，这种过于简单的列表实现存在几个问题：
- 它需要程序员做太多的手工工作
- 它太容易出错（这是第一点的结果）
- 列表的太多内部工作向程序员公开
我们将在以下章节中讨论所有这些问题。
列表显然是一个独立于节点的概念。因此，我们首先创建一个非常简单的类来保存列表。我们将从一个构造函数开始，该构造函数保存对列表中第一个节点的引用。由于此列表最初为空，我们将首先将此引用设置为None：
class SinglyLinkedList:
def __init__(self):
self.tail = None 我们需要执行的第一个操作是将项目附加到列表中。此操作有时称为插入操作。在这里我们有机会躲开Node班。我们list类的用户应该永远不必与节点对象交互。这些纯粹是内部使用。
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是否指向节点）。如果没有，我们将新节点作为列表的第一个节点；否则，通过遍历列表到最后一个节点，将最后一个节点的下一个指针更新到新节点，找到插入点。
我们可以附加一些项目：
>>> words = SinglyLinkedList()
>>> words.append('egg')
>>> words.append('ham')
>>> words.append('spam')列表遍历将或多或少像以前一样工作。您将从列表本身获取列表的第一个元素：
>>> current = words.tail
>>> while current:
print(current.data)
current = current.next上一节中的 append 方法有一个大问题：它必须遍历整个列表才能找到插入点。当列表中只有几个项目时，这可能不是问题，但请等待，直到您需要添加数千个项目。每个附加都会比前一个稍微慢一点。一个O（n）来证明我们当前的append方法的实现实际上会有多慢。
为了解决这个问题，我们不仅要存储对列表中第一个节点的引用，还要存储对最后一个节点的引用。这样，我们就可以在列表的末尾快速添加一个新节点。追加操作的最坏情况运行时间现在从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。然后我们在append方法中将大小增加 1：
class SinglyLinkedList:
def __init__(self):
# ...
self.size = 0
def append(self, data):
# ...
self.size += 1 因为我们现在只读取节点对象的 size 属性，而不使用循环来计算列表中的节点数，所以我们可以将最坏情况下的运行时间从O（n）减少到O（1）。
如果你注意到我们如何浏览我们的列表。那是一个我们仍然接触到node阶级的地方。我们需要使用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.size -= 1
return
prev = current
current = current.next 删除一个节点需要一个O（n）。
我们可能还需要一种方法来检查列表是否包含项目。由于我们之前编写的iter()方法，此方法相当容易实现。循环的每个过程都会将当前数据与正在搜索的数据进行比较。如果找到匹配项，则返回True，否则返回False：
def search(self, data):
for node in self.iter():
if data == node:
return True
return False 我们可能需要一种快速清除列表的方法。幸运的是，这很简单。我们所做的就是通过将指针head和tail设置为None来清除它们：
def clear(self):
""" Clear the entire list. """
self.tail = None
self.head = None 一下子，我们孤立了列表中tail和head指针处的所有节点。这会产生一个连锁反应，即孤立中间的所有节点。
既然我们已经对什么是单链表以及可以对其执行的操作有了坚实的基础，我们现在将把我们的重点更高一个档次地转向双链表的主题。
双链表在某种程度上类似于单链表，因为我们使用了将节点串在一起的相同基本思想。在单链表中，每个连续节点之间存在一个链接。双链接列表中的节点有两个指针：指向下一个节点的指针和指向上一个节点的指针：
单链表中的节点只能确定与其关联的下一个节点。但是被引用的节点或下一个节点无法判断谁在进行引用。流向为单向。
在双链表中，我们向每个节点添加了不仅引用下一个节点而且还引用上一个节点的功能。
为了更好地理解，让我们检查两个连续节点之间存在的链接的性质：
由于存在指向下一个和上一个节点的两个指针，双链接列表就具备了某些功能。
双链接列表可以在任何方向上遍历。根据正在执行的操作，双链接列表中的节点可以在必要时轻松引用其前一个节点，而无需指定变量来跟踪该节点。由于单链表只能在一个方向上遍历，因此有时可能意味着移动到列表的开头或开头，以实现隐藏在列表中的某些更改。
由于可以立即访问下一个和上一个节点，因此删除操作更容易执行，您将在本章后面看到。
创建一个类以捕获双链表节点的 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变量继续保存对下一个节点的引用。
创建一个类来捕获函数将要操作的数据仍然很重要：
class DoublyLinkedList(object):
def __init__(self):
self.head = None
self.tail = None
self.count = 0为了增强size方法，我们还将count实例变量设置为 0。当我们开始向列表中插入节点时，head和tail将指向列表的开头和结尾。
我们采用了一种新的约定，self.head指向列表的初学者节点，self.tail指向添加到列表中的最新节点。这与我们在单链表中使用的约定相反。关于头节点指针和尾节点指针的命名没有固定的规则。
双链接列表还需要提供返回列表大小、插入列表以及从列表中删除节点的函数。我们将检查一些代码来实现这一点。让我们从append操作开始。
在append操作过程中，重要的是检查head是否为None。如果是None，则表示列表为空，应该将head设置为指向刚创建的节点。列表的tail也通过头部指向新节点。在这一系列步骤结束时，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 下图演示了将新节点添加到空列表时双链接列表的头指针和尾指针。
算法的else部分仅在列表不为空时执行。新节点的上一个变量设置为列表的尾部：
new_node.prev = self.tail 尾部的下一个指针（或变量）设置为新节点：
self.tail.next = new_node 最后，我们更新尾部指针以指向新节点：
self.tail = new_node 由于append操作将节点数增加 1，因此我们将计数器增加 1：
self.count += 1 append操作的视觉表示如下：
与单链表不同，在单链表中，我们需要在遍历列表的整个长度时随时跟踪以前遇到的节点，而双链表避免了整个步骤。这可以通过使用上一个指针来实现
在完成删除节点之前，从双链表中删除节点的算法基本上满足四种情况。这些是：
- 当根本找不到搜索项时
- 在列表最开始处找到搜索项时
- 在列表末尾找到搜索项时
- 当在列表中间找到某个搜索项时
当其data实例变量与传递给要在搜索节点时使用的方法的数据匹配时，将标识要删除的节点。如果找到匹配节点并随后删除，则变量node_deleted设置为True。任何其他结果导致node_deleted被设置为False：
def delete(self, data):
current = self.head
node_deleted = False
... 在delete方法中，current变量设置为列表的头部（即指向列表的self.head。然后使用一组if... else语句搜索列表的各个部分，以找到具有指定数据的节点。
首先搜索head节点。由于current指向head，如果current为无，则假定列表中没有节点，搜索甚至可以开始查找要删除的节点：
if current is None:
node_deleted = False 但是，如果current（现在指向 head）包含正在搜索的数据，则self.head被设置为指向current下一个节点。由于现在头部后面没有节点，self.head.prev设置为None：
elif current.data == data:
self.head = current.next
self.head.prev = None
node_deleted = True 如果要删除的节点位于列表的末尾，则采用类似的策略。这是搜索要删除的节点可能位于列表末尾的第三条语句：
elif self.tail.data == data:
self.tail = self.tail.prev
self.tail.next = None
node_deleted = True 最后，查找和删除节点的算法通过节点列表循环。如果找到匹配的节点，current的前一个节点连接到当前的下一个节点。在该步骤之后，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 在对所有的if-else语句求值之后，检查node_delete变量。如果if-else语句中的任何一个更改了此变量，则表示已从列表中删除了一个节点。因此，count 变量递减 1：
if node_deleted:
self.count -= 1 作为删除被埋入列表中的节点的示例，假设存在三个节点 A、B 和 C。在列表中间删除节点 B，我们将本质上指向 C 作为下一个节点，同时使 C 点指向其先前的节点：
在这样一次操作之后，我们将得到以下列表：
搜索算法类似于单链表中的search方法。我们调用内部方法iter()返回所有节点中的数据。当我们循环遍历数据时，每个数据都与传递到contain方法的数据相匹配。如果有匹配项，则返回True，否则返回False表示未找到匹配项：
def contain(self, data):
for node_data in self.iter():
if data == node_data:
return True
return False 我们的双链表有一个用于append操作的O（1）和用于delete操作的O（n）。
循环列表是链表的特例。它是连接端点的列表。也就是说，列表中的最后一个节点指向第一个节点。循环列表可以基于单链接列表和双链接列表。对于双链接循环列表，第一个节点还需要指向最后一个节点。
在这里，我们将看到一个单链接循环列表的实现。一旦掌握了基本概念，实现双链接循环列表应该很简单。
我们可以重用我们在单链表部分中创建的node类。事实上，我们也可以重用SinglyLinkedList类的大部分部分。因此，我们将重点讨论循环列表实现不同于普通单链表的方法。
当我们将一个元素附加到循环列表中时，我们需要确保新节点指向尾部节点。下面的代码演示了这一点。与单链表实现相比，还有一行额外的内容：
def append(self, data):
node = Node(data)
if self.head:
self.head.next = node
self.head = node
else:
self.head = node
self.tail = node
self.head.next = self.tail
self.size += 1 我们可能认为我们可以遵循与 append 相同的原则，只需确保头部指向尾部。这将为我们提供以下实施：
def delete(self, data):
current = self.tail
prev = self.tail
while current:
if current.data == data:
if current == self.tail:
self.tail = current.next
self.head.next = self.tail
else:
prev.next = current.next
self.size -= 1
return
prev = current
current = current.next 如前所述，只有一行需要更改。只有在移除尾部节点时，我们才需要确保头部节点更新为指向新的尾部节点。
然而，这段代码有一个严重的问题。在循环列表的情况下，我们不能循环直到电流变为None，因为这永远不会发生。如果删除一个现有节点，您将看不到这一点，但是尝试删除一个不存在的节点，您将陷入一个不确定的循环中。
因此，我们需要找到一种不同的方法来控制while循环。我们无法检查电流是否到达头部，因为这样它将永远不会检查最后一个节点。但我们可以使用prev，因为它落后于电流一个节点。然而，有一种特殊情况。第一次循环迭代current和prev将指向同一个节点，即尾部节点。我们希望确保循环在这里运行，因为我们需要考虑单节点列表。更新后的delete方法如下：
def delete(self, data):
current = self.tail
prev = self.tail
while prev == current or prev != self.head:
if current.data == data:
if current == self.tail:
self.tail = current.next
self.head.next = self.tail
else:
prev.next = current.next
self.size -= 1
return
prev = current
current = current.next 您不需要修改iter()方法。它将非常适合我们的循环列表。但是在循环遍历循环列表时，确实需要设置退出条件，否则程序将陷入循环。通过使用计数器变量，可以实现以下目的：
words = CircularList()
words.append('eggs')
words.append('ham')
words.append('spam')
counter = 0
for word in words.iter():
print(word)
counter += 1
if counter > 1000:
break 一旦我们打印出 1000 个元素，我们就打破了循环。
在本章中，我们将介绍链表。我们研究了列表的基础概念，例如节点和指向其他节点的指针。我们实现了在这些类型的列表上发生的主要操作，并查看了它们最坏情况下的运行时间的比较。
在下一章中，我们将研究通常使用列表实现的两种其他数据结构：栈和队列。