学习目标
- 理解线性表的逻辑结构和物理实现方式。
- 掌握顺序表和链表的实现原理及核心操作。
- 能够通过代码实现顺序表和链表的基本功能。
- 分析顺序表与链表的性能差异及适用场景。
重点与难点
- 重点：顺序表的动态增容、链表的指针操作、时间复杂度分析。
- 难点：链表节点的插入与删除逻辑、顺序表与链表的性能权衡。
线性表概述
定义
线性表是由 n 个具有相同特性的元素组成的有限序列，元素之间有明确的前后关系。每个元素有唯一的前驱和后继元素。线性表可以是顺序存储或链式存储。
- 逻辑结构：线性表是逻辑上的顺序排列，指的是元素之间的关系是依次排列的，每个元素都有一个明确的前后关系。
- 物理结构：线性表的元素在计算机内存中的存储方式，可以是连续的（顺序表）或者不连续的（链表）。
基本特性
- 元素的顺序性：线性表中元素的顺序关系决定了元素之间的前后依赖关系，通常我们按从第一个元素到最后一个元素的顺序进行访问。
- 唯一性：每个元素在序列中有唯一的前驱和后继元素，只有第一个元素没有前驱，最后一个元素没有后继。
- 有限性：线性表包含一个有限的元素集合，且元素数量固定。
常见实现方式
线性表有两种常见的物理存储方式：顺序存储和链式存储。
顺序存储（顺序表）
顺序存储使用一段连续的内存空间存储数据，通常使用数组来实现。数据元素在内存中的地址是连续的，因此可以通过索引来直接访问。
- 优点：
- 高效的随机访问：可以通过索引直接访问任意位置的元素，时间复杂度为 O(1)。
- 空间效率高：在内存中是连续存储，相对来说能够更高效地利用内存。
- 缺点：
- 插入和删除效率较低：在顺序表中间插入或删除元素时，需要移动大量的元素，时间复杂度为 O(N)。
- 固定容量问题：顺序表的容量一旦固定，后期无法动态调整空间，需要使用动态扩容，但扩容可能导致空间浪费。
链式存储（链表）
链表使用非连续的内存空间存储数据，每个元素包含一个数据域和一个指向下一个元素的指针（或者同时包含指向前后节点的指针），因此数据元素的地址不一定是连续的。
- 优点：
- 插入和删除效率高：链表只需要调整指针即可完成插入和删除操作，时间复杂度为 O(1)（不需要移动元素）。
- 动态内存分配：链表不需要预先定义大小，内存空间可以根据实际需求动态分配，避免了空间浪费问题。
- 缺点：
- 随机访问效率低：访问链表中的元素需要从头节点开始依次遍历，时间复杂度为 O(N)。
- 指针开销：每个节点需要额外的指针空间存储前驱或后继元素。
顺序表详解
静态顺序表与动态顺序表
- 静态顺序表：使用固定大小的数组来存储数据元素。其大小在编译时就已经确定，运行时不能更改。适合数据量已知并且不会频繁变化的场景。
