> ## Documentation Index
> Fetch the complete documentation index at: https://docs.0907world.cn/llms.txt
> Use this file to discover all available pages before exploring further.
# 第 2 章 线性表
本章重点复习线性表这一基础数据结构，包括其逻辑结构特征，以及在计算机中两种截然不同的物理实现：顺序表与链表重点在于掌握不同存储结构下各种基本操作的时间复杂度差异及适用场景
## 线性表的定义
* **表中元素的个数有限**
* 表中元素具有逻辑上的顺序性，均为数据元素，数据类型都相同，具有抽象性
**背景说明**：在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，常把数据元素称为**记录**，含有大量记录的线性表又称为**文件**
**结论**：线性表是一种**逻辑结构**，表示元素之间一对一的相邻关系
## 线性表的表示
### 顺序表
**核心特征**：逻辑顺序与其物理存储顺序完全一致
**主要优点**
* 可进行随机访问，按索引查找速度快
* 存储密度高，不需要额外指针空间
**主要缺点**
* 插入和删除操作效率较低，需要移动大量元素
* 要求分配连续的存储空间，可能产生空间浪费或溢出
* **初始化**：静态分配或动态分配
* **插入操作**：
* 最好情况：在尾部插入，$O(1)$
* 最坏情况：在表头插入，$O(n)$
* 平均情况：$O(n)$
* **删除操作**：
* 最好情况：删除表尾元素，$O(1)$
* 最坏情况：删除表头元素，$O(n)$
* 平均情况：$O(n)$
* **查找操作**：
* 按值查找：$O(n)$
* 按索引查找：$O(1)$
* **双指针**：如王道 P20 05
* **倒置**：如王道 P20 07、10
* **Boyer–Moore 投票算法**：如王道 P20 12
* **空间换时间**：如王道 P21 13
### 链表
数据元素的存储映像称为**结点**，其中存储数据元素信息的域称为**数据域**，存储直接后继存储位置的域称为**指针域**
* **求表长操作**：$O(n)$
* **按序号查找节点**：$O(n)$
* **按值查找表节点**：$O(n)$
* **插入节点操作**（含查找）：$O(n)$
* **删除节点操作**（含查找）：$O(n)$
* **头插法建立单链表**：$O(n)$
* **尾插法建立单链表**：$O(n)$
尾结点的指针域指向头结点，形成环状结构适合处理需要反复遍历的场景
每个结点包含两个指针域，分别指向前驱和后继可以双向遍历，在已知结点位置时，插入和删除操作更为高效
借用一维数组来描述线性链表
* 含备用链
* 不含备用链
* **快慢指针**：用于找中点、判环等如王道 P44 15、16、17、20
* **公共节点**：求两个链表的交点如王道 P43 05、P45 18
* **空间换时间**：如王道 P45 19