数据结构与算法入门:数组、链表与栈

数据结构是程序的骨架。本文用最直观的方式介绍三种基础结构--数组、链表、栈,重点对比它们的内存模型与时间复杂度。

1. 数组(Array)

数组在内存中是一段连续的空间,每个元素大小相同。因此可以通过"起始地址 + 下标 × 元素大小"直接定位--这就是随机访问 O(1) 的原因。

arr = [10, 20, 30, 40]
print(arr[2])      # 30, 直接寻址 O(1)
arr.append(50)     # 尾部追加, 均摊 O(1)
arr.insert(0, 5)   # 头部插入, 需要搬移所有元素 O(n)
arr.remove(20)     # 删除同样需要搬移 O(n)

2. 链表(Linked List)

链表由一个个节点组成,每个节点存数据 + 指向下一个节点的指针。内存不必连续,插入删除只需改指针,但查找必须从头遍历。

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

# 构建: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

# 遍历
cur = head
while cur:
    print(cur.val, end=" ")
    cur = cur.next   # 1 2 3

3. 栈(Stack)

栈是"后进先出"(LIFO)的线性结构,只有栈顶能进出。想象一叠盘子:后放的先拿走。函数调用、括号匹配、浏览器后退都用它实现。

stack = []
stack.append(1)   # push 入栈
stack.append(2)
stack.append(3)
print(stack.pop())  # pop 出栈: 3
print(stack[-1])    # peek 看栈顶: 2

# 经典应用: 括号匹配
def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in s:
        if ch in "([{":
            st.append(ch)
        elif not st or st.pop() != pairs[ch]:
            return False
    return not st

print(is_valid("({[]})"))   # True
print(is_valid("([)]"))     # False

4. 复杂度对比

* 双向链表维护尾指针时可 O(1)

5. 怎么选?

• 读多写少、按下标访问 → 数组(大多数场景的默认选择);
• 频繁在中间/头部增删 → 链表;
• 需要"撤销""回溯""匹配"语义 → 栈。

6. 队列(Queue):先进先出

队列和栈正好相反:先进先出(FIFO),就像排队买奶茶,先来的先服务。任务调度、消息队列、BFS 广度优先搜索都靠它。

from collections import deque

queue = deque()
queue.append("任务A")   # 入队
queue.append("任务B")
queue.append("任务C")

print(queue.popleft())  # 出队: 任务A
print(queue.popleft())  # 出队: 任务B
print(len(queue))       # 还剩 1 个

# 经典应用: BFS 二叉树层序遍历(简化版)
def bfs(root):
    if not root:
        return []
    q, result = deque([root]), []
    while q:
        node = q.popleft()
        result.append(node.val)
        if node.left:  q.append(node.left)
        if node.right: q.append(node.right)
    return result

注意:list.pop(0) 是 O(n) 的(要搬移后面所有元素),所以实现队列请用 collections.deque,两端操作都是 O(1)。

💡 学习路径建议:掌握这三种后,继续学队列、哈希表、二叉树,再配合 LeetCode 每日一题练习,数据结构就算入门了。