【数据结构根本_链表】

1、链表的界说

链表与数组的区分：

1. 数组是一块连续的内存空间，有了这块内存空间的首地址，就能直接通过索引计算出任意位置的元素地址。
2. 数组最大的优势是支持通过索引快速访问元素，而链表就不支持。
4. 链表不一样，一条链表并不需要一整块连续的内存空间存储元素。
5. 链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 next, prev 指针，将零散的内存块串联起来形成一个链式结构。
7. 1）这样可以提高内存的利用效率，链表的节点不需要挨在一起，给点内存 new 出来一个节点就能用，操作系统会觉得这娃好养活
9. 2）另外一个好处，它的节点要用的时候就能接上，不用的时候拆掉就行了，从来不需要考虑扩缩容和数据搬移的问题
11. 弊端：
12. 因为元素并不是紧挨着的，所以如果你想要访问第 3 个链表元素，你就只能从头结点开始往顺着 next 指针往后找，直到找到第 3 个节点才行。

复制代码

二、链表的类型

1、单链表

编程语言标准库一样平常都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。

1. class ListNode:
2.     def __init__(self, x):
3.         self.val = x
4.         self.next = None

复制代码

2、双链表

编程语言标准库一样平常使用的都是双链表而非单链表。
单链表节点只有一个 next 指针，指向下一个节点；
而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。

1. class Node:
2.     def __init__(self, prev, element, next):
3.         self.val = element
4.         self.next = next #指向下个元素的指针
5.         self.prev = prev #指向上个元素的指针

复制代码

三、单链表的使用

起首，要创建一个单链表，来用于下面的使用

1. class ListNode:
2.     def __init__(self, x):  # 修正了 __int__ 为 __init__
3.         self.val = x
4.         self.next = None
6. def createlinkedlist(arry: 'List[int]') -> ListNode:
7.     if arry is None or len(arry) == 0:
8.         return None
9.     head = ListNode(arry[0])  # 创建头节点
10.     current = head  # 使用一个指针来遍历链表
11.     for i in range(1, len(arry)):
12.         current.next = ListNode(arry[i])  # 创建新节点并链接
13.         current = current.next  # 移动指针
14.     return head  # 返回链表的头节点

复制代码

1. 1、对节点进行赋值，必须转化为ListNode类型
3. head = ListNode(arry[0])  # 创建头节点
4.    
5. current.next = ListNode(arry[i])  # 创建新节点并链接
7. 错误写法：current.next = arry[i]
9. 2、必须使用指针来遍历链表
11. head = ListNode(arry[0])  # 创建头节点
12. current = head  # 使用一个指针来遍历链表
14. 问题：为什么需要使用指针（如 current）？
15. 1、保持链表头节点的引用
16. 链表的头节点是链表的入口点，通常需要保持对它的引用，以便后续可以访问整个链表。如果不使用额外的指针，直接操作 head，可能会导致以下问题：
17. 1）丢失链表头节点：在链表操作过程中，如果直接修改 head，可能会意外地丢失对链表的引用，导致无法再访问链表的其他部分。
18. 2)无法返回链表头节点：在函数中创建链表时，最终需要返回链表的头节点。如果不使用额外的指针，直接操作 head，可能会导致返回的头节点指向错误的位置。
20. 2、方便链表的遍历和操作
21. 使用指针（如 current）可以方便地遍历链表，并在遍历过程中对链表进行操作（如插入、删除节点）。指针的作用类似于一个“游标”，可以在不改变链表头节点的情况下，逐个访问链表的节点。
23. 3、如果不使用指针：
24. def createlinkedlist(arry: 'List[int]') -> ListNode:
25.   。。。
26.     head = ListNode(arry[0])
27.     for i in range(1, len(arry)):
28.         head.next = ListNode(arry[i])
29.         head = head.next  # 直接修改 head
30.     return head  # 返回的是最后一个节点，而不是头节点

复制代码

运行结果：

1、查

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # P为指针，遍历单链表
5. p = head
6. while p is not None:
7.     print(p.val)
8.     p = p.next

复制代码

2、增

在头部增加新节点

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 在单链表头部插入一个新节点 0
5. newHead = ListNode(0)
7. newHead.next = head
8. head = newHead
9. # 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5

复制代码

在尾部增加新节点

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 在单链表尾部插入一个新节点 6
5. p = head
6. # 先走到链表的最后一个节点
7. while p.next is not None:
8.     p = p.next
9. # 现在 p 就是链表的最后一个节点
10. # 在 p 后面插入新节点
11. p.next = ListNode(6)
13. # 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

复制代码

 在单链表中间插入新元素

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 在第 3 个节点后面插入一个新节点 66
5. # 先要找到前驱节点，即第 3 个节点
6. p = head
7. for _ in range(2):
8.     p = p.next
9. # 此时 p 指向第 3 个节点
10. # 组装新节点的后驱指针
11. new_node = ListNode(66)
12. new_node.next = p.next
14. # 插入新节点
15. p.next = new_node
17. # 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

复制代码

3、删

删除一个节点，起首要找到要被删除节点的前驱节点，然后把这个前驱节点的 next 指针指向被删除节点的下一个节点。这样就能把被删除节点从链表中摘除了。

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 删除第 4 个节点，要操作前驱节点
5. p = head
6. for i in range(2):
7.     p = p.next
9. # 此时 p 指向第 3 个节点，即要删除节点的前驱节点
10. # 把第 4 个节点从链表中摘除
11. p.next = p.next.next
13. # 现在链表变成了 1 -> 2 -> 3 -> 5

复制代码

 在单链表尾部删除元素

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 删除尾节点
5. p = head
6. # 找到倒数第二个节点
7. while p.next.next is not None:
8.     p = p.next
10. # 此时 p 指向倒数第二个节点
11. # 把尾节点从链表中摘除
12. p.next = None
14. # 现在链表变成了 1 -> 2 -> 3 -> 4

复制代码

在单链表头部删除元素

1. # 创建一条单链表
2. head = createLinkedList([1, 2, 3, 4, 5])
4. # 删除头结点
5. head = head.next
7. # 现在链表变成了 2 -> 3 -> 4 -> 5

复制代码

四、双链表的使用

1. class DoublyListNode:
2.     def __init__(self, x):
3.         self.val = x
4.         self.next = None
5.         self.prev = None
6.         
7. def createDoublyLinkedList(arr: List[int]) -> Optional[DoublyListNode]:
8.     if not arr:
9.         return None
10.    
11.     head = DoublyListNode(arr[0])
12.     cur = head
13.    
14.     # for 循环迭代创建双链表
15.     for val in arr[1:]:#基于切片进行迭代
16.         new_node = DoublyListNode(val)
17.         cur.next = new_node
18.         new_node.prev = cur
19.         cur = cur.next
20.    
21.     return head

复制代码

1. 判断空列表：
3. 方式一：更加显式
5. if arr is None or len(arr):
8. 方式二：更加简洁
10. if not arr:
12. 在 Python 中，if not arr 是一种简洁的写法，用于检查一个可迭代对象（如列表、字符串、字典等）是否为空。它基于 Python 的布尔上下文（Boolean Context）：
14. 如果 arr 是 None 或者是一个空列表（[]），if not arr 的条件为 True。
16. 如果 arr 是一个非空列表（如 [1, 2, 3]），if not arr 的条件为 False。
18. 因此，if not arr 可以同时检查 arr 是否为 None 或者是否为空列表。
20. 0为false,非0 为true

复制代码

 1、查

对于双链表的遍历和查找，我们可以从头节点或尾节点开始，根据需要向前或向后遍历：

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
3. tail = None
5. # 1、从头节点向后遍历双链表
6. p = head
7. while p:
8.     print(p.val)
9.     tail = p
10.     p = p.next
12. # 2、从尾节点向前遍历双链表
13. p = tail
14. while p:
15.     print(p.val)
16.     p = p.prev

复制代码

2、增

在链表头节点插入一个值

1. # 创建一条双链表
2. head = create_doubly_linked_list([1, 2, 3, 4, 5])
4. # 在双链表头部插入新节点 0
5. new_head = DoublyListNode(0)
6. new_head.next = head
7. head.prev = new_head
8. head = new_head
9. # 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5

复制代码

在链表尾部插入一个值

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
4. # p是一个指针，初始化是从头节点开始
5. p = head
6. # 先走到链表的最后一个节点
7. while p.next is not None:
8.     p = p.next
10. # 在双链表尾部插入新节点 6
11. newNode = DoublyListNode(6)
12. p.next = newNode
13. newNode.prev = p
14. # 更新尾节点引用
15. p = newNode
17. # 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6

复制代码

在双链表中间插入元素

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
4. # 在第 3 个节点后面插入新节点 66
5. # 找到第 3 个节点
6. p = head
7. for _ in range(2): #range(2)代表0,1
8.     p = p.next
10. # 组装新节点
11. newNode = DoublyListNode(66)
12. newNode.next = p.next
13. newNode.prev = p
15. # 插入新节点
16. p.next.prev = newNode
17. p.next = newNode
19. # 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5

复制代码

表明

1. _ 是一个特殊的变量名，通常被称为“占位符变量”
3. for _ in range(2): 的作用
4. for _ in range(2): 的意思是：循环两次，每次循环中 _ 的值会从 range(2) 中依次取值（即 0 和 1），但 _ 的值在循环体中不会被使用。

复制代码

3、删

在双链表中删除一个节点，需要调解前驱节点和后继节点的指针

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
4. # 删除第 4 个节点
5. # 先找到第 3 个节点
6. p = head
7. for i in range(2):
8.     p = p.next
10. # 现在 p 指向第 3 个节点，我们将它后面的那个节点摘除出去
11. toDelete = p.next
13. # 把 toDelete 从链表中摘除
14. p.next = toDelete.next
15. toDelete.next.prev = p
17. # 把 toDelete 的前后指针都置为 null 是个好习惯（可选）
18. toDelete.next = None
19. toDelete.prev = None
21. # 现在链表变成了 1 -> 2 -> 3 -> 5

复制代码

在双链表头部删除元素

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
4. # 删除头结点
5. toDelete = head
6. head = head.next
7. head.prev = None
9. # 清理已删除节点的指针
10. toDelete.next = None
12. # 现在链表变成了 2 -> 3 -> 4 -> 5

复制代码

在双链表尾部删除元素

1. # 创建一条双链表
2. head = createDoublyLinkedList([1, 2, 3, 4, 5])
4. # 删除尾节点
5. p = head
6. # 找到尾结点
7. while p.next is not None:
8.     p = p.next
10. # 现在 p 指向尾节点
11. # 把尾节点从链表中摘除
12. p.prev.next = None
14. # 把被删结点的指针都断开是个好习惯（可选）
15. p.prev = None
17. # 现在链表变成了 1 -> 2 -> 3 -> 4

复制代码

防止内存泄漏：把删除的元素，赋值为None，就可以

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。