理解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 = None

3. 我们有NodeLinkedList类。我们如何将新节点插入链表?简单的答案可能是使用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 = None

2. 双向链表类。

class LinkedList:

	def __init__(self):
		## 将头结点初始化为None
		self.head = None

3. 向双向链表插入新结点的方法。

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_node

4. 显示双向链表数据的方法。

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()

我们已经看到了双向链表的代码。而且这段代码中没有使用双向链表类的代码。这就是留给你的。使用双向链表类与使用单向链表类类似。玩得开心 🙂

结论

你可以找到许多基于链表的问题。但是,你必须知道在本教程中学到的链表的基本实现。希望你在学习这个新概念的过程中度过愉快的时光。

编程愉快 🙂

类似文章