河小马
除了 数组，链表 是一种非常常见的线性 数据结构。它们与数组类似，但数据的存储和访问方式有所不同。此外，链表的应用与数组的应用也有所不同。在本文中，我们将快速解释链表是什么，并深入探讨它们在计算机科学和日常生活中的应用。
链表是什么？
链表与数组类似，但它们不会连续存储元素。相反，它们将每个元素存储在一个节点中，每个节点与一个“下一个”指针相关联。这些指针指向下一个节点，使链表具有方向。指针也用于访问每个元素，而不是使用索引。这样做的一个优点是，链表可以在运行时动态修改，这意味着我们可以随时添加和删除元素。
不同类型的链表有哪些？
虽然基本结构（称为单链表）相当简单，但该结构还有一些更复杂的版本。这些版本包括双向链表、循环链表、双向循环链表、跳跃链表、展开链表和自适应链表。下面将对它们进行描述，并介绍它们的应用。
单链表
如前所述，单链表通过指针将连续节点链接在一起。这样可以轻松添加和删除元素，而无需重新组织整个列表。尽管该结构相当基本，但在许多情况下，单链表是合适的选择。这些情况包括：
- 实现动态数据结构和 哈希表。当我们需要动态结构（例如堆栈或 队列）时，链表是实现这一目标的最简单方法之一。它们还可以用于实现哈希表，以防止具有相同索引的元素之间的冲突。
- 撤消/重做 – 因为我们可以在进行操作时存储应用程序的状态，所以我们可以使用链表来撤消和重做以前完成的操作。
- gps系统 – 类似地，链表可用于存储地标和方向。如果将它们表示为节点，我们可以使用它们来导航。
- 组织文件 – 这些链表还可以用于组织目录中的文件结构。文件和目录都可以由一个节点表示，并且可以指向相关的文件或目录。
- 多项式操作 – 我们使用每个节点来表示多项式，多项式是包含变量和系数的表达式，例如 3x2 + 2x – 1。我们可以使用链表高效地修改这些多项式。
- 表示图 – 通过使用节点作为顶点，我们可以使用链表表示图结构。
示例
下面是python中单链表的示例实现：
class node:
def __init__(self, data):
self.data = data
self.next = none
self.previous = none
class doublylinkedlist:
def __init__(self):
self.head = none
def append(self, data):
new_node = node(data)
if self.head is none:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.previous = current
def display(self):
if self.head is none:
print("linked list is empty.")
else:
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("none")
my_list = doublylinkedlist()
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.display()我们定义了“node”和“doublylinkedlist”类以及“append()”方法，该方法用于向列表中添加元素。如果列表为空，则新节点成为头节点。否则，头节点指向下一个节点。添加了3个元素，并且列表将如图所示显示。
在python中实现了单向链表。
©jingzhengli.com
双向链表
与单向链表只有一种方向不同，双向链表是双向的。这是通过使用额外的“previous”指针来实现的，它指向列表中的前一个节点。这使得我们可以在正向和反向方向上遍历列表，这在特定应用中更为适用。双向链表的应用包括：
- 在列表的两端插入和删除元素。
- 实现数据结构，如双端队列和链表。
- 撤消/重做 – 在使用单向链表时，我们必须使用堆栈结构来跟踪更改。而在使用双向链表时，不需要，因为我们可以在两个方向上遍历。
- 浏览器 – 因为可以在两个方向上遍历，所以可以使用双向链表允许用户在其网页历史记录中向前和向后导航。
- 幻灯片放映 – 将每个图像表示为一个节点，可以轻松地在图像之间移动。
- 管理缓存 – 通过将最近查看的项目保持在头部附近，一旦缓存已满，就可以删除旧项目。
- 文字处理 – 可以将一些文本部分表示为一个节点，例如一行，并使用此结构来编辑我们的文本。
- 播放音乐 – 在使用播放列表时，我们经常使用双向链表来允许用户切换歌曲。
- 进程调度 – 操作系统通常使用此结构来管理活动进程。
示例
对于一个简单的双向链表实现，考虑以下代码：
class node:
def __init__(self, data):
self.data = data
self.prev = none
self.next = none
class doublylinkedlist:
def __init__(self):
self.head = none
def is_empty(self):
return self.head is none
def insert_at_beginning(self, data):
new_node = node(data)
if self.is_empty():
self.head = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = node(data)
if self.is_empty():
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display(self):
if self.is_empty():
print("双向链表为空。")
else:
current = self.head
while current:
print(current.data, end=" ")
current = current.next
print()
def display_reverse(self):
if self.is_empty():
print("双向链表为空。")
else:
current = self.head
while current.next:
current = current.next
while current:
print(current.data, end=" ")
current = current.prev
print()
dll = doublylinkedlist()
dll.insert_at_beginning(10)
dll.insert_at_beginning(20)
dll.insert_at_end(30)
dll.insert_at_end(40)
dll.display()
dll.display_reverse()我们像之前一样定义了节点和链表类，但这次还加入了一个前一个指针。根据添加元素的位置不同，我们有不同的代码。如果在开头添加元素，将新节点的下一个指针设置为头节点，并将头节点的前一个指针设置为新节点，新节点成为头节点。如果我们将元素添加到末尾，就将尾节点的下一个指针更新为新节点，并将新节点的前一个指针更新为尾节点。然后我们按正序和逆序打印链表，如图片所示。
一个双向链表在程序中被实现。
©jingzhengli.com
循环链表
这些链表没有定义的起点和终点，因为尾节点会环绕到头节点。因此，它们在需要循环行为时使用。循环链表的应用包括：
- 实现循环队列 – 链表的结构自然适用于循环队列，最早进入的元素将首先被移除。
- 轮转调度 – 这是一种类型的调度，每个进程被分配一个固定的时间。这样，每个进程都有平等的机会被执行，并且按顺序进行循环。
- 多人游戏 – 循环链表在这里可以用于许多事情，如维护玩家轮换、发送消息、同步玩家和在加入会话时匹配玩家。
- 缓冲 – 循环链表可用于管理缓冲区中的数据，因为数据可以被删除而无需重新排列其他元素。
例子
下面是如何在python中实现一个简单的循环链表。
class node:
def __init__(self, data):
self.data = data
self.next = none
class circularlinkedlist:
def __init__(self):
self.head = none
def is_empty(self):
return self.head is none
def insert_at_beginning(self, data):
new_node = node(data)
if self.is_empty():
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
self.head = new_node
def insert_at_end(self, data):
new_node = node(data)
if self.is_empty():
new_node.next = new_node
self.head = new_node
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def display(self):
if self.is_empty():
print("循环链表为空。")
else:
current = self.head
while true:
print(current.data, end=" ")
current = current.next
if current == self.head:
break
print()
cll = circularlinkedlist()
cll.insert_at_beginning(10)
cll.insert_at_beginning(20)
cll.insert_at_end(30)
cll.insert_at_end(40)
cll.display()
循环链表用于需要循环行为的情况。
©jingzhengli.com
双向循环链表
正如您现在可能已经猜到的那样，双向循环链表是既循环又双向的。它们在之前讨论的链表中有许多相同的应用场景，包括音乐播放器、撤销/重做操作、浏览器历史记录、任务调度、幻灯片演示和文本编辑器。双向循环链表在这些场景中通常提供更多的优势。它们还有一些独特的应用场景，比如：
- 图像处理 – 我们可以使用这些链表进行更高效的图像处理，因为我们可以利用相邻像素的信息。
- 窗口管理 – 当我们需要循环浏览窗口或重新排序窗口时，这种类型的链表很有用。
- 链式哈希表 – 链式哈希表将哈希表与链表的特性结合起来。双向循环链表在这里经常被使用，以便进行灵活的操作。
示例
下面是使用双向循环链表的一个示例。
class node:
def __init__(self, data):
self.data = data
self.next = none
self.prev = none
class doublycircularlinkedlist:
def __init__(self):
self.head = none
def is_empty(self):
return self.head is none
def insert_at_beginning(self, data):
new_node = node(data)
if self.is_empty():
new_node.next = new_node
new_node.prev = new_node
self.head = new_node
else:
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev.next = new_node
self.head.prev = new_node
self.head = new_node
def insert_at_end(self, data):
new_node = node(data)
if self.is_empty():
new_node.next = new_node
new_node.prev = new_node
self.head = new_node
else:
new_node.next = self.head
new_node.prev = self.head.prev
self.head.prev.next = new_node
self.head.prev = new_node
def display(self):
if self.is_empty():
print("列表为空。")
return
current = self.head
while true:
print(current.data, end=" ")
current = current.next
if current == self.head:
break
print()
dllist = doublycircularlinkedlist()
dllist.insert_at_beginning(3)
dllist.insert_at_beginning(7)
dllist.insert_at_beginning(1)
dllist.display()
dllist.insert_at_end(9)
dllist.insert_at_end(5)
dllist.display()作为一种双向链表和循环链表的组合，其过程类似。当在前面添加另一个元素时，新节点的next指针指向头节点，前一个指针设置为头节点原本指向的位置，头节点的下一个节点指向新节点，新节点成为头节点。
要在末尾添加元素，新节点的next指针设置为头节点。然后，前一个指针设置为头节点的前一个节点，头节点的前一个节点的下一个节点指向新节点，头节点的前一个指针指向新节点。可以在图中看到这一点。
python实现的双向循环链表示例。
©jingzhengli.com
跳跃表
一种更复杂的链表类型是跳跃表。这是一种分层结构，由多个链表组成。通常，我们有一个包含排序元素的列表和其他一些包含其中一些元素的列表。这些列表是随机选择的，某些元素被“跳过”，因此得名。主要优点在于更高效的操作。该结构允许具有对数时间复杂度，因为我们不需要遍历列表中的所有元素。因此，跳跃表用于索引数据库，实现字典，管理缓存以及键值对。
示例
这是一个相对复杂的列表实现，但下面是一个相对简单的示例：
导入随机模块
class node:
def __init__(self, key, level):
self.key = key
self.next_nodes = [none] * (level + 1)
class customskiplist:
def __init__(self, max_level, probability):
self.max_level = max_level
self.probability = probability
self.header = self.create_node(self.max_level, -1)
self.level = 0
def create_node(self, level, key):
new_node = node(key, level)
return new_node
def random_level(self):
level = 0
while random.random() < self.probability and level < self.max_level:
level += 1
return level
def insert_element(self, key):
update_nodes = [none] * (self.max_level + 1)
current_node = self.header
for i in range(self.level, -1, -1):
while current_node.next_nodes[i] and current_node.next_nodes[i].key self.level:
for i in range(self.level + 1, new_level + 1):
update_nodes[i] = self.header
self.level = new_level
new_node = self.create_node(new_level, key)
for i in range(new_level + 1):
new_node.next_nodes[i] = update_nodes[i].next_nodes[i]
update_nodes[i].next_nodes[i] = new_node
print(“成功插入关键字: {}”.format(key))
def display_list(self):
print(“n***** 自定义跳表 ******”)
current_level = self.level
header_node = self.header
for level in range(current_level + 1):
print(“层级 {}: “.format(level), end=””)
node = header_node.next_nodes[level]
while node is not none:
print(node.key, end=” “)
node = node.next_nodes[level]
print(“”)
def main():
custom_list = customskiplist(3, 0.5)
custom_list.insert_element(5)
custom_list.insert_element(2)
custom_list.insert_element(8)
custom_list.insert_element(3)
custom_list.display_list()
main()
如何在程序中实现跳表。
©jingzhengli.com
未满列表
这是一种在单个节点中存储多个元素的列表类型。通常这样做是为了使信息更加局部化，从而可能加快像顺序访问数据和查询范围这样的操作。然而，某些操作，例如插入和删除元素，可能不那么高效，因为我们可能需要拆分节点并重新排列它们。未满列表可能有优势，但通常只有在高级缓存性能和减少内存使用量优于复杂操作的减速时才会使用。因此，它们的使用比其他类型更加深思熟虑。
示例
为了了解未满列表的工作原理，考虑以下代码块：
class unrolledlistnode:
def __init__(self, capacity):
self.capacity = capacity
self.elements = [none] * capacity
self.next = none
class unrolledlist:
def __init__(self, node_capacity):
self.node_capacity = node_capacity
self.head = none
def insert(self, value):
if self.head is none:
self.head = unrolledlistnode(self.node_capacity)
self.head.elements[0] = value
return
current = self.head
while current.next is not none:
current = current.next
if none in current.elements:
index = current.elements.index(none)
current.elements[index] = value
elif len(current.elements) < current.capacity:
current.elements.append(value)
else:
new_node = unrolledlistnode(self.node_capacity)
new_node.elements[0] = value
current.next = new_node
def display(self):
current = self.head
while current is not none:
print(current.elements)
current = current.next
ulist = unrolledlist(3)
ulist.insert(5)
ulist.insert(2)
ulist.insert(8)
ulist.insert(3)
ulist.display()这段代码与单链表有些相似。但是我们多了一个属性”capacity”。当添加一个新元素时，我们还会检查最后一个元素的值。如果有任何值被设置为”none”，则更新为新值。否则，创建一个新的节点，并在此处分配值。下面是使用示例的图片。
通过程序演示了非卷曲列表的工作原理。
©duncan dodsworth/shutterstock.com
自适应列表
这种类型也被称为前移列表，因为元素的重新排列取决于它们的访问顺序。在被访问后，它们被移动到列表的前面。这可以提高效率，因为最常使用的元素保持在列表的开头附近。虽然在需要维护元素顺序时这可能无用，但它可以加速操作，如web缓存、文件系统甚至搜索算法。
示例
这段代码给出了一个自适应列表的简短示例。
class selfadjustinglist:
def __init__(self):
self.items = []
def insert(self, item):
if item in self.items:
self.items.remove(item)
self.items.append(item)
def search(self, item):
if item in self.items:
self.items.remove(item)
self.items.append(item)
return true
return false
def remove(self, item):
if item in self.items:
self.items.remove(item)
def display(self):
print(self.items)
sa_list = selfadjustinglist()
sa_list.insert(5)
sa_list.insert(2)
sa_list.insert(8)
sa_list.insert(3)
sa_list.display()
print(sa_list.search(5))
sa_list.display()
sa_list.remove(2)
sa_list.display()在搜索元素时，将位置更改为列表的末尾，以保持自适应行为。我们向列表中添加了一些项目，搜索了一个元素，并删除了一个元素。您可以在图片中看到输出结果。
演示如何实现自适应列表的程序。
©jingzhengli.com
总结
链表是最常用的数据结构之一，具有许多应用。它们主要用于管理数据库、网页、缓存和文件系统。但它们也用于交通信号灯系统、音乐播放器、数据缓冲和实现各种复杂的数据结构。每当我们处理复杂的数据集并且需要动态行为时，很可能某种形式的链表将帮助我们更高效地访问和修改数据。虽然有些操作可能会有额外的开销，但是当我们谨慎使用时，链表可以提高性能。
