数组和链表

1、数组

数组（array）是一种线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。

1.1 初始化数组
1
2
arr: list[int] = [0] * 10  # 初始化长度为10的数组，
nums: list[int] = [1, 2, 3, 4, 5]
1.2 访问元素

索引本质上是内存地址的偏移量，因此数组的访问操作是非常高效的。

1
2
3
4
5
6
7
8
9
def random_access(nums: list[int]) -> int:
    """
    随机访问数组元素
    :param nums: 数组
    :return: 数组元素
    """
    random_index = random.randint(0, len(nums) - 1)
    random_num = nums[random_index]
    return random_num
1.3 插入元素
1
2
3
4
5
6
def insert(nums: list[int], num: int, index: int):
    # 把索引index以及之后的所有元素向后移动一位
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    # 将num插入到索引index的位置
    nums[index] = num
1.4 删除元素
1
2
3
4
def remove(nums: list[int], index: int):
    # 把索引index以及之后的所有元素向前移动一位
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i + 1]

数组的插入与删除操作缺点:

  • 时间复杂度高
  • 丢失元素
  • 内存浪费
1.5 遍历元素
1
2
3
4
5
6
7
8
9
10
11
12
def traverse(nums: list[int]):
    count = 0
    # 通过索引遍历
    for i in range(len(nums)):
        count += nums[i]
    # 直接遍历
    for num in nums:
        count += num
    # 同时遍历索引和元素
    for i, num in enumerate(nums):
        count += nums[i]
        count += num
1.6 查找元素
1
2
3
4
5
def find(nums: list[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1
1.7 扩容元素
1
2
3
4
5
def extend(nums: list[int], enlarge: int) -> list[int]:
    res = [0] * (len(nums) + enlarge)
    for i in range(len(nums)):
        res[i] = nums[i]
    return res

数组的优点和局限性

  • 空间效率高
  • 支持随机访问
  • 缓存局部性： 当访问数组元素时，计算机不仅会加载他，还会缓存其他周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
  • 插入与删除效率低
  • 长度不可变
  • 空间浪费

2、链表

  • 链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过引用相连接。
    引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
  • 链表的组成单位是节点(node)对象。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import pickle


class ListNode:
    """
    链表的首个节点称为 头结点，最后一个节点称为 尾节点
    尾节点指向的是 None
    """

    def __init__(self, val: int):
        self.val: int = val
        self.next: ListNode | None = None


# 初始化链表
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4


# 我们通常将头结点当做链表的代称，以上链表记作链表n0。


# 插入节点
def insert(n0: ListNode, P: ListNode):
    n1 = n0.next
    P.next = n1
    n0.next = P


# 删除节点
def remove(n0: ListNode):
    P = n0.next
    n1 = P.next
    n0.next = n1


# 访问节点
def access(head: ListNode, index: int) -> ListNode | None:
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head


# 查找节点
def find(head: ListNode, target: int) -> int:
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1


# 常见链表类型
# 单向链表 如上演示
# 环形链表 令单向链表的尾节点指向头结点，其中任意节点都可以视为头结点
# 双向链表
class ListNode:
    def __init__(self, val: int):
        self.val: int = val
        self.prev: ListNode | None = None
        self.next: ListNode | None = None