1.链表

类型：单链表，双链表，循环链表

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

Python链表操作

1. 定义链表节点类：

class ListNode:
    def init(self, value=0, next=None):
        self.value = value
        self.next = next

2. 创建链表：

# 创建链表 1->2->3->4->5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

3. 遍历链表：

def print_linked_list(head):
	current = head
    while current:
        print(current.value, end=" -> ")
        current = current.next
    print("None")
# 输出: 1 -> 2 -> 3 -> 4 -> 5 -> None
print_linked_list(head)

4. 插入节点：

def insert_node_after(node, new_value):
	new_node = ListNode(new_value)
	new_node.next = node.next
	node.next = new_node
# 在节点 2 后插入节点 6
insert_node_after(head.next, 6)
# 输出: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> None
print_linked_list(head)

5.删除节点

def delete_node(node):
    node.value = node.next.value
    node.next = node.next.next

# 删除节点 3
delete_node(head.next.next)
# 原本: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> None
# 输出: 1 -> 2 -> 3 -> 4 -> 5 -> None
print_linked_list(head)

6.反转链表

def reverse_linked_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

# 反转链表
new_head = reverse_linked_list(head)
# 输出: 5 -> 4 -> 3 -> 2 -> 1 -> None
print_linked_list(new_head)

性能分析

数组的查询时间复杂度为 O(1) 是因为数组具有随机访问的特性。在数组中，每个元素都占据一个固定的内存位置，因此通过索引就能够直接计算出该元素的内存地址。假设数组的起始地址为 base_address，每个元素占用的内存空间为 element_size，要访问数组中的第 i 个元素，可以使用以下公式迅速计算该元素的内存地址：

memory_address = base_address + i * element_size

因为计算内存地址的步骤是基本的算术运算，与数组大小 n 无关，所以数组的查询时间复杂度为 O(1)。

2.题目

 203.移除链表元素  

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

思路：找个辅助节点，指向原节点，找个指针去做删除操作

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        new=ListNode(next=head)
        current=new
        while current.next:
            if current.next.val == val:
                current.next=current.next.next
            else:
                current=current.next
        return new.next

 707.设计链表  

建议： 这是一道考察 链表综合操作的题目，不算容易，可以练一练 使用虚拟头结点

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

 206.反转链表 

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

思路：先把cur.next暂存，再把next指向pre，再把暂存赋值给pre

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre=None
        cur=head
        while cur:
            zan = cur.next
            cur.next=pre
            pre=cur
            cur=zan
        return pre