网站设计公司 无锡,怎么把网站做二维码,广州免费建站平台,系统开发立项报告1、链表的定义
链表与数组的区分#xff1a;
数组是一块连续的内存空间#xff0c;有了这块内存空间的首地址#xff0c;就能直接通过索引计算出任意位置的元素地址。
数组最大的优势是支持通过索引快速访问元素#xff0c;而链表就不支持。链表不一样#xff0c;一条链…1、链表的定义
链表与数组的区分
数组是一块连续的内存空间有了这块内存空间的首地址就能直接通过索引计算出任意位置的元素地址。
数组最大的优势是支持通过索引快速访问元素而链表就不支持。链表不一样一条链表并不需要一整块连续的内存空间存储元素。
链表的元素可以分散在内存空间的天涯海角通过每个节点上的 next, prev 指针将零散的内存块串联起来形成一个链式结构。1这样可以提高内存的利用效率链表的节点不需要挨在一起给点内存 new 出来一个节点就能用操作系统会觉得这娃好养活2另外一个好处它的节点要用的时候就能接上不用的时候拆掉就行了从来不需要考虑扩缩容和数据搬移的问题弊端
因为元素并不是紧挨着的所以如果你想要访问第 3 个链表元素你就只能从头结点开始往顺着 next 指针往后找直到找到第 3 个节点才行。
二、链表的类型
1、单链表
编程语言标准库一般都会提供泛型即你可以指定 val 字段为任意类型而力扣的单链表节点的 val 字段只有 int 类型。
class ListNode:def __init__(self, x):self.val xself.next None
2、双链表
编程语言标准库一般使用的都是双链表而非单链表。
单链表节点只有一个 next 指针指向下一个节点
而双链表节点有两个指针prev 指向前一个节点next 指向下一个节点。
class Node:def __init__(self, prev, element, next):self.val elementself.next next #指向下个元素的指针self.prev prev #指向上个元素的指针
三、单链表的操作
首先要创建一个单链表来用于下面的操作
class ListNode:def __init__(self, x): # 修正了 __int__ 为 __init__self.val xself.next Nonedef createlinkedlist(arry: List[int]) - ListNode:if arry is None or len(arry) 0:return Nonehead ListNode(arry[0]) # 创建头节点current head # 使用一个指针来遍历链表for i in range(1, len(arry)):current.next ListNode(arry[i]) # 创建新节点并链接current current.next # 移动指针return head # 返回链表的头节点
1、对节点进行赋值必须转化为ListNode类型head ListNode(arry[0]) # 创建头节点current.next ListNode(arry[i]) # 创建新节点并链接错误写法current.next arry[i]2、必须使用指针来遍历链表head ListNode(arry[0]) # 创建头节点
current head # 使用一个指针来遍历链表问题为什么需要使用指针如 current
1、保持链表头节点的引用
链表的头节点是链表的入口点通常需要保持对它的引用以便后续可以访问整个链表。如果不使用额外的指针直接操作 head可能会导致以下问题
1丢失链表头节点在链表操作过程中如果直接修改 head可能会意外地丢失对链表的引用导致无法再访问链表的其他部分。
2)无法返回链表头节点在函数中创建链表时最终需要返回链表的头节点。如果不使用额外的指针直接操作 head可能会导致返回的头节点指向错误的位置。2、方便链表的遍历和操作
使用指针如 current可以方便地遍历链表并在遍历过程中对链表进行操作如插入、删除节点。指针的作用类似于一个“游标”可以在不改变链表头节点的情况下逐个访问链表的节点。3、如果不使用指针
def createlinkedlist(arry: List[int]) - ListNode:。。。head ListNode(arry[0])for i in range(1, len(arry)):head.next ListNode(arry[i])head head.next # 直接修改 headreturn head # 返回的是最后一个节点而不是头节点
运行结果 1、查
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# P为指针遍历单链表
p head
while p is not None:print(p.val)p p.next
2、增
在头部增加新节点
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 在单链表头部插入一个新节点 0
newHead ListNode(0)newHead.next head
head newHead
# 现在链表变成了 0 - 1 - 2 - 3 - 4 - 5
在尾部增加新节点
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 在单链表尾部插入一个新节点 6
p head
# 先走到链表的最后一个节点
while p.next is not None:p p.next
# 现在 p 就是链表的最后一个节点
# 在 p 后面插入新节点
p.next ListNode(6)# 现在链表变成了 1 - 2 - 3 - 4 - 5 - 6 在单链表中间插入新元素
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 在第 3 个节点后面插入一个新节点 66
# 先要找到前驱节点即第 3 个节点
p head
for _ in range(2):p p.next
# 此时 p 指向第 3 个节点
# 组装新节点的后驱指针
new_node ListNode(66)
new_node.next p.next# 插入新节点
p.next new_node# 现在链表变成了 1 - 2 - 3 - 66 - 4 - 5
3、删
删除一个节点首先要找到要被删除节点的前驱节点然后把这个前驱节点的 next 指针指向被删除节点的下一个节点。这样就能把被删除节点从链表中摘除了。
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 删除第 4 个节点要操作前驱节点
p head
for i in range(2):p p.next# 此时 p 指向第 3 个节点即要删除节点的前驱节点
# 把第 4 个节点从链表中摘除
p.next p.next.next# 现在链表变成了 1 - 2 - 3 - 5 在单链表尾部删除元素
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 删除尾节点
p head
# 找到倒数第二个节点
while p.next.next is not None:p p.next# 此时 p 指向倒数第二个节点
# 把尾节点从链表中摘除
p.next None# 现在链表变成了 1 - 2 - 3 - 4
在单链表头部删除元素
# 创建一条单链表
head createLinkedList([1, 2, 3, 4, 5])# 删除头结点
head head.next# 现在链表变成了 2 - 3 - 4 - 5
四、双链表的操作
class DoublyListNode:def __init__(self, x):self.val xself.next Noneself.prev Nonedef createDoublyLinkedList(arr: List[int]) - Optional[DoublyListNode]:if not arr:return Nonehead DoublyListNode(arr[0])cur head# for 循环迭代创建双链表for val in arr[1:]:#基于切片进行迭代new_node DoublyListNode(val)cur.next new_nodenew_node.prev curcur cur.nextreturn head
判断空列表方式一更加显式if arr is None or len(arr):方式二更加简洁if not arr:在 Python 中if not arr 是一种简洁的写法用于检查一个可迭代对象如列表、字符串、字典等是否为空。它基于 Python 的布尔上下文Boolean Context如果 arr 是 None 或者是一个空列表[]if not arr 的条件为 True。如果 arr 是一个非空列表如 [1, 2, 3]if not arr 的条件为 False。因此if not arr 可以同时检查 arr 是否为 None 或者是否为空列表。0为false,非0 为true 1、查
对于双链表的遍历和查找我们可以从头节点或尾节点开始根据需要向前或向后遍历
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])
tail None# 1、从头节点向后遍历双链表
p head
while p:print(p.val)tail pp p.next# 2、从尾节点向前遍历双链表
p tail
while p:print(p.val)p p.prev
2、增
在链表头节点插入一个值
# 创建一条双链表
head create_doubly_linked_list([1, 2, 3, 4, 5])# 在双链表头部插入新节点 0
new_head DoublyListNode(0)
new_head.next head
head.prev new_head
head new_head
# 现在链表变成了 0 - 1 - 2 - 3 - 4 - 5
在链表尾部插入一个值
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])# p是一个指针初始化是从头节点开始
p head
# 先走到链表的最后一个节点
while p.next is not None:p p.next# 在双链表尾部插入新节点 6
newNode DoublyListNode(6)
p.next newNode
newNode.prev p
# 更新尾节点引用
p newNode# 现在链表变成了 1 - 2 - 3 - 4 - 5 - 6
在双链表中间插入元素
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])# 在第 3 个节点后面插入新节点 66
# 找到第 3 个节点
p head
for _ in range(2): #range(2)代表0,1p p.next# 组装新节点
newNode DoublyListNode(66)
newNode.next p.next
newNode.prev p# 插入新节点
p.next.prev newNode
p.next newNode# 现在链表变成了 1 - 2 - 3 - 66 - 4 - 5
解释
_ 是一个特殊的变量名通常被称为“占位符变量”for _ in range(2): 的作用
for _ in range(2): 的意思是循环两次每次循环中 _ 的值会从 range(2) 中依次取值即 0 和 1但 _ 的值在循环体中不会被使用。 3、删
在双链表中删除一个节点需要调整前驱节点和后继节点的指针
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])# 删除第 4 个节点
# 先找到第 3 个节点
p head
for i in range(2):p p.next# 现在 p 指向第 3 个节点我们将它后面的那个节点摘除出去
toDelete p.next# 把 toDelete 从链表中摘除
p.next toDelete.next
toDelete.next.prev p# 把 toDelete 的前后指针都置为 null 是个好习惯可选
toDelete.next None
toDelete.prev None# 现在链表变成了 1 - 2 - 3 - 5
在双链表头部删除元素
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])# 删除头结点
toDelete head
head head.next
head.prev None# 清理已删除节点的指针
toDelete.next None# 现在链表变成了 2 - 3 - 4 - 5
在双链表尾部删除元素
# 创建一条双链表
head createDoublyLinkedList([1, 2, 3, 4, 5])# 删除尾节点
p head
# 找到尾结点
while p.next is not None:p p.next# 现在 p 指向尾节点
# 把尾节点从链表中摘除
p.prev.next None# 把被删结点的指针都断开是个好习惯可选
p.prev None# 现在链表变成了 1 - 2 - 3 - 4
防止内存泄漏把删除的元素赋值为None就可以
