【数据结构基础_链表】

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 #指向上个元素的指针

三、链表的表达

1、链表通过嵌套的 ListNode 对象来表示。

每个 ListNode 对象表示一个节点，val 属性存储节点的值，next 属性指向下一个节点。

head1 = ListNode(1, ListNode(4, ListNode(5)))  # 链表1: 1 -> 4 -> 5
head2 = ListNode(1, ListNode(3, ListNode(4)))  # 链表2: 1 -> 3 -> 4
head3 = ListNode(2, ListNode(6))               # 链表3: 2 -> 6lists = [head1, head2, head3]  # 链表数组，每个元素是一个链表的头节点例如，链表 1 -> 4 -> 5 可以表示为：head1 = ListNode(1, ListNode(4, ListNode(5)))这里的代码逻辑是：ListNode(5)：创建一个值为 5 的节点，它的 next 默认为 None。ListNode(4, ListNode(5))：创建一个值为 4 的节点，它的 next 指向值为 5 的节点。ListNode(1, ListNode(4, ListNode(5)))：创建一个值为 1 的节点，它的 next 指向值为 4 的节点。通过这种方式，整个链表 1 -> 4 -> 5 被构建出来，head1 是链表的头节点。

2、链表数组（可以理解为只存头节点）

因为对于一个链表来说，只要有头节点，就可以代表这个链表，因为头节点有指针，会一直指下去

对链表和链表数组的结构理解。让我们详细解释一下。1. 链表的结构
链表是一种线性数据结构，由一系列节点组成，每个节点包含两部分：
val：存储节点的值。
next：指向下一个节点的指针。链表的头节点是链表的起点，通过头节点可以访问整个链表。例如，一个链表 1 -> 2 -> 3 的结构如下：头节点的值为 1，它的 next 指向值为 2 的节点。
值为 2 的节点的 next 指向值为 3 的节点。
值为 3 的节点的 next 为 None，表示链表结束。2. 链表数组的结构
lists 是一个包含多个链表的数组，每个链表都将只通过它的头节点来表示。例如：lists = [head1, head2, head3]
head1 是第一个链表的头节点。
head2 是第二个链表的头节点。
head3 是第三个链表的头节点。3. 为什么链表数组只包含头节点？
链表的头节点是访问整个链表的入口。通过头节点，可以遍历整个链表。
因此，在链表数组中，只需要存储每个链表的头节点即可。具体来说：1）存储头节点：只需要存储链表的头节点，就可以通过 next 指针访问链表中的所有节点。
2）节省空间：不需要存储整个链表的所有节点，只需要存储头节点即可表示整个链表。
3）方便操作：通过头节点可以方便地遍历、修改或操作整个链表。4. 示例说明
假设我们有以下三个链表：链表1：1 -> 4 -> 5
链表2：1 -> 3 -> 4
链表3：2 -> 6在代码中，lists 的结构如下：head1 = ListNode(1, ListNode(4, ListNode(5)))
head2 = ListNode(1, ListNode(3, ListNode(4)))
head3 = ListNode(2, ListNode(6))lists = [head1, head2, head3]lists 是一个数组，包含三个链表的头节点。
通过 head1，可以访问链表1的所有节点。
通过 head2，可以访问链表2的所有节点。
通过 head3，可以访问链表3的所有节点。5. 代码中的遍历逻辑
在代码中：for node in lists:  # 遍历链表数组的每一个链表头节点，因为只存头节点即可表达链表while node:  # 遍历当前链表的每一个节点values.append(node.val)node = node.next解释：
for node in lists：每次迭代取出数组中的一个头节点。
while node：从当前头节点开始，通过 node.next 逐个访问链表中的所有节点。总结
链表数组 lists：是一个包含多个链表头节点的数组。
头节点的作用：通过头节点可以访问整个链表，因此只需要存储头节点即可表示整个链表。
遍历逻辑：通过 for 循环取出每个头节点，然后通过 while 循环遍历链表中的所有节点。
这种结构既简洁又高效，是链表操作中常见的表示方式。

四、单链表的操作

首先，要创建一个单链表，来用于下面的操作

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，就可以