Python 中的链表：简介

既然您已经了解了链表的结构，您就可以查看它的一些实际用例了。

实际应用

链表在现实世界中有多种用途。它们可用于实现（剧透警报！）队列或堆栈以及图形。它们对于更复杂的任务也很有用，例如操作系统应用程序的生命周期管理。

在上图中，您可以看到堆栈中插入的第一个元素（索引0）在底部，而最后插入的元素在顶部。由于堆栈使用 LIFO 方法，插入的最后一个元素（在顶部）将首先被检索。

由于您从队列和堆栈的边缘插入和检索元素的方式，链表是实现这些数据结构的最方便的方法之一。您将在本文后面看到这些实现的示例。

图表

图形可用于显示对象之间的关系或表示不同类型的网络。例如，图形的可视化表示——比如有向无环图 (DAG)——可能如下所示：

介绍 collections.deque

在 Python 中，collections模块中有一个特定对象可用于链表，称为deque（发音为“deck”），它代表双端队列。

collections.deque使用链表的实现，您可以在其中访问、插入或删除列表开头或结尾的元素，性能恒定为O (1)。

>>> from collections import deque
>>> deque()
deque([])

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.appendleft("z")
>>> llist
deque(['z', 'a', 'b', 'c', 'd', 'e'])

>>> llist.popleft()
'z'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

队列

对于队列，您希望将值添加到列表 ( enqueue)，并且当时机合适时，您希望删除在列表中存在时间最长的元素 ( dequeue)。例如，想象一下在一家时尚且订满的餐厅排队。如果您试图为客人实施公平的座位系统，那么您首先要创建一个队列并在他们到达时添加人员：

>>> from collections import deque
>>> queue = deque()
>>> queue
deque([])

>>> queue.append("Mary")
>>> queue.append("John")
>>> queue.append("Susan")
>>> queue
deque(['Mary', 'John', 'Susan'])

现在，队列中有 Mary、John 和 Susan。请记住，由于队列是先进先出的，第一个进入队列的人应该最先出去。

现在想象一下，随着时间的流逝，有几张桌子可用。在此阶段，您希望以正确的顺序从队列中删除人员。这是你将如何做到这一点：

>>> queue.popleft()
'Mary'

>>> queue
deque(['John', 'Susan'])

>>> queue.popleft()
'John'

>>> queue
deque(['Susan'])

每次调用 时popleft()，都会从链表中删除头元素，模拟现实生活中的队列。

堆栈

如果你想创建一个堆栈呢？嗯，这个想法或多或少与队列相同。唯一的区别是堆栈使用 LIFO 方法，这意味着要插入堆栈的最后一个元素应该是第一个被删除的元素。

想象一下，您正在创建一个 Web 浏览器的历史记录功能，其中存储用户访问的每个页面，以便他们可以轻松地回到过去。假设这些是随机用户在浏览器上执行的操作：

1. 访问Real Python 的网站
2. 导航到Pandas：如何读写文件
3. 单击用于在 Python 中读取和写入 CSV 文件的链接

如果您想将此行为映射到堆栈中，则可以执行以下操作：

>>> from collections import deque
>>> history = deque()

>>> history.appendleft("https://realpython.com/")
>>> history.appendleft("https://realpython.com/pandas-read-write-files/")
>>> history.appendleft("https://realpython.com/python-csv/")
>>> history
deque(['https://realpython.com/python-csv/',
       'https://realpython.com/pandas-read-write-files/',
       'https://realpython.com/'])

在此示例中，您创建了一个空history对象，并且每次用户访问新站点时，您都​​使用 将其添加到history变量中appendleft()。这样做可以确保每个新元素都添加到head链表的 中。

现在假设用户阅读完这两篇文章后，他们想返回 Real Python 主页选择一篇新文章阅读。知道您有一个堆栈并希望使用 LIFO 删除元素，您可以执行以下操作：

>>> history.popleft()
'https://realpython.com/python-csv/'

>>> history.popleft()
'https://realpython.com/pandas-read-write-files/'

>>> history
deque(['https://realpython.com/'])

你去吧！使用popleft()，您从head链表的 中删除元素，直到您到达 Real Python 主页。

从上面的示例中，您可以看到它collections.deque在您的工具箱中是多么有用，因此请确保在下次您需要解决基于队列或堆栈的挑战时使用它。

如何创建链接列表

首先，创建一个类来表示您的链表：

class LinkedList:
    def __init__(self):
        self.head = None

您需要为链表存储的唯一信息是列表的开始位置（head列表的位置）。接下来，创建另一个类来表示链表的每个节点：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

在上面的类定义中，您可以看到每个节点的两个主要元素：data和next。您还可以__repr__向两个类添加，以获得更有用的对象表示：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return self.data

class LinkedList:
    def __init__(self):
        self.head = None

    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)

看一下使用上述类快速创建具有三个节点的链表的示例：

>>> llist = LinkedList()
>>> llist
None

>>> first_node = Node("a")
>>> llist.head = first_node
>>> llist
a -> None

>>> second_node = Node("b")
>>> third_node = Node("c")
>>> first_node.next = second_node
>>> second_node.next = third_node
>>> llist
a -> b -> c -> None

通过定义节点的data和next值，您可以非常快速地创建链表。这些LinkedList和Node类是我们实现的起点。从现在开始，一切都是为了增加它们的功能。

下面是对链表的一个小改动，__init__()它允许您使用一些数据快速创建链表：

def __init__(self, nodes=None):
    self.head = None
    if nodes is not None:
        node = Node(data=nodes.pop(0))
        self.head = node
        for elem in nodes:
            node.next = Node(data=elem)
            node = node.next

通过上述修改，创建用于以下示例的链表将更快。

如何遍历链表

您将使用链表做的最常见的事情之一是遍历它。遍历意味着遍历每个节点，从head链表的开始，到next值为的节点结束None。

遍历只是一种更高级的迭代方式。因此，考虑到这一点，创建一个__iter__以将相同的行为添加到链表中，这与您对普通列表的期望相同：

def __iter__(self):
    node = self.head
    while node is not None:
        yield node
        node = node.next

上面的方法遍历列表并产生每个节点。对此要记住的最重要的事情__iter__是，您需要始终验证当前node不是None。当该条件为 时True，表示您已到达链接列表的末尾。

在产生当前节点后，您想移动到列表中的下一个节点。这就是为什么你添加node = node.next. 这是遍历随机列表并打印每个节点的示例：

>>> llist = LinkedList(["a", "b", "c", "d", "e"])
>>> llist
a -> b -> c -> d -> e -> None

>>> for node in llist:
...     print(node)
a
b
c
d
e

在其他文章中，您可能会看到将遍历定义为名为 的特定方法traverse()。但是，使用 Python 的内置方法来实现上述行为会使这个链表实现更加Pythonic。

在开头插入

在列表的开头插入一个新节点可能是最直接的插入，因为您不必遍历整个列表来执行此操作。这一切都是关于创建一个新节点，然后head将列表的 指向它。

看看add_first()类的以下实现LinkedList：

def add_first(self, node):
    node.next = self.head
    self.head = node

在上面的示例中，您设置self.head为next新节点的引用，以便新节点指向旧self.head. 之后，您需要声明head列表的新节点是插入的节点。

以下是示例列表的行为方式：

>>> llist = LinkedList()
>>> llist
None

>>> llist.add_first(Node("b"))
>>> llist
b -> None

>>> llist.add_first(Node("a"))
>>> llist
a -> b -> None

如您所见，add_first()始终将节点添加到head列表的 ，即使列表之前为空。

最后插入

在链表末尾插入一个新节点会强制您首先遍历整个链表，并在到达末尾时添加新节点。您不能像使用普通列表那样直接附加到末尾，因为在链表中您不知道哪个节点是最后一个。

下面是将节点插入到链表末尾的函数的示例实现：

def add_last(self, node):
    if self.head is None:
        self.head = node
        return
    for current_node in self:
        pass
    current_node.next = node

首先，您要遍历整个列表，直到到达末尾（即，直到for循环引发StopIteration异常）。接下来，您要将 设置current_node为列表中的最后一个节点。最后，您想添加新节点作为nextthat的值current_node。

下面是一个add_last()在行动的例子：

>>> llist = LinkedList(["a", "b", "c", "d"])
>>> llist
a -> b -> c -> d -> None

>>> llist.add_last(Node("e"))
>>> llist
a -> b -> c -> d -> e -> None

>>> llist.add_last(Node("f"))
>>> llist
a -> b -> c -> d -> e -> f -> None

在上面的代码，你用四个值创建列表开始（a，b，c和d）。然后，当您使用 添加新节点时add_last()，您可以看到这些节点始终附加到列表的末尾。

在两个节点之间插入

在两个节点之间插入为链表已经很复杂的插入增加了另一层复杂性，因为您可以使用两种不同的方法：

1. 在现有节点之后插入
2. 在现有节点之前插入

将它们分成两种方法似乎很奇怪，但是链接列表的行为与普通列表不同，并且您需要针对每种情况使用不同的实现。

这是在具有特定数据值的现有节点之后添加节点的方法：

def add_after(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    for node in self:
        if node.data == target_node_data:
            new_node.next = node.next
            node.next = new_node
            return

    raise Exception("Node with data '%s' not found" % target_node_data)

在上面的代码中，您正在遍历链表以查找带有数据的节点，该数据指示要在何处插入新节点。当您找到要查找的节点时，您将立即在它之后插入新节点并重新连接next引用以保持列表的一致性。

唯一的例外是如果列表为空，从而无法在现有节点之后插入新节点，或者列表不包含您要搜索的值。以下是一些add_after()行为方式的示例：

>>> llist = LinkedList()
>>> llist.add_after("a", Node("b"))
Exception: List is empty

>>> llist = LinkedList(["a", "b", "c", "d"])
>>> llist
a -> b -> c -> d -> None

>>> llist.add_after("c", Node("cc"))
>>> llist
a -> b -> c -> cc -> d -> None

>>> llist.add_after("f", Node("g"))
Exception: Node with data 'f' not found

尝试add_after()在空列表上使用会导致异常。当您尝试在不存在的节点之后添加时，也会发生同样的情况。其他一切都按预期工作。

现在，如果你想实现add_before()，那么它看起来像这样：

 1def add_before(self, target_node_data, new_node):
 2    if self.head is None:
 3        raise Exception("List is empty")
 4
 5    if self.head.data == target_node_data:
 6        return self.add_first(new_node)
 7
 8    prev_node = self.head
 9    for node in self:
10        if node.data == target_node_data:
11            prev_node.next = new_node
12            new_node.next = node
13            return
14        prev_node = node
15
16    raise Exception("Node with data '%s' not found" % target_node_data)

在执行上述操作时，需要记住一些事项。首先，与 一样add_after()，如果链表为空（第 2 行）或您要查找的节点不存在（第 16 行），您要确保引发异常。

其次，如果您尝试在列表的头部（第 5 行）之前添加一个新节点，那么您可以重用，add_first()因为您插入的节点将是head列表中的新节点。

最后，对于任何其他情况（第 9 行），您应该使用prev_node变量跟踪最后检查的节点。然后，当您找到目标节点时，您可以使用该prev_node变量重新连接next值。

再一次，一个例子胜过千言万语：

>>> llist = LinkedList()
>>> llist.add_before("a", Node("a"))
Exception: List is empty

>>> llist = LinkedList(["b", "c"])
>>> llist
b -> c -> None

>>> llist.add_before("b", Node("a"))
>>> llist
a -> b -> c -> None

>>> llist.add_before("b", Node("aa"))
>>> llist.add_before("c", Node("bb"))
>>> llist
a -> aa -> b -> bb -> c -> None

>>> llist.add_before("n", Node("m"))
Exception: Node with data 'n' not found

使用add_before()，您现在拥有了在列表中任意位置插入节点所需的所有方法。

使用高级链表

到目前为止，您一直在学习一种称为单向链表的特定类型的链表。但是有更多类型的链表可用于略有不同的目的。

结论

在这篇文章中，你学到了很多东西！最重要的是：

• 什么是链表以及何时应该使用它们
• 如何使用collections.deque实现队列和栈
• 如何实现自己的链表和节点类，以及相关方法
• 其他类型的链表是什么以及它们的用途

如果您想了解有关链表的更多信息，请查看Vaidehi Joshi 的 Medium 帖子以获得一个很好的视觉解释。如果您对更深入的指南感兴趣，那么维基百科文章非常详尽。最后，如果您对 的当前实现背后的推理感到好奇collections.deque，请查看Raymond Hettinger 的线程。