一、线性表
1. 线性表的基本概念
线性表（Linear List）是一种基本的数据结构，由一组具有相同数据类型的元素构成，这些元素按线性顺序排列。每个元素（除首尾外）均有唯一的前驱和后继元素。线性表的逻辑结构表现为一条'线'，元素之间是一对一的关系。线性表的特点主要有有限性、有序性、同质性。并且线性表在逻辑结构上连续的但在物理结构上不一定连续。
2. 线性表的储存方式
- 顺序存储（顺序表）：使用连续的物理内存单元存储元素，通过数组实现。支持随机访问，但插入/删除需移动大量元素。
- 链式存储（链表）：通过节点（包含数据域和指针域）动态分配内存，节点间通过指针链接。插入/删除高效，但访问需遍历。
3. 常见线性表类型
- 顺序表：基于数组实现，如 C++ 的
vector、Java 的ArrayList。 - 单链表：每个节点指向后继，如
LinkedList。 - 双向链表：节点包含前驱和后继指针。
- 循环链表：尾节点指向头节点形成环。
4. 线性表的基本操作
- 插入：在指定位置添加新元素。
- 删除：移除指定位置的元素。
- 查找：根据值或位置检索元素。
- 修改：更新指定位置的元素值。
- 遍历：按顺序访问所有元素。
二、顺序表
1. 顺序表的基本概念
顺序表是一种线性表的存储结构，通过连续的物理存储单元依次存放数据元素。其逻辑顺序与物理顺序一致，通常采用数组实现，支持随机访问。顺序表在逻辑结构和物理结构上都具有连续性，这使得其有储存连续的特点，除此之外还具有随机访问、大小固定、插入或删除效率低等特点。
2. 顺序表的两种形式
-
静态顺序表
-
动态顺序表
注：因静态顺序表数组大小给定，给大了易造成空间浪费，给小了空间不够，所以现实中静态顺序表不常用，因此接下来的实现以动态顺序表为主。
3. 顺序表的基本操作
- 初始化：分配固定大小的数组空间，记录当前元素数量（长度）。
- 插入操作：在指定位置插入元素，需将后续元素后移。若空间不足，需先扩容。
- 删除操作：移除指定位置元素，并将后续元素前移。
