D13. 线性数据结构
3.1 数组是线性数据结构的基础
目标：理解数组的内存特性及动态扩容机制。
3.1.1 数组的内存特性
数组元素在内存中连续存储，每个元素的地址可通过基地址+偏移量直接计算。
- 优势：支持随机访问（时间复杂度O(1)）。
- 限制：插入/删除非末尾元素需移动其他元素（时间复杂度O(n)）。
JavaScript数组的自动扩容
javascript
// JavaScript数组底层类似动态数组（如C++的vector）
let arr = [1, 2, 3]; // 初始容量3
arr.push(4); // 尾部插入O(1)
arr.unshift(0); // 头部插入需移动所有元素O(n)扩容机制： 当数组长度超过当前容量时，会分配更大空间（通常2倍扩容），并将旧元素复制到新空间。
时间代价：单次扩容O(n)，但摊还均摊到每次操作为O(1)。
3.2 栈与队列适合处理顺序问题
目标：掌握栈和队列的特性及典型应用场景。
3.2.1 栈：后进先出（LIFO）
javascript
class Stack {
constructor() {
this.items = [];
}
push(item) { this.items.push(item); } // 入栈：O(1)
pop() { return this.items.pop(); } // 出栈：O(1)
peek() { return this.items[this.items.length-1]; } // 查看栈顶
}经典应用：
- 函数调用栈：记录方法调用顺序。
- 括号匹配：用栈验证符号是否成对闭合。
- 回退功能：浏览器历史记录的“前进”和“后退”。
3.2.2 队列：先进先出（FIFO）
javascript
class Queue {
constructor() {
this.items = [];
}
enqueue(item) { this.items.push(item); } // 入队：O(1)
dequeue() { return this.items.shift(); } // 出队：O(n)（需移动元素）
front() { return this.items[0]; } // 查看队头
}优化建议： 使用双指针（front和rear）实现常数时间出队（如Java的LinkedList）。
经典应用：
- 任务调度：操作系统进程调度。
- 消息队列：异步处理任务。
3.3 链表大幅降低插入和删除成本
目标：理解链表的结构优势及适用场景。
3.3.1 链表的结构
javascript
// 单向链表节点
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 链表类
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 插入、删除等操作需遍历找到目标节点
}核心特性：
- 插入/删除效率：仅需修改相邻节点的指针，时间复杂度O(1)（需找到位置后）。
- 内存不连续：无法随机访问，需从头遍历（时间复杂度O(n)）。
3.3.2 链表与数组的对比
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 尾部插入 | O(1) | O(1)* |
| 中间插入 | O(n) | O(1)*（找到位置后） |
| 内存连续 | 是 | 否 |
注：链表需先遍历找到插入位置，总时间复杂度为O(n)。
3.3.3 链表的变体
- 双向链表：每个节点包含
prev和next指针，支持双向遍历。 - 循环链表：尾节点的
next指向头节点，无头尾之分。 - Java实现差异：
ArrayList（基于动态数组）：随机访问快，但中间操作慢。LinkedList（基于双向链表）：插入/删除快，但随机访问慢。
知识回顾
- 数组：内存连续，随机访问快，但中间插入/删除效率低。
- 栈：后进先出，适合需要回退或匹配顺序的场景。
- 队列：先进先出，适用于任务调度和资源分配。
- 链表：通过指针连接节点，插入/删除高效，但失去随机访问能力。
- 动态数组：通过扩容机制平衡固定大小与动态需求，摊还复杂度O(1)。
课后练习
选择题：以下哪种数据结构适合实现浏览器的前进/后退功能？
- A. 栈
- B. 队列
- C. 双向链表
代码题：实现一个支持
O(1)时间出队的队列（提示：使用双指针或尾指针）。分析题：比较Java中
ArrayList和LinkedList在以下操作中的性能差异：- 插入元素到中间位置。
- 遍历所有元素。
扩展阅读
- 动态数组实现细节：
- 摊还分析（Amortized Analysis）：解释为何多次扩容操作均摊为O(1)。
- 链表优化：
- 哈希表的链地址法（解决哈希冲突）。
- 图的邻接表表示（用链表存储顶点的邻接边）。
- 真实场景应用：
- LRU缓存：用队列或链表维护最近访问顺序。
- 内存管理：操作系统用链表管理空闲内存块。