第四章 数组与链表

数据库系统概念导航🚀🚀🚀

1. 🐻‍❄️ 第一章 初始算法

2. 🦝 第二章 复杂度分析

3. 🐳 第三章 数据结构

4. 🐼 第四章 数组与链表 ⇦ 当前位置🪂

数组

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

初始化数组

arr = [0] * 5
nums = [1, 2, 3, 4, 5]

访问数组

本质：索引index，索引的含义本质上是内存地址的偏移量。首个元素的地址偏移量是 0

num_1 = arr[index]
num_2 = nums[index]

def random_access(nums: list[int]) -> int:
    """随机访问元素"""
    # 在区间 [0, len(nums)-1] 中随机抽取一个数字
    random_index = random.randint(0, len(nums) - 1)
    # 获取并返回随机元素
    random_num = nums[random_index]
    return random_num

插入元素

1. 把索引 index 及以后的所有元素向后移动一位
2. 把插入的元素赋值给 索引处 index

def insert(nums: list[int], num: int, index: int):
    """在数组的索引 index 处插入元素 num"""
    # 把索引 index 以及之后的所有元素向后移动一位
    for i in range(len(nums) - 1, index, -1):
        nums[i] = nums[i - 1]
    # 将 num 赋给 index 处的元素
    nums[index] = num

删除元素

把索引 index 及以后的所有元素向前移动一位

def remove(nums: list[int], index: int):
    """删除索引 index 处的元素"""
    # 把索引 index 之后的所有元素向前移动一位
    for i in range(index, len(nums) - 1):
        nums[i] = nums[i + 1]

遍历数组

1. 通过索引
2. 直接遍历
3. 同时遍历索引和数据 enumerate()

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

查找元素

遍历+判断

def find(nums: list[int], target: int) -> int:
    """在数组中查找指定元素"""
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

扩容数组

原因：数组的长度是不可变的

初始化+复制粘贴

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

优点

• 空间效率高
• 支持随机访问
• 缓存局部性

缺点

• 插入与删除效率低
• 长度不可变
• 空间浪费

链表

「链表 linked list」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。 引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点

链表=节点（值和指向下一个的引用）的总和

class ListNode:
    """链表节点类"""
    def __init__(self, val: int):
        self.val: int = val               # 节点值
        self.next: ListNode | None = None # 指向下一节点的引用

头节点：首个节点

尾节点：最后节点 →None

初始化链表

# 初始化链表 1 -> 2 -> 3 -> 4 -> 5
# 初始化各个节点
n0 = ListNode(1)
n1 = ListNode(2)
n2 = ListNode(3)
n3 = ListNode(4)
n4 = ListNode(5)
# 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

插入节点

P先指向后面的，前面的指向P

def insert(n0: ListNode, P: ListNode):
    """在链表的节点 n0 之后插入节点 P"""
    n1 = n0.next
    P.next = n1
    n0.next = P

删除节点

index 前面的直接指向后面的

def remove(n0: ListNode):
    """删除链表的节点 n0 之后的首个节点"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next # 就算P是None也可以
    n0.next = n1

访问节点

遍历

_ 为占位符，用于迭代不需要这个值时

def access(head: ListNode, index: int) -> ListNode | None:
    """访问链表中索引为 index 的节点"""
    for _ in range(index):
        if not head: # 检查当前的 head 节点是否为 None，链表末尾或者链表为空
            return None
        head = head.next
    return head

查找节点

遍历

def find(head: ListNode, target: int) -> int:
    """在链表中查找值为 target 的首个节点"""
    index = 0
    while head: # head = None 不进行循环
        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.next: ListNode | None = None  # 指向后继节点的引用
        self.prev: ListNode | None = None  # 指向前驱节点的引用
        # 实际上是self.prev = None 要这样看

数组与链表的效率对比

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	O(1)	O(n)
添加元素	O(n)	O(1)
删除元素	O(n)	O(1)

---

列表

list.clear() 清空列表

list.append(number) 尾部添加元素

list.insert(index, number) 在索引处插入元素

list.pop(index) 删除索引处元素

len(list) 返回列表的长度

list1 + list2 列表拼接

list.sort() 列表排序

class MyList:
    """列表类"""

    def __init__(self):
        """构造方法"""
        # 以单个下划线 _ 开头的属性或方法被视为受保护的（protected），这意味着它们是类内部使用的，不应该被外部直接访问
        self._capacity: int = 10  # 列表容量
        self._arr: list[int] = [0] * self._capacity  # 数组（存储列表元素）
        self._size: int = 0  # 列表长度（当前元素数量）
        self._extend_ratio: int = 2  # 每次列表扩容的倍数

    def size(self) -> int:
        """获取列表长度（当前元素数量）"""
        return self._size

    def capacity(self) -> int:
        """获取列表容量"""
        return self._capacity

    def get(self, index: int) -> int:
        """访问元素"""
        # 索引如果越界，则抛出异常，下同
        if index < 0 or index >= self._size:
            raise IndexError("索引越界")
        return self._arr[index]

    def set(self, num: int, index: int):
        """更新元素"""
        if index < 0 or index >= self._size:
            raise IndexError("索引越界")
        self._arr[index] = num

    def add(self, num: int):
        """在尾部添加元素"""
        # 元素数量超出容量时，触发扩容机制
        if self.size() == self.capacity():
            self.extend_capacity()
        self._arr[self._size] = num
        self._size += 1

    def insert(self, num: int, index: int):
        """在中间插入元素"""
        if index < 0 or index >= self._size:
            raise IndexError("索引越界")
        # 元素数量超出容量时，触发扩容机制
        if self._size == self.capacity():
            self.extend_capacity()
        # 将索引 index 以及之后的元素都向后移动一位
        for j in range(self._size - 1, index - 1, -1):
            self._arr[j + 1] = self._arr[j]
        self._arr[index] = num
        # 更新元素数量
        self._size += 1

    def remove(self, index: int) -> int:
        """删除元素"""
        if index < 0 or index >= self._size:
            raise IndexError("索引越界")
        num = self._arr[index]
        # 将索引 index 之后的元素都向前移动一位
        for j in range(index, self._size - 1):
            self._arr[j] = self._arr[j + 1]
        # 更新元素数量
        self._size -= 1
        # 返回被删除的元素
        return num

    def extend_capacity(self):
        """列表扩容"""
        # 新建一个长度为原数组 _extend_ratio 倍的新数组，并将原数组复制到新数组
        self._arr = self._arr + [0] * self.capacity() * (self._extend_ratio - 1)
        # 更新列表容量
        self._capacity = len(self._arr)

    def to_array(self) -> list[int]:
        """返回有效长度的列表"""
        return self._arr[: self._size]