链表是一种线性数据结构,其中元素不存储在连续位置,而是使用指针链接。链表形成一系列相连的节点,每个节点存储数据和下一个节点的地址。
节点结构:链表中的节点通常由两个组件组成: 数据:它保存与该节点关联的实际值或数据。 下一个指针:它存储序列中下一个节点的内存地址(引用)。 头尾:链表通过头节点访问,头节点指向链表中的第一个节点。链表的最后一个节点指向NULL或nullptr,表示链表的结尾。该节点称为尾节点。
下面列出了链表的一些优点,它将帮助您理解为什么有必要了解它。
在系统中,如果我们在数组 id[] = [1000, 1010, 1050, 2000, 2040] 中维护一个有序的 ID 列表。 如果我们想插入一个新的ID 1005,那么为了保持排序顺序,我们必须移动1000之后的所有元素(不包括1000)。 除非使用一些特殊技术,否则数组的删除成本也很高。例如,要删除 id[] 中的 1010,则必须移动 1010 之后的所有内容,因为要做的工作太多,影响了代码的效率。
链表主要有以下三种类型:
在单链表中,每个节点都包含对序列中下一个节点的引用。遍历单链表是向前完成的。
单链表
# 节点类
class Node:
#初始化节点对象的函数
def __init__(self, data):
self.data = data # 分配数据
self.next = None # 将 next 初始化为空
# 链接列表类
class LinkedList:
#初始化链表对象的函数
def __init__(self):
self.head = None
在双向链表中,每个节点都包含对下一个和前一个节点的引用。这允许向前和向后两个方向遍历,但需要额外的内存用于向后引用。
双链表
# 双向链表的节点
class Node:
def __init__(self, next=None, prev=None, data=None):
self.next = next # 双向链表中指向下一个节点的引用
self.prev = prev # 双向链表中的上一个节点引用
self.data = data
在循环链表中,最后一个节点指向头节点,形成循环结构。它可以是单链或双链。
循环链表
给定一个链表,任务是在这个给定的链表中的以下位置插入一个新节点:
方法:
要在链表的开始/开始/前面插入一个节点,我们需要:
下面是该方法的实现:
#这个函数在LinkedList类中
#在开头插入一个新节点的函数
def push(self, new_data):
#1和2:分配节点和
#放入数据
new_node = Node(new_data)
# 3. 将新节点的下一个指向头部
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node