程序员的进阶课-架构师之路 - 线性表

一、线性表的定义
【百度百科】线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

1、线性表(List)是零个或多个数据元素的集合
2、线性表中的数据元素之间是有顺序的
3、线性表中的数据元素个数是有限的
4、线性表中的数据元素的类型必须相同

生活中的线性表：

数组也是一种线性表。

二、线性表的分类

1.顺序表
基本思想：元素的存储空间是连续的。在内存中是以顺序存储，内存划分的区域是连续的。存储结构如下：

2.链表
基本思想：元素的存储空间是离散的，单独的（物理），它们可以通过在逻辑上指针的联系使得它成为了整体的链表。存储上分为数据和指针两部分。存储结构如下图：

单链表和循环链表只可向一个方向遍历；双链表和循环链表，首节点和尾节点被连接在一起，可视为“无头无尾”；双链表可以向两个方向移动，灵活度更大。

三、线性表的一些常用操作
1、创建线性表
2、销毁线性表
3、清空线性表
4、将元素插入线性表
5、将元素从线性表中删除
6、获取线性表中某个位置的元素
7、获取线性表的长度

四、选择合适的数据结构

１．基于存储的考虑
顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对＂MAXSIZE＂要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比，显然链式存储结构的存储密度是小于１的）。

２．基于运算的考虑
在顺序表中按序号访问的时间性能为O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

３．基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

扩展阅读：https://www.roncoo.com/view/1160515822987776001