理解Python中链表的实现
数据结构在编程领域中起着关键作用。它们帮助我们以高效的方式组织数据。
在本教程中，我们将学习单链表和双链表。
链表是一种线性数据结构。它不像数组那样在连续的内存位置中存储数据。链表中的每个元素被称为节点，它们使用指针连接在一起。链表中的第一个节点称为头节点。
链表的大小是动态的。因此，我们可以拥有任意数量的节点，只要设备上有足够的存储空间。
链表有两种类型。让我们逐个详细了解它们。
#1. 单链表
单链表包含一个连接到链表中的下一个节点的单个指针。我们必须为链表中的每个节点存储数据和指针。
链表中的最后一个节点包含null作为下一个指针，表示链表的结束。
您可以看到下图是链表的示意图。
现在，我们对单链表有了完整的理解。让我们看看如何在Python中实现它的步骤。
单链表实现
1. 第一步是为链表创建节点。
如何创建它？
在Python中，我们可以轻松地使用类创建节点。该类包含数据和指向下一个节点的指针。
请看节点的代码。
class Node:
def __init__(self, data):
## 节点的数据
self.data = data
## 下一个指针
self.next = None我们可以使用上面的类创建任何类型的节点。稍后我们会看到。
现在，我们已经拥有了节点。接下来，我们必须创建一个具有多个节点的链表。让我们为链表创建另一个类。
2. 创建一个名为LinkedList的类，其中头节点初始化为None。请参考下面的代码。
class LinkedList:
def __init__(self):
## 初始化头节点为None
self.head = None3. 我们有Node和LinkedList类。我们如何将新节点插入链表？简单的答案可能是使用LinkedList类中的方法。是的，那会很好。让我们编写一个方法将新节点插入链表。
为了将新节点插入链表中，我们必须按照一定的步骤进行。
让我们看看这些步骤。
- 检查头节点是否为空。
- 如果头节点为空，则将新节点赋值给头节点。
- 如果头节点不为空，则获取链表的最后一个节点。
- 将新节点赋值给最后一个节点的下一个指针。
让我们看一下将新节点插入链表的代码。
class LinkedList:
####
def insert(self, new_node):
## 检查头节点是否为空
if self.head:
## 获取最后一个节点
last_node = self.head
while last_node != None:
last_node = last_node.next
## 将新节点赋值给最后一个节点的下一个指针
last_node.next = new_node
else:
## 头节点为空
## 将节点赋值给头节点
self.head = new_node太棒了！我们已经完成了将新节点插入链表的方法。我们如何从链表中访问节点数据？
要访问链表中的数据，我们必须通过使用“next指针”来迭代遍历链表，就像在插入方法中获取最后一个节点一样。让我们在LinkedList类中编写一个方法来打印链表中所有节点的数据。
4. 按照以下步骤打印链表中的所有节点数据。
– 使用“head”初始化一个变量。
– 编写一个循环，直到我们到达链表的末尾。
– 打印节点数据。
– 移动到下一个指针。
让我们看看代码。
“`python
class LinkedList:
####
def display(self):
## 变量用于迭代
temp_node = self.head
## 迭代直到达到链表的末尾
while temp_node != None:
## 打印节点数据
print(temp_node.data, end='->')
## 移动到下一个节点
temp_node = temp_node.next
print(‘Null')
“`
我们完成了创建带有必要方法的链表。让我们通过实例化一些数据来测试链表。
我们可以使用`Node(1)`代码创建节点。让我们看看链表实现的完整代码以及示例用法。
“`python
class Node:
def __init__(self, data):
## 节点的数据
self.data = data
## 下一个指针
self.next = None
class LinkedList:
def __init__(self):
## 将头部初始化为None
self.head = None
def insert(self, new_node):
## 检查头是否为空
if self.head:
## 获取最后一个节点
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## 将新节点分配给最后一个节点的下一个指针
last_node.next = new_node
else:
## 头部为空
## 将节点分配给头部
self.head = new_node
def display(self):
## 变量用于迭代
temp_node = self.head
## 迭代直到达到链表的末尾
while temp_node != None:
## 打印节点数据
print(temp_node.data, end='->')
## 移动到下一个节点
temp_node = temp_node.next
print(‘Null')
if __name__ == ‘__main__':
## 实例化链表
linked_list = LinkedList()
## 将数据插入链表
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## 打印链表
linked_list.display()
“`
运行上述程序以获得以下结果。
“`
1->2->3->4->5->6->7->Null
“`
这就是链表的全部内容。现在，你知道如何实现一个单链表。掌握单链表的知识后，你可以很容易地实现双链表。让我们深入下一节教程。
#2. 双链表
双链表包含与前一个节点和后一个节点在链表中连接的“两个指针”。我们必须为链表中的每个节点存储数据和两个指针。
第一个节点的“前一个指针”是null，最后一个节点的“下一个指针”是null，表示双链表在两端结束。
你可以看到下面的链表示例。
双链表的实现与单链表具有相似的步骤。再次解释相同的内容对你来说会很无聊。逐步查看每个步骤中的代码，你会很快理解。让我们开始吧。
双链表实现
1. 使用前一个节点指针、数据和后一个节点指针创建双链表的节点。
class Node:
def __init__(self, data):
## 前一个指针
self.prev = None
## 结点的数据
self.data = data
## 下一个指针
self.next = None2. 双向链表类。
class LinkedList:
def __init__(self):
## 将头结点初始化为None
self.head = None3. 向双向链表插入新结点的方法。
class LinkedList:
####
def insert(self, new_node):
## 检查头结点是否为空
if self.head:
## 获取最后一个结点
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## 将最后一个结点赋给新节点的前一个指针
new_node.prev = last_node
## 将新结点赋给最后一个结点的下一个指针
last_node.next = new_node4. 显示双向链表数据的方法。
class LinkedList:
####
def display(self):
## 正序打印数据
print("正序：", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## 使用前一个指针倒序打印数据
print("倒序：", end='')
## 获取最后一个结点
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()我们已经看到了双向链表的代码。而且这段代码中没有使用双向链表类的代码。这就是留给你的。使用双向链表类与使用单向链表类类似。玩得开心 🙂
结论
你可以找到许多基于链表的问题。但是，你必须知道在本教程中学到的链表的基本实现。希望你在学习这个新概念的过程中度过愉快的时光。
编程愉快 🙂