线性表概述：从定义到存储，一次讲透
大家好，我是你们的嵌入式老司机。今天咱们来聊聊线性表——这个数据结构里的“入门第一课”。
说实话，我刚开始学C语言那会儿，觉得线性表不就是个数组嘛，有啥好讲的？直到后来做项目，踩了无数坑，才明白这东西远没那么简单。嗯，今天我就把这些年积累的经验，一次性倒给你们。
一、线性表的定义：说白了就是“排排坐”
线性表，英文叫 Linear List。你想象一下，一群小朋友排成一队，每个人都知道自己前面是谁、后面是谁——这就是线性表。
专业点说：线性表是n个数据元素的有限序列。这里有两个关键词：
- 有限：不能无限长，总有个头
- 序列：有顺序，谁在前谁在后是确定的
举个例子，我当年做的一个传感器数据采集系统，每隔10ms采一次温度值，存成一个数组：
// 温度数据线性表
float temp_data[100] = {25.3, 25.6, 25.8, 26.1, ...};这100个温度值，按时间顺序排列，就是一个典型的线性表。
核心要点：线性表里，除了第一个和最后一个元素，每个元素都有且只有一个前驱和一个后继。这就是“线性”二字的由来。
二、线性表的抽象数据类型：别被“抽象”吓到
很多同学一看到“抽象数据类型”就头大。其实说白了，就是定义一套“接口规范”——你线性表应该能干什么事。
我个人习惯这样理解：抽象数据类型就像餐厅的菜单，只告诉你有什么菜，不告诉你后厨怎么做。
线性表的基本操作，我归纳为以下几类：
| 操作类别 | 具体操作 | 说明 |
|---|---|---|
| 初始化 | InitList(&L) | 创建一个空表 |
| 销毁 | DestroyList(&L) | 释放内存资源 |
| 判空 | ListEmpty(L) | 表是否为空 |
| 求长度 | ListLength(L) | 返回元素个数 |
| 按位查找 | GetElem(L, i, &e) | 获取第i个元素 |
| 按值查找 | LocateElem(L, e) | 查找元素位置 |
| 插入 | ListInsert(&L, i, e) | 在第i位插入 |
| 删除 | ListDelete(&L, i, &e) | 删除第i个元素 |
你看，就这么8个操作，覆盖了线性表的所有使用场景。我在项目中写队列和栈的时候，底层就是基于这些操作封装的。
我的经验：写代码前先把这些接口定义好，后面实现起来思路特别清晰。这叫“先设计，后编码”。
三、顺序存储 vs 链式存储：两种思路，各有千秋
线性表怎么存到计算机里？主要有两种方式。我当年面试的时候，这个问题被问了不下10次。
3.1 顺序存储：数组的天下
说白了就是用数组存。每个元素挨着放，像火车车厢一样连在一起。
// 顺序存储结构
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE]; // 用数组存数据
int length; // 当前长度
} SeqList;优点很明显：
- 随机访问：想取第5个元素，直接 data[4] 就行，O(1)时间复杂度
- CPU缓存友好：数据连续存储，遍历时命中率高
缺点也致命：
- 插入删除要移动大量元素，最坏情况O(n)
- 长度固定，扩容麻烦
我曾经在一个数据采集项目里，用顺序表存采样数据。结果需求一变，采样率翻倍，数组不够用了……改代码改到凌晨三点。嗯，从那以后我对固定长度有了心理阴影。
3.2 链式存储：指针的艺术
每个元素不光存数据，还存一个指向下一个元素的指针。就像寻宝游戏，一个线索指向下一个线索。
// 链式存储结构
typedef struct Node {
int data; // 数据域
struct Node *next; // 指针域
} Node, *LinkList;优点：
- 插入删除只需改指针，O(1)时间复杂度
- 动态分配内存，想用多少用多少
缺点：
- 不能随机访问，找第5个元素得从头遍历
- 每个节点多存一个指针，内存开销大
- CPU缓存不友好，节点分散在内存各处
避坑指南：我曾经在嵌入式项目里用链表管理任务队列，结果频繁malloc/free导致内存碎片，系统跑了三天就挂了。后来改用静态内存池+数组模拟，稳如老狗。
3.3 对比总结：一张表说清楚
| 对比维度 | 顺序存储 | 链式存储 |
|---|---|---|
| 存储方式 | 连续内存 | 离散内存 |
| 随机访问 | O(1) ✅ | O(n) ❌ |
| 插入删除 | O(n) ❌ | O(1) ✅ |
| 空间利用率 | 高（无额外指针） | 低（有指针开销） |
| 扩容 | 困难 | 容易 |
| 适用场景 | 频繁查找、长度固定 | 频繁插入删除、长度不定 |
四、知识体系总览：一张SVG图看懂
下面这张图，是我自己总结的线性表知识体系。你看一遍，心里就有谱了。
五、怎么选？我的实战建议
你可能会问：那我到底用哪种？
我的经验是：
- 嵌入式裸机开发：优先用顺序存储。内存有限，malloc容易出问题。我一般用静态数组+游标管理。
- 频繁插入删除：比如任务调度队列，用链表。但记得用内存池，别裸用malloc。
- 数据量固定：比如传感器采样点，用数组。简单、高效、可靠。
- 数据量不确定：比如日志记录，用链表。动态扩展，不浪费内存。
一句话总结：顺序存储适合“读多写少”，链式存储适合“写多读少”。没有绝对的好坏，只有合不合适的场景。
好了，线性表的基础就讲到这里。下一节咱们会深入队列和栈的具体实现，到时候我会带着大家手写代码。记住我今天说的这些，后面你会感谢我的。