一、线性表核心概念

线性表是n个数据元素的有序序列，元素间呈“一对一”逻辑关系（除首尾元素外，每个元素有唯一前驱和后继），常见实现：数组（顺序表）、链表。

二、顺序表（数组实现）

• 存储特点：元素连续存储在一块固定大小的内存中，用数组下标直接访问。

• 核心操作：

1. 访问：O(1)（通过下标直接定位）；

2. 插入/删除：O(n)（需移动后续元素腾出位置或填补空缺）；

3. 扩容：数组满时需创建新数组，复制原元素（时间开销较大）。

• 优缺点：查询快、结构简单；插入删除效率低、固定容量易溢出。

三、链表（节点链式存储）

• 存储特点：元素（节点）分散存储，每个节点含数据域和指针域（指向下一节点），无需连续内存。

• 常见类型：

1. 单链表：仅含后继指针，只能单向遍历；

2. 双链表：含前驱+后继指针，双向遍历更灵活；

3. 循环链表：首尾节点相连，可循环访问（适合环形场景）。

• 核心操作：

1. 访问：O(n)（需从表头遍历查找）；

2. 插入/删除：O(1)（找到节点后，仅需修改指针指向）；

3. 无扩容问题（按需创建节点）。

• 优缺点：插入删除灵活、不浪费内存；查询效率低、需额外存储指针。

四、顺序表与链表对比

• 优先用顺序表：查询频繁、元素数量稳定（如查询成绩排名）；

• 优先用链表：插入删除频繁、元素数量不确定（如增删购物车商品）。