【数据结构2】链表(使用头插法和尾插法创建链表)、链表的插入和删除、双链表节点的插入、双链表节点的删除

ops/2024/9/23 10:20:09/

1 链表
1.2 使用头插法和尾插法创建链表
2 链表的插入和删除
3 双链表
3.1 双链表节点的插入
3.2 双链表节点的删除

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。
通过节点之间的相互连接最终串联成一个链表。

在这里插入图片描述

class Node:def __init__(self, item=None):self.item = item  # 存储节点的数据self.next = None  # 指向下一个节点的指针，初始为 None# a = Node(1)
# b = Node(2)
# c = Node(3)
# a.next = b
# b.next = c
#
# print(a.next.next.item)

在这里插入图片描述

def create_link_list_head(li: list):"""使用头插法创建链表头插法的特点是新节点总是插入到链表的头部，因此链表的顺序会与原始列表相反。:param li: 包含要插入的元素的列表:return: 链表的头节点"""head = Node(li[0])  # 初始化链表的头节点for element in li[1:]:  # 从列表的第二个元素开始遍历node = Node(element)  # 创建一个新的节点node.next = head  # 新节点的 next 指向当前的头节点head = node  # 更新头节点为新创建的节点return head  # 返回新链表的头节点def create_link_list_tail(li: list):"""使用尾插法创建链表尾插法的特点是新节点总是插入到链表的尾部，因此链表的顺序与原始列表相同。:param li: 包含要插入的元素的列表:return: 链表的头节点"""head = Node(li[0])  # 初始化链表的头节点tail = head  # 初始化尾节点为头节点for element in li[1:]:  # 从列表的第二个元素开始遍历node = Node(element)  # 创建一个新的节点tail.next = node  # 当前尾节点的 next 指向新节点tail = node  # 更新尾节点为新创建的节点return head  # 返回链表的头节点def print_link_list(lk):"""打印链表中的所有节点从链表的头节点开始，逐个打印每个节点的值，直到链表的末尾。:param lk: 链表的头节点"""while lk:  # 当当前节点不为 None 时继续循环print(lk.item, end=',')  # 打印当前节点的值，并在末尾加上逗号lk = lk.next  # 将当前节点更新为下一个节点lk = create_link_list_head([1, 23, 33])
# lk = create_link_list_tail([1, 23, 33, 44])
print_link_list(lk)

2 链表的插入和删除

在这里插入图片描述

链表节点的插入 把4查到1和2中间

在这里插入图片描述
链表节点的插入可以分为几种常见情况：
在链表的头部插入节点、在链表的尾部插入节点、以及在链表的中间某个位置插入节点。

1. 在链表头部插入节点

在链表头部插入节点，也称为头插法，操作相对简单。新节点会成为链表的第一个节点，原来的头节点将成为第二个节点。

class Node:def __init__(self, item=None):self.item = item  # 存储节点的数据self.next = None  # 指向下一个节点的指针def insert_at_head(head: Node, item) -> Node:"""在链表头部插入新节点:param head: 链表的头节点:param item: 要插入的新数据:return: 新的头节点"""new_node = Node(item)  # 创建一个新的节点new_node.next = head  # 新节点的 next 指向当前的头节点return new_node  # 新节点现在成为头节点，返回它

2. 在链表尾部插入节点

在链表尾部插入节点，也称为尾插法。你需要遍历链表，找到当前最后的节点，并将新节点插入到它的后面。

def insert_at_tail(head: Node, item) -> Node:"""在链表尾部插入新节点:param head: 链表的头节点:param item: 要插入的新数据:return: 链表的头节点"""new_node = Node(item)  # 创建一个新的节点if head is None:  # 如果链表为空，直接返回新节点作为头节点return new_nodetail = headwhile tail.next:  # 遍历链表找到最后的节点tail = tail.nexttail.next = new_node  # 将新节点插入到最后的节点后面return head  # 返回头节点

3. 在链表中间插入节点

在链表中间插入节点需要指定插入的位置。你需要遍历链表找到合适的位置，然后将新节点插入到它的前驱节点之后。

def insert_at_position(head: Node, item, position: int) -> Node:"""在链表的指定位置插入新节点:param head: 链表的头节点:param item: 要插入的新数据:param position: 插入的位置（从0开始）:return: 链表的头节点"""new_node = Node(item)  # 创建一个新的节点if position == 0:  # 如果插入位置是头部，直接使用头插法new_node.next = headreturn new_nodecurrent = headcurrent_position = 0while current and current_position < position - 1:  # 找到指定位置的前驱节点current = current.nextcurrent_position += 1if current is None:  # 如果当前节点为空，说明插入位置超出了链表长度raise IndexError("Position out of bounds")new_node.next = current.next  # 新节点的 next 指向当前位置的下一个节点current.next = new_node  # 前驱节点的 next 指向新节点return head  # 返回头节点

示例用法

# 创建一个简单的链表：1 -> 2 -> 3
head = Node(1)
head = insert_at_tail(head, 2)
head = insert_at_tail(head, 3)# 在链表头部插入0：0 -> 1 -> 2 -> 3
head = insert_at_head(head, 0)# 在链表尾部插入4：0 -> 1 -> 2 -> 3 -> 4
head = insert_at_tail(head, 4)# 在位置2插入1.5：0 -> 1 -> 1.5 -> 2 -> 3 -> 4
head = insert_at_position(head, 1.5, 2)# 打印链表
print_link_list(head)

总结

  • 头插法：新节点插入到链表的头部，成为新的头节点。
  • 尾插法：新节点插入到链表的尾部，成为链表的最后一个节点。
  • 中间插入：新节点插入到链表的指定位置，前驱节点的 next 指向新节点，新节点的 next 指向后继节点。

链表节点的删除

在这里插入图片描述
链表节点的删除操作可以分为几种常见情况：
删除头节点、删除尾节点、以及删除链表中间的某个节点。

1. 删除头节点

删除链表的头节点是最简单的操作。只需将头节点指向它的下一个节点即可。

def delete_head(head: Node) -> Node:"""删除链表的头节点:param head: 链表的头节点:return: 删除头节点后的链表新头节点"""if head is None:  # 如果链表为空，直接返回 Nonereturn Nonereturn head.next  # 返回第二个节点作为新的头节点

2. 删除尾节点

删除尾节点需要遍历链表，找到倒数第二个节点，然后将它的 next 指向 None。

def delete_tail(head: Node) -> Node:"""删除链表的尾节点:param head: 链表的头节点:return: 删除尾节点后的链表头节点"""if head is None:  # 如果链表为空，直接返回 Nonereturn Noneif head.next is None:  # 如果链表只有一个节点，删除该节点后链表为空return Nonecurrent = headwhile current.next.next:  # 找到倒数第二个节点current = current.nextcurrent.next = None  # 将倒数第二个节点的 next 指向 Nonereturn head  # 返回头节点

3. 删除中间节点

删除链表中间的某个节点需要先找到它的前驱节点，然后将前驱节点的 next 指向要删除节点的下一个节点。

def delete_at_position(head: Node, position: int) -> Node:"""删除链表指定位置的节点:param head: 链表的头节点:param position: 要删除的节点位置（从0开始）:return: 删除节点后的链表头节点"""if head is None:  # 如果链表为空，直接返回 Nonereturn Noneif position == 0:  # 如果要删除头节点，直接使用 delete_head 函数return delete_head(head)current = headcurrent_position = 0while current and current_position < position - 1:  # 找到待删除节点的前驱节点current = current.nextcurrent_position += 1if current is None or current.next is None:  # 如果位置超出链表长度，抛出异常raise IndexError("Position out of bounds")current.next = current.next.next  # 将前驱节点的 next 指向待删除节点的下一个节点return head  # 返回头节点

示例用法

# 创建一个简单的链表：1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head = insert_at_tail(head, 2)
head = insert_at_tail(head, 3)
head = insert_at_tail(head, 4)
head = insert_at_tail(head, 5)# 删除头节点：2 -> 3 -> 4 -> 5
head = delete_head(head)# 删除尾节点：2 -> 3 -> 4
head = delete_tail(head)# 删除位置1的节点（删除值为3的节点）：2 -> 4
head = delete_at_position(head, 1)# 打印链表
print_link_list(head)

总结

  • 删除头节点：直接将头节点指向它的下一个节点。
  • 删除尾节点：找到倒数第二个节点，将其 next 指向 None，删除最后一个节点。
  • 删除中间节点：找到要删除节点的前驱节点，将前驱节点的 next 指向待删除节点的下一个节点。

3 双链表

在这里插入图片描述

3.1 双链表节点的插入

在这里插入图片描述
在这里插入图片描述
双链表（Doubly Linked List）是一种链表结构，其中每个节点不仅包含指向下一个节点的指针（next），还包含指向前一个节点的指针（prev）。
这种结构使得在链表中进行插入、删除等操作更加灵活，因为可以从任意节点向前或向后遍历链表。

双链表节点的插入操作

在双链表中，节点的插入操作可以分为以下几种情况：

  1. 在链表头部插入节点
  2. 在链表尾部插入节点
  3. 在链表中间某个节点之前或之后插入节点

1. 在链表头部插入节点

在链表头部插入节点时，新节点将成为新的头节点，原来的头节点成为第二个节点。

class Node:def __init__(self, item=None):self.item = item  # 存储节点的数据self.next = None  # 指向下一个节点self.prev = None  # 指向前一个节点def insert_at_head(head: Node, item) -> Node:"""在双链表的头部插入新节点:param head: 链表的头节点:param item: 要插入的新数据:return: 新的头节点"""new_node = Node(item)  # 创建一个新的节点new_node.next = head  # 新节点的 next 指向当前的头节点if head is not None:  # 如果链表不为空head.prev = new_node  # 原头节点的 prev 指向新节点return new_node  # 新节点现在成为头节点，返回它

2. 在链表尾部插入节点

在链表尾部插入节点时，需要遍历链表找到最后的节点，然后将新节点插入到最后的节点之后。

def insert_at_tail(head: Node, item) -> Node:"""在双链表的尾部插入新节点:param head: 链表的头节点:param item: 要插入的新数据:return: 链表的头节点"""new_node = Node(item)  # 创建一个新的节点if head is None:  # 如果链表为空，直接返回新节点作为头节点return new_nodetail = headwhile tail.next:  # 遍历链表找到最后的节点tail = tail.nexttail.next = new_node  # 将新节点插入到最后的节点后面new_node.prev = tail  # 新节点的 prev 指向当前的最后节点return head  # 返回头节点

3. 在链表中间某个节点之前或之后插入节点

在双链表的中间插入节点时，可以选择在指定节点之前或之后插入新节点。
这里假设我们需要在某个位置插入新节点。

def insert_after(node: Node, item):"""在指定节点之后插入新节点:param node: 当前节点:param item: 要插入的新数据"""if node is None:returnnew_node = Node(item)  # 创建一个新的节点new_node.next = node.next  # 新节点的 next 指向当前节点的下一个节点new_node.prev = node  # 新节点的 prev 指向当前节点if node.next:  # 如果当前节点的 next 不为空，调整下一个节点的 prev 指向新节点node.next.prev = new_nodenode.next = new_node  # 当前节点的 next 指向新节点def insert_before(node: Node, item):"""在指定节点之前插入新节点:param node: 当前节点:param item: 要插入的新数据"""if node is None:returnnew_node = Node(item)  # 创建一个新的节点new_node.prev = node.prev  # 新节点的 prev 指向当前节点的前一个节点new_node.next = node  # 新节点的 next 指向当前节点if node.prev:  # 如果当前节点的 prev 不为空，调整前一个节点的 next 指向新节点node.prev.next = new_nodeelse:return new_node  # 如果插入的是第一个位置，返回新节点作为新的头节点node.prev = new_node  # 当前节点的 prev 指向新节点

示例用法

# 创建一个双向链表：1 <-> 2 <-> 3
head = Node(1)
head = insert_at_tail(head, 2)
head = insert_at_tail(head, 3)# 在链表头部插入0：0 <-> 1 <-> 2 <-> 3
head = insert_at_head(head, 0)# 在链表尾部插入4：0 <-> 1 <-> 2 <-> 3 <-> 4
head = insert_at_tail(head, 4)# 在节点2之后插入2.5：0 <-> 1 <-> 2 <-> 2.5 <-> 3 <-> 4
insert_after(head.next.next, 2.5)# 在节点2之前插入1.5：0 <-> 1 <-> 1.5 <-> 2 <-> 2.5 <-> 3 <-> 4
head = insert_before(head.next.next, 1.5)

总结

  • 头部插入：新节点成为新的头节点，调整原头节点的 prev 指向新节点。
  • 尾部插入：新节点成为新的尾节点，调整原尾节点的 next 指向新节点。
  • 中间插入：在指定节点之前或之后插入新节点，调整前驱和后继节点的指针。

使用双链表时，需要确保插入操作时正确更新节点的 next 和 prev 指针，以保持链表结构的完整性。

3.2 双链表节点的删除

在这里插入图片描述
双链表（Doubly Linked List）的删除操作比单链表（Singly Linked List）稍复杂，
但由于双链表的每个节点都包含前一个节点的指针（prev）和下一个节点的指针（next），
删除操作变得更加灵活。

1. 删除头节点

删除双链表的头节点时，只需将头节点指向它的下一个节点，并更新新头节点的 prev 指针为 None。

class Node:def __init__(self, item=None):self.item = item  # 存储节点的数据self.next = None  # 指向下一个节点self.prev = None  # 指向前一个节点def delete_head(head: Node) -> Node:"""删除双链表的头节点:param head: 链表的头节点:return: 删除头节点后的链表新头节点"""if head is None:  # 如果链表为空，直接返回 Nonereturn Nonenew_head = head.next  # 新的头节点是当前头节点的下一个节点if new_head:  # 如果新的头节点存在new_head.prev = None  # 将新的头节点的 prev 指向 Nonereturn new_head  # 返回新的头节点

2. 删除尾节点

删除尾节点时，需要遍历链表找到倒数第二个节点，然后将它的 next 指向 None，并将其 prev 指向 None。

def delete_tail(head: Node) -> Node:"""删除双链表的尾节点:param head: 链表的头节点:return: 删除尾节点后的链表头节点"""if head is None:  # 如果链表为空，直接返回 Nonereturn Noneif head.next is None:  # 如果链表只有一个节点，删除该节点后链表为空return Nonetail = headwhile tail.next:  # 遍历找到最后一个节点tail = tail.nextif tail.prev:  # 如果有前驱节点tail.prev.next = None  # 将倒数第二个节点的 next 指向 Nonereturn head  # 返回头节点

3. 删除中间节点

删除链表中的某个中间节点时，需找到要删除节点的前驱节点和后继节点，然后调整它们的 next 和 prev 指针。

def delete_node(node: Node):"""删除指定的节点:param node: 要删除的节点"""if node is None:returnif node.prev:  # 如果前驱节点存在node.prev.next = node.next  # 将前驱节点的 next 指向要删除节点的后继节点if node.next:  # 如果后继节点存在node.next.prev = node.prev  # 将后继节点的 prev 指向要删除节点的前驱节点# 可以将要删除的节点的 next 和 prev 设置为 None 来帮助垃圾回收node.next = Nonenode.prev = None

示例用法

# 创建一个双链表：1 <-> 2 <-> 3 <-> 4 <-> 5
head = Node(1)
head = insert_at_tail(head, 2)
head = insert_at_tail(head, 3)
head = insert_at_tail(head, 4)
head = insert_at_tail(head, 5)# 删除头节点：2 <-> 3 <-> 4 <-> 5
head = delete_head(head)# 删除尾节点：2 <-> 3 <-> 4
head = delete_tail(head)# 假设我们要删除值为 3 的节点
node_to_delete = head.next  # 获取要删除的节点（值为 3 的节点）
delete_node(node_to_delete)  # 删除指定的节点# 打印链表
print_link_list(head)

总结

  • 删除头节点：更新头节点指向下一个节点，并将新的头节点的 prev 设置为 None。
  • 删除尾节点：找到倒数第二个节点，将其 next 设置为 None，并返回头节点。
  • 删除中间节点：更新前驱节点的 next 指向要删除节点的后继节点，同时更新后继节点的 prev 指向要删除节点的前驱节点。

在进行删除操作时，确保更新了前驱节点和后继节点的指针，以保持双链表的结构完整。


http://www.ppmy.cn/ops/100808.html

相关文章

小程序wx:if 和hidden的区别

小程序wx:if 和hidden的区别

在微信小程序中&#xff0c;wx:if和hidden都是用于控制元素显示与隐藏的方法&#xff0c;但它们在工作原理和性能上存在显著差异。以下是两者的详细区别&#xff1a; 工作原理 wx:if&#xff1a; 这是一个条件渲染指令&#xff0c;用于根据条件判断来决定是否渲染该元素。当条…
阅读更多...
等保测评中的安全测试方法

等保测评中的安全测试方法

等保测评&#xff0c;即信息安全等级保护测评&#xff0c;是我国网络安全领域的重要评估机制&#xff0c;用于验证网络系统或应用是否满足相应的安全保护等级要求。在等保测评中&#xff0c;安全测试方法扮演着至关重要的角色。本文将详细介绍等保测评中常用的安全测试方法及其…
阅读更多...
【Linux】分析一段oom及oops报错日志

【Linux】分析一段oom及oops报错日志

oom相关日志分析: Oom-killer错误是因系统内存分配不足&#xff0c;为保障系统正常运行会随机kill掉占用较多的内存进程。 该日志已经输出内存占满相关提示&#xff0c;内存上限为16G&#xff0c;当前已使用16G&#xff0c;内存限制导致分配失败次数为586755次。 OOPS相关日志…
阅读更多...
MySQL（面试篇）

MySQL（面试篇）

目录 说一下ACID是什么&#xff1f; Atomicity&#xff08;原子性&#xff09;&#xff1a; Consistency&#xff08;一致性&#xff09;&#xff1a; Isolation&#xff08;隔离性&#xff09;&#xff1a; Durability&#xff08;持久性&#xff09;&#xff1a; MySQL…
阅读更多...
网络-VPN

网络-VPN

VPN&#xff08;Virtual Private Network&#xff0c;虚拟专用网络&#xff09;是一种网络技术&#xff0c;用于在公共网络&#xff08;如互联网&#xff09;上建立一个安全的、加密的连接通道&#xff0c;以保护数据传输的安全性和隐私。通过使用 VPN&#xff0c;用户可以在不…
阅读更多...
Cubase操作：如何修改每个音频块的名字 写歌习惯

Cubase操作：如何修改每个音频块的名字 写歌习惯

如何修改每个音频块的名字 我对命名比较注重&#xff0c;之前用Cubase12&#xff0c;导入我手机中编辑过的Cubasis的工程时&#xff0c;发现中文部分有乱码…… 而且好像改名改得很费劲…… 后面通过多方咨询和探索思考&#xff0c;终于找到方法了&#xff01; 可以先把信息…
阅读更多...
Python(PyTorch)物理变化可微分神经算法

Python(PyTorch)物理变化可微分神经算法

&#x1f3af;要点 &#x1f3af;使用受控物理变换序列实现可训练分层物理计算 | &#x1f3af;多模机械振荡、非线性电子振荡器和光学二次谐波生成神经算法验证 | &#x1f3af;训练输入数据&#xff0c;物理系统变换产生输出和可微分数字模型估计损失的梯度 | &#x1f3af;…
阅读更多...
Tutorial：Deep Learning for Remote Sensing Data

Tutorial：Deep Learning for Remote Sensing Data

文章目录 0. Intro1. ADVANTAGES OF REMOTE SENSING METHODS2. THE GENERAL FRAMEWORK3. BASIC ALGORITHMS IN DEEP LEARNING3.1 CONVOLUTIONAL NEURAL NETWORKS3.1.1 CONVOLUTIONAL LAYER3.1.2 NONLINEARITY LAYER3.1.3 POOLING LAYER 3.2 AUTOENCODERS3.3 RESTRICTED BOLTZMA…
阅读更多...
最新文章

Copyright @ 2022~2023