数据结构与算法-2线性结构

o( ￣⌣￣ )o included in Computer Science

2025-06-08 6188 words 13 minutes

Contents

概述

线性结构是数据结构中最基础、最核心的部分，其特点是数据元素之间存在一对一的线性关系。常见的线性结构包括数组、链表、栈和队列，它们既是独立的数据结构，也是构建更复杂结构（如树、图）的基础单元。

本章节将从存储原理出发，依次深入探讨数组与链表这两种底层存储方式，以及基于它们实现的栈和队列。

一、数组

1.1 基本概念

数组（Array）是一种顺序存储的线性表，其核心特征是：

元素在内存中连续存储，地址计算公式为 $Loc(e_i) = Loc(e_0) + c \times i$
每个元素占用大小固定相同的存储单元
支持随机访问，访问时间复杂度为 O(1)
大多数编程语言在未指定初始值时，会将数组元素初始化为 0

顺序表与数组的关系：顺序表是一种用地址连续的存储单元依次存储线性表数据的结构，可以由数组实现。顺序表通常会对数组进行封装，提供动态扩容、插入、删除等操作。

1.2 数组的实现方式

实现方式	特点	更换数据区时的操作
一体式	结构紧凑，创建后元素存储区固定	只能整体搬迁整个顺序表对象
分离式	表对象与元素存储区通过指针链接	只需更新表信息区中的链接地址，顺序表对象本身不变

1.3 动态数组与扩容机制

数组长度固定，只能视为有长度限制的列表。动态数组则支持在使用过程中自动扩容，Python 中的 list 就是基于分离式技术的动态数组实现。

扩容策略	实现方式	优缺点
线性增长	每次增加固定数量（如 10 个槽位）	节省空间，但扩容次数多，频繁复制数据
指数增长（推荐）	每次容量加倍	减少扩容次数，提高插入效率；以空间换时间

Python 列表采用过度分配策略：扩容时新分配空间约为 当前容量 + floor(当前容量 / 8) + 常数（3或6），即每次扩容增长量约为当前容量的 12.5%。这种设计使 append 操作的平均时间复杂度为 O(1)，同时避免分配过多未使用内存。

1.4 核心算法

数组领域的核心算法包括：二分查找、双指针技巧、滑动窗口。

二分查找

二分查找基于分治策略，利用数据的有序性，每轮将搜索范围缩小一半。

优点：查找效率高，无需额外存储空间。

局限：只适用于有序数据；不适用于链表（无法跳跃访问）。

闭区间写法（左闭右闭）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def binary_search(nums: list[int], target: int) -> int:
    """二分查找非递归实现"""
    first = 0
    last = len(nums) - 1
    while first <= last:
        midpoint = first + (last - first) // 2
        if nums[midpoint] < target:
            first = midpoint + 1
        elif nums[midpoint] > target:
            last = midpoint - 1
        else:
            return midpoint
    return -1

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binary_search(testlist, 3))   # -1
print(binary_search(testlist, 13)) # 4

开区间写法（左闭右开）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def binary_search_lcro(nums: list[int], target: int) -> int:
    """二分查找左闭右开区间写法"""
    first = 0
    last = len(nums)
    while first < last:
        midpoint = first + (last - first) // 2
        if nums[midpoint] < target:
            first = midpoint + 1
        elif nums[midpoint] > target:
            last = midpoint
        else:
            return midpoint
    return -1

递归实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def binary_search(alist, item):
    """二分查找递归实现"""
    if len(alist) == 0:
        return False
    midpoint = len(alist) // 2
    if alist[midpoint] == item:
        return True
    elif item < alist[midpoint]:
        return binary_search(alist[:midpoint], item)
    else:
        return binary_search(alist[midpoint + 1:], item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
# 最优时间复杂度：O(1)
# 最坏时间复杂度：O(logn)

二分查找变种：

LC 528：按权重随机选择
左侧边界查找 / 右侧边界查找（用于定位元素适合的插入点）

滑动窗口

滑动窗口是一种常用的算法思想，主要应用于数组和字符串的处理中。它可以把嵌套的循环问题，转换为单循环问题，降低时间复杂度滑动窗口的基本思想是，维护一个固定大小的窗口，窗口通过不断滑动来遍历整个数据集合。在窗口内部进行某些操作，如求最大值、最小值、平均值等等以求解数组连续子数组的和为例，滑动窗口可以通过维护左右指针来实现：初始时，左指针指向数组的第一个元素，右指针指向第 k 个元素（k 为窗口大小），窗口内的和为 S。然后，移动右指针，移动左指针，并再次更新窗口内的和，直到右指针到达数组的末尾，同时不断更新窗口内的和。这样，就可以得到所有长度为 k 的子数组的和使用滑动窗口可以有效地解决一些数组和字符串相关的问题，特别是在需要 连续子数组或子字符串的问题 中，滑动窗口可以缩小搜索空间，减少不必要的操作，降低时间复杂度

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


from collections import Counter

def sliding_window_template_with_examples(s, p):
    counter = Counter(p)
    start, end = 0, 0
    count = 0
    res = 0
    while end < len(s):
        counter[s[end]] += 1
        if counter[s[end]] > 1:
            count += 1
        end += 1
        while count > 0:
            # 寻找最小窗口时在此更新 res
            counter[s[start]] -= 1
            if counter[s[start]] > 0:
                count -= 1
            start += 1
        # 寻找最大窗口时在此更新 res
        res = max(res, end - start)
    return res

典型应用：

LC 1423：可获得的最大点数
LC 3：无重复字符的最长子串
LC 1004：最大连续 1 的个数 III

注意：滑动窗口通常需要保存当前最优和全局最优两个状态。

双指针

双指针算法的基本思路是，定义两个指针分别指向数组或链表中的不同位置，然后根据问题的要求不断移动这两个指针。通常情况下，移动的方向是相同的，即向前或向后，也有可能是相反的，即向中间靠拢，如求解最大回文子串的问题在求解两数之和的问题中，双指针算法可以通过将数组排序，然后使用双指针从数组两端向中间移动来查找，时间复杂度可以降低到 O(n log n) 在求解三数之和的问题中，双指针算法通常需要先将数组排序，然后使用一个指针固定位置，再用另外两个指针分别从左右两端向中间移动，寻找符合要求的三个数之和，时间复杂度为 O(n^2) 在链表中使用双指针通常是为了找到链表中点或判断链表是否存在环。其中，找到链表中点的算法可以使用快慢指针，即使用一个指针每次走一步，另外一个指针每次走两步，当快指针走到链表末尾时，慢指针指向的节点即为链表中点。判断链表是否存在环也可以使用快慢指针，当快指针与慢指针相遇时，即可判断链表中存在环双指针算法的优点在于 不需要额外的辅助空间，常常可以降低时间复杂度。但它也有一定的局限性，比如 无法处理存在多个解 的问题

常见模式：

1
2
3
4
5


# 双指针的几种典型应用场景
# 1. 快慢指针：slow-> fast-> (找中点、判环)
# 2. 对撞指针：left-> <-right (两数之和、回文判断)
# 3. 滑动窗口边界：start-> end-> (子串问题)
# 4. 双序列指针：p1-> p2-> (合并有序链表)

应用场景：

两数之和：排序后使用双指针，时间复杂度 O(n log n)
三数之和：固定一个指针，双指针搜索另外两个，时间复杂度 O(n²)
合并有序数组/链表：双指针遍历两个序列
去除重复元素：新旧状态迭代

快慢指针链表应用：

找链表中点：快指针每次走两步，慢指针每次走一步
判断链表环：快慢指针相遇则存在环

双指针的优点是不需要额外辅助空间，可降低时间复杂度；但局限性在于无法处理存在多个解的问题。

二、链表

2.1 基本概念

链表（Linked List）是一种非连续存储的数据结构，它通过在每个节点存放指向下一个节点的指针来实现灵活的内存动态管理。

单链表结构：头节点 → 首元节点 → 普通节点 → … → 尾节点

与数组对比：

特性	数组（Array）	链表（Linked List）
存储方式	连续存储，内存连续	非连续存储，通过指针链接
访问速度	随机访问，O(1)	顺序访问，平均 O(n)
大小固定	是	否，动态大小
插入/删除	较慢，需移动元素	较快，仅调整指针
空间效率	较好，无额外指针	较差，需额外指针空间

顺序表需要预先申请连续存储空间，扩充时需搬迁数据；链表则可以充分利用零散内存空间。

2.2 链表翻转

迭代翻转：

1
2
3
4
5
6


def reverse_iteratively(head: ListNode):
    prev, cur = None, head
    while cur:
        # 改变指向后，两个指针各向前移动一格
        cur.next, cur, prev = prev, cur.next, cur
    return prev

递归翻转：

1
2
3
4
5
6
7
8


def reverse_recursively(head: ListNode):
    def recursive(cur, pre=None):
        if not cur:
            return pre
        # 暂存下一节点，调整指向，递归处理
        pre, cur.next = cur.next, pre
        return recursive(pre, cur)
    return recursive(head)

注意：Python 中 a, b = b, a 这种元组赋值操作，会先计算右侧表达式的所有值，再依次赋值给左侧变量。

2.3 核心算法

链表领域的核心算法包括：反转链表、环检测、合并有序链表、LRU 缓存淘汰。

快慢指针（Floyd 判圈法）：用于判断链表是否存在环，以及找到环的入口节点。

三、栈

3.1 基本概念

栈（Stack）是一种先入后出（LIFO）的线性数据结构，其特点是保证任何时候可访问、删除的元素都是最后存入的那个元素。

常用操作（时间复杂度均为 O(1)）：入栈（push）、出栈（pop）、获取栈顶元素（top）。

3.2 应用场景

函数调用栈（函数调用与返回的管理）
括号匹配（表达式语法检查）
浏览器的前进、后退功能
软件中的撤销、恢复操作

3.3 核心算法

基于链表的栈实现：入栈操作只需将元素插入链表头部（头插法）。

单调栈：用于解决 Next Greater Element（一元素右侧首个更大元素）问题。

1
2
3
4
5
6


stack = []
for i in range(len(nums)):
    while stack and nums[i] > stack[-1]:
        # 处理单调递减栈中的元素
        stack.pop()
    stack.append(nums[i])

四、队列

4.1 基本概念

队列（Queue）是一种先入先出（FIFO）的线性表，只允许在一端插入（队尾），在另一端删除（队头）。

假设队列为 q = (a₁, a₂, …, aₙ)，其中 a₁ 是队头元素，aₙ 是队尾元素。

4.2 应用场景

BFS（广度优先搜索）算法的基础
滑动窗口问题的实现
消息队列、任务调度

4.3 核心算法

双向队列（Deque）

双向队列（Double-ended Queue，简称 Deque）是一种支持在两端进行插入和删除的线性数据结构。相比普通队列只能一端进、另一端出，Deque 更加灵活。

常用操作（时间复杂度均为 O(1)）：

appendleft(x) / append(x)：在左/右端添加元素
popleft() / pop()：从左/右端删除元素

Python 实现：

1
2
3
4
5
6
7
8


from collections import deque

dq = deque()
dq.append(1)       # 右端入队：[1]
dq.append(2)       # 右端入队：[1, 2]
dq.appendleft(0)   # 左端入队：[0, 1, 2]
print(dq.pop())    # 2，右端出队
print(dq.popleft()) # 0，左端出队

典型应用：

滑动窗口问题（配合单调队列效果更佳）
实现栈（作为栈的替代）
浏览器前进/后退功能

单调队列：滑动窗口最大值

单调队列在普通队列的基础上增加了单调性维护，常用于解决滑动窗口最值问题。其核心思想是维护一个单调递减（或递增）的队列。

问题场景：给定数组和一个滑动窗口大小 k，求每个窗口内的最大值。

思路：维护一个单调递减队列，队首始终是当前窗口的最大值。

 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


from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """滑动窗口最大值"""
    if not nums or k == 0:
        return []

    deque_index = deque()  # 存储索引
    result = []

    for i, num in enumerate(nums):
        # 1. 新元素入队前，先把超出窗口范围的元素移除
        while deque_index and deque_index[0] <= i - k:
            deque_index.popleft()

        # 2. 维护单调性：移除所有比新元素小的元素索引
        while deque_index and nums[deque_index[-1]] <= num:
            deque_index.pop()

        # 3. 新元素入队
        deque_index.append(i)

        # 4. 窗口形成后，记录当前窗口的最大值（队首索引对应的元素）
        if i >= k - 1:
            result.append(nums[deque_index[0]])

    return result

# 示例
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))  # [3, 3, 5, 5, 6, 7]

时间复杂度：每个元素最多入队和出队各一次，整体 O(n)。

表达式求值：中缀转后缀

表达式求值通常通过将中缀表达式转换为后缀表达式（逆波兰表达式）来实现。

核心规则：

操作数：直接输出
左括号 (：入栈
右括号 )：弹出栈中元素直至遇到左括号
操作符：弹出优先级不低于当前操作符的所有元素，再将当前操作符入栈

 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


def infix_to_postfix(expr: str) -> str:
    """中缀表达式转后缀表达式"""
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '%': 2}
    stack = []
    output = []

    for token in expr.replace(' ', ''):
        if token.isdigit():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 弹出左括号
        elif token in precedence:
            while (stack and stack[-1] != '(' and
                   precedence.get(stack[-1], 0) >= precedence[token]):
                output.append(stack.pop())
            stack.append(token)

    # 弹出剩余操作符
    while stack:
        output.append(stack.pop())

    return ''.join(output)

# 示例：1 + 2 * 3 -> 123*+
#      (1 + 2) * 3 -> 12+3*
print(infix_to_postfix("1+2*3"))    # 123*+
print(infix_to_postfix("(1+2)*3")) # 12+3*

后缀表达式求值：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


def evaluate_postfix(postfix: str) -> int:
    """计算后缀表达式的值"""
    stack = []
    operators = {'+', '-', '*', '/', '%'}

    for token in postfix:
        if token.isdigit():
            stack.append(int(token))
        elif token in operators:
            b, a = stack.pop(), stack.pop()
            if token == '+': result = a + b
            elif token == '-': result = a - b
            elif token == '*': result = a * b
            elif token == '/': result = int(a / b)  # 整数除法
            elif token == '%': result = a % b
            stack.append(result)

    return stack[0]

print(evaluate_postfix("123*+"))  # 7 (1 + 2 * 3)

循环队列：数组实现

普通队列用数组实现时，删除操作会导致队首后面的元素整体前移，时间复杂度 O(n)。循环队列通过取模运算实现空间复用，避免元素迁移。

核心原理：当队尾到达数组末端时，环绕到数组开头继续存储。

 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


class MyCircularQueue:
    """循环队列实现"""

    def __init__(self, k: int):
        self.capacity = k
        self.queue = [0] * k
        self.head = self.tail = 0
        self.size = 0

    def enqueue(self, value: int) -> bool:
        """入队"""
        if self.size == self.capacity:
            return False
        self.queue[self.tail] = value
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1
        return True

    def dequeue(self) -> bool:
        """出队"""
        if self.size == 0:
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def front(self) -> int:
        """获取队首元素"""
        if self.size == 0:
            return -1
        return self.queue[self.head]

    def rear(self) -> int:
        """获取队尾元素"""
        if self.size == 0:
            return -1
        return self.queue[(self.tail - 1) % self.capacity]

    def is_empty(self) -> bool:
        return self.size == 0

    def is_full(self) -> bool:
        return self.size == self.capacity

注意：需要预留一个槽位来区分队空和队满状态，或者额外维护一个 size 字段。

链表实现无界队列

相比数组实现的循环队列，链表实现的无界队列天然支持动态扩容，不存在容量上限。

 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


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedQueue:
    """链表实现的无界队列"""

    def __init__(self):
        self.head = None  # 队头，用于出队
        self.tail = None  # 队尾，用于入队
        self.size = 0

    def enqueue(self, value: int) -> bool:
        """入队：O(1)"""
        new_node = ListNode(value)
        if not self.tail:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
        return True

    def dequeue(self) -> int:
        """出队：O(1)"""
        if not self.head:
            return None
        value = self.head.val
        self.head = self.head.next
        if not self.head:
            self.tail = None
        self.size -= 1
        return value

    def front(self) -> int:
        return self.head.val if self.head else None

    def is_empty(self) -> bool:
        return self.size == 0

最小栈：O(1) 获取最小元素

普通栈的 get_min() 操作需要遍历整个栈，时间复杂度 O(n)。最小栈通过额外维护一个栈来记录当前最小值，实现 O(1) 获取最小元素。

 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


class MinStack:
    """最小栈：在 O(1) 时间复杂度内获取栈内最小元素"""

    def __init__(self):
        self.stack = []
        self.min_stack = []  # 同步维护当前最小值

    def push(self, val: int) -> None:
        self.stack.append(val)
        # 同步更新最小栈
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            return None
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1] if self.stack else None

    def get_min(self) -> int:
        """获取最小元素：O(1)"""
        return self.min_stack[-1] if self.min_stack else None

# 示例
ms = MinStack()
ms.push(3)
ms.push(5)
ms.push(1)
ms.push(2)
print(ms.get_min())  # 1
ms.pop()
print(ms.get_min())  # 3

技巧：min_stack 与原栈同步维护，存储每次入栈后的当前最小值。空间换时间。

五、数组与链表的综合对比

维度	数组	链表
存储方式	连续内存	分散内存，通过指针链接
访问方式	随机访问 O(1)	顺序访问 O(n)
插入/删除	需移动元素 O(n)	仅调整指针 O(1)
空间预分配	需要预先分配固定大小	按需分配，动态扩容
空间效率	紧凑，无额外开销	每个节点需存指针，有额外开销
缓存友好性	优秀（连续内存）	较差（访问不连续）

链表插入/删除 O(1) 指指针调整操作本身；实际应用中需先定位元素位置，整体仍为 O(n)。

拓展与后续学习建议

深入进阶方向
- 学习散列表（Hash Table）的实现原理与冲突解决策略
- 掌握优先队列（堆）的实现，了解其如何利用数组实现完全二叉树
- 研究递归与栈的关系，理解递归如何转化为迭代
算法练习建议
- 在 LeetCode 上按"数据结构"分类刷题，系统覆盖数组、链表、栈、队列的基础题型
- 重点练习双指针与滑动窗口的变式问题，这两类技巧在面试中出现频率很高
- 尝试将栈和队列的题目与实际应用场景结合，如括号匹配、表达式求值
工程实践视角
- 了解 Python list、collections.deque 等内置数据结构的底层实现
- 研究常见编程语言（如 Java ArrayList、Go slice）如何实现动态数组
- 关注数据结构选型对系统性能的影响，如缓存命中、内存分配策略等