后端开发教程 - Java、Spring Boot 实战 - msg200.com
[Python🐍精通] Python 中的链表概述和基本链表操作🛠️
在上一篇文章中，我们学习了面向对象编程，并对 Python 的 Magic/Dunder 方法进行了概述。
Python 中的面向对象编程 (OOP)：Python 中的这种范式围绕创建可重用代码展开。它涉及使用类作为对象的蓝图。这些对象可以具有定义其行为和交互的属性（数据）和方法（函数）。
Python 的 Magic/Dunder 方法：Python 中的 Magic 或 Dunder（双下划线）方法是特殊方法，其名称以双下划线开头和结尾（例如__init__，，，__str__）__repr__。
您可以在这里阅读相关内容。👇
今天，我们将对其进行扩展，并利用面向对象编程的知识来理解和创建 Python 中的链表。并对其进行一些操作。
开源 Python 项目：Swirl
如果你对 Python 感兴趣，你一定会喜欢Swirl。Swirl是一个开源搜索平台，它可以让你了解以下内容：
- Python
- 人工智能
- 在任何产品中集成大型语言模型
- 了解如何开发搜索平台。
查看我们的 GitHub 存储库：
GitHub 上的 Swirl
如果您能做到以下几点，我们将非常高兴：
链表
链表是对象的有序集合。它是一种旨在将数据保存在非连续内存块中的数据结构。
与使用连续内存块的数组或传统列表不同，链表存储在非连续的内存位置。这种设计允许高效的插入和删除操作，而无需重新排列整个数据结构。
这种设计允许高效的插入和删除，而无需重新排列整个数据结构。
基本链表
基本链表是一种线性数据结构，其中每个元素（称为节点）包含两部分：数据和对列表中下一个节点的引用。这种结构允许高效地插入和删除元素，因为它不需要像数组那样移动元素。
典型的节点设计：
数据：包含数据，可以是数字、地址、文本等。
下一个：指向下一个数据节点或保存下一个数据节点的地址。
第一个节点称为列表的头，最后一个节点指向 None（在 Python 中）（或在其他语言中为 Null），称为列表的尾。
当你将许多节点收集在一起时，它就变成了一个链表。
链表的优点和操作的时间复杂度
链表有很多好处，尤其是在动态数据操作场景中。以下是一些主要优点：
- 动态大小：与数组不同，链表的大小可以动态增大或缩小，这对于内存使用非常有效。
- 插入/删除的简易性：插入或删除节点相对简单，因为它通常只涉及更改一些引用，而无需像数组那样移动元素。
- 灵活性：它们可以实现其他数据结构，如堆栈、队列和图邻接表。
| 手术 | 时间复杂度 |
|---|---|
| 使用权 | 在） |
| 搜索 | 在） |
| 插入 | O(1) |
| 删除 | O(1) |
注意：我们正在考虑单链表。
在 Python 中实现链表。
这是在 Python 中创建节点的代码。如果您对该__repr__方法感到困惑，请参考本系列的上一篇文章。
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return f"Node({self.data})"
链接列表类的代码。它利用了前面提到的 Node 类来创建数据并将所有内容链接在一起。
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = new_node
def __repr__(self):
nodes = []
current = self.head
while current:
nodes.append(repr(current))
current = current.next
return "->".join(nodes)
这段代码做了两件事：
- 附加：在链接列表的末尾附加一个节点。
__repr__：此方法遍历链接列表并以 Pythonic 方式打印它。- 这也可以通过一种称为遍历的方法来完成。
print(llist)这是调用 ` repr _` 方法的输出：
遍历链接列表。
遍历链表是遍历每个节点并打印它的过程。
def traverse(linked_list):
current = linked_list.head
while current:
print(current.data)
current = current.next
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Traversing the linked list:")
traverse(llist)
反转链接列表
其思路是遍历链表，并针对每个节点，将其next指针切换为指向前一个节点而不是下一个节点。这将帮助我们反转链表。
def reverse_linked_list(head):
previous = None
current = head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
print("Original List:", llist)
new_head = reverse_linked_list(llist.head)
llist.head = new_head
print("Reversed List:", llist)
在链接列表中插入值
我们已经有一个 append 函数，可以将值添加到链表的末尾。但是，如果我们想要一个方法，在特定位置添加值，如果该位置不存在，则将值添加到链表末尾，该怎么办呢？
class LinkedList:
def insert_after_value(self, data_after, data_to_insert):
if self.head is None:
return
current = self.head
while current:
if current.data == data_after:
new_node = Node(data_to_insert)
new_node.next = current.next
current.next = new_node
return
current = current.next
self.append(data_to_insert)
删除链接列表中的节点
要从链表中删除节点，请创建一个函数，该函数以链表的头节点和要删除的节点数据作为参数。遍历链表直到找到数据，然后将其删除。
class LinkedList:
def delete_node(self, data):
current = self.head
if current is None or current.data == data:
self.head = current.next if current else None
return
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
感谢您读到这里。在本系列的后续文章中，我们将讨论 Python 和 Python 数据结构的更复杂细节。
为Swirl做贡献
Swirl是一个开源 Python 项目。为 Swirl 做出贡献可以帮助您获得生产级的 Python 知识并提升您的技能。
查看我们的 GitHub 存储库：
GitHub 上的 Swirl
如果您能做到以下几点，我们将非常高兴：
谢谢阅读，
你们都令人惊叹不已。
