了解 Python 中的链表实现

数据结构在编程世界中起着关键作用。 它们帮助我们以一种可以有效使用的方式组织我们的数据。

在本教程中,我们将学习单向链表和双向链表。

链表是一种线性数据结构。 它不会将数据存储在像数组这样的连续内存位置。 链接中的每个元素都称为节点,它们使用指针连接。 链表中的第一个节点称为表头。

链表的大小是动态的。 因此,除非设备中的存储可用,否则我们可以拥有任意数量的节点。

有两种类型的链表。 让我们一一查看有关它们的详细教程。

#1。 单链表

单向链表包含连接到链表中下一个节点的单个指针。 我们必须存储链表中每个节点的数据和指针。

链表的最后一个节点包含null作为next指针,表示链表结束。

您可以在下面看到链接的插图。

现在,我们对单向链表有了一个完整的了解。 让我们看看在 Python 中实现它的步骤。

单链表实现

1.第一步是为链表创建节点。

如何创建它?

在 Python 中,我们可以使用类轻松创建节点。 该类包含数据和下一个节点的指针。

查看节点的代码。

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

我们可以使用上述类创建具有任何类型数据的节点。 我们待会儿会看到。

现在,我们有了节点。 接下来,我们必须创建一个包含多个节点的链表。 让我们为链表创建另一个类。

2. 创建一个名为 LinkedList 的类,头部初始化为 None。 请参阅下面的代码。

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

3. 我们有 Node 和 LinkedList 类。 我们如何向链表中插入一个新节点呢? 一个简单的答案可能是使用 LinkedList 类中的方法。 是的,那会很好。 让我们编写一个方法来将一个新节点插入到链表中。

要将新节点插入链表,我们必须遵循某些步骤。

让我们看看他们。

  • 检查头部是否为空。
  • 如果头部为空,则将新节点分配给头部。
  • 如果头部不为空,则获取链表的最后一个节点。
  • 将新节点分配给最后一个节点的下一个指针。

让我们看看在链表中插入新节点的代码。

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

欢呼! 我们已经完成了在链表中插入新节点的方法。 我们如何访问链表中的节点数据?

  霰弹枪农民解锁代码:立即兑换

要访问链表中的数据,我们必须使用 next 指针遍历链接,就像我们在插入方法中获取最后一个节点一样。 让我们在 LinkedList 类中编写一个方法来打印链表中的所有节点数据。

4. 按照以下步骤打印链表中的所有节点数据。

  • 用头初始化一个变量。
  • 编写一个循环,迭代直到我们到达链表的末尾。
    • 打印节点数据。
    • 移动下一个指针

让我们看看代码。

class LinkedList:

	####

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')

呸! 我们用必要的方法完成了链接的创建。 让我们通过用一些数据实例化它来测试链表。

我们可以使用 Node(1) 代码创建节点。 让我们看看链表实现的完整代码以及示例用法。

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

		else:
			## head is empty
			## assigning the node to head
			self.head = new_node

	def display(self):
		## variable for iteration
		temp_node = self.head

		## iterating until we reach the end of the linked list
		while temp_node != None:
			## printing the node data
			print(temp_node.data, end='->')

			## moving to the next node
			temp_node = temp_node.next

		print('Null')


if __name__ == '__main__':
	## instantiating the linked list
	linked_list = LinkedList()

	## inserting the data into the linked list
	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))

	## printing the linked list
	linked_list.display()

运行上面的程序得到如下结果。

1->2->3->4->5->6->7->Null

链表就是这样。 现在,您知道如何实现单链表了。 有了单向链表的知识,你就可以很容易地实现双向链表。 让我们深入教程的下一部分。

  修复 PowerPoint 不保存文件错误

#2。 双向链表

双链表包含两个指向链表中的前一个节点和下一个节点的指针。 我们必须为链表中的每个节点存储数据和两个指针。

第一个节点的previous指针为null,最后一个节点的next指针为null,表示两边链表结束。

您可以在下面看到链接的插图。

双向链表在实现上也和单向链表有类似的步骤。 再次解释同样的事情对你来说会很无聊。 把每一步的代码都过一遍,你会很快理解的。 我们走吧。

双向链表实现

1.为双向链表创建一个节点,前一个节点指针,数据,下一个节点指针。

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2.双向链表类。

class LinkedList:

	def __init__(self):
		## initializing the head with None
		self.head = None

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

class LinkedList:

	####

	def insert(self, new_node):
		## check whether the head is empty or not
		if self.head:
			## getting the last node
			last_node = self.head
			while last_node.next != None:
				last_node = last_node.next

			## assigning the last node to the previous pointer of the new node
			new_node.prev = last_node

			## assigning the new node to the next pointer of last node
			last_node.next = new_node

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

class LinkedList:

	####

	def display(self):

		## printing the data in normal order
		print("Normal Order: ", end='')

		temp_node = self.head
		while temp_node != None:
			print(temp_node.data, end=' ')
			temp_node = temp_node.next
		print()

		## printing the data in reverse order using previous pointer
		print("Reverse Order: ", end='')

		## getting the last node
		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()

我们已经看到了双向链表的代码。 并且没有使用双向链表类的代码。 那是给你的。 使用类似于单链表的双向链表类。 玩得开心🙂

  如何将 PayPal 帐户从企业更改为个人

结论

你可以根据链表找到很多问题。 但是,您必须了解您在本教程中学到的链接的基本实现。 希望您在学习新概念时玩得开心。

快乐编码🙂