线性表(linear list)
线性表结构基础
线性表是一种最常见、最基础的数据结构。它强调元素之间的前后次序， 也就是除了头和尾之外，每个元素都处在一条“前驱—自己—后继”的链条中。
线性表长什么样
在线性表这个非空有限集合中，所有数据元素排成一条线。 它不是随意堆在一起，而是有明确先后关系的顺序结构。
第一个a1
→
a2
→
a3
→
a4
→
最后一个an
从图上可以看出：线性表中的元素不是并列散放的，
而是一个挨着一个顺次排列，因此它最适合表达“有顺序”的数据。
线性表的四个特点
判断一个结构是不是线性表，关键看它是否满足下面四条性质。
1
唯一的第一个元素
在线性表中，表头只能有一个，不可能同时出现两个“第一个”。
2
唯一的最后一个元素
在线性表中，表尾也只能有一个，不可能同时出现两个“最后一个”。
3
除第一个外都有唯一前驱
除了第一个元素之外，其余每个元素前面都恰好接着一个元素。
4
除最后一个外都有唯一后继
除了最后一个元素之外，其余每个元素后面都恰好接着一个元素。
按存储结构分成两类
在线性表的程序实现中，最常见的两种存储方式是：顺序表和链表。 它们逻辑上都是线性表，但在计算机中的存放方式不同。
顺序表
a1
a2
a3
a4
顺序表通常把元素连续存放在一段内存空间里。 优点是按位置访问很快，缺点是在中间插入或删除时可能需要移动很多元素。
链表
a1
→
a2
→
a3
→
a4
链表中的元素可以分散存放，再靠指针把前后关系连起来。 优点是插入删除更灵活，缺点是按位置访问通常不如顺序表直接。
顺序表和链表怎么理解
顺序表更像什么
- 像一排连续编号的座位
- 想找第 3 个位置，直接按编号去就行
- 但中间插一个新同学，后面的座位可能都要调整
链表更像什么
- 像一串用绳子串起来的牌子
- 想插进一个新牌子，只要改连接关系
- 但想找第 3 个牌子，通常要顺着一个一个往后找
一句话记住线性表
本质
线性表是有先后顺序的一组数据元素。
结构特征
头尾唯一，中间元素前后关系唯一。
顺序表
连续存放，访问快，但插删可能要移动元素。
链表
分散存放，连接灵活，但按位置访问较慢。