线性表总结 顺序表、链表对比
前几篇我们已经学习了顺序表、单链表、双链表等，再次回顾一下。
1. 线性表
概念：线性表是具有相同数据类型的 n (n>=0) 个数据元素的有限序列。
特点：
- 表中元素个数有限；
- 表中元素具有逻辑上的顺序性，表中元素有其先后顺序；
- 表中元素都是数据元素，每个元素都是单个元素；
- 表中元素的数据类型相同，这意味着每个元素占有相同大小的存储空间；
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
基本操作包括初始化、求表长、插入、删除等等。
2. 线性表分类
注意线性表是从逻辑结构上考虑的，侧重的是元素之间的逻辑关系，它有两种存储方式，顺序存储的叫顺序表，链式存储的有单链表、双链表、循环链表等，顺序表和链表都是线性表。像树、图这种不是线性表。
3. 顺序表、链表比较
3.1. 读写方式
顺序表可以顺序存取，也可以随机存取；
链表只能从表头顺序存取元素。
补充：双链表里提到过可以维护一个尾指针，实际上也可以从表尾开始找，如果有指向前驱结点的指针的话可以倒着找前面的，但无论从哪里开始，无论是从前往后还是从后往前，这里的“只能顺序存取”强调的是必须一个一个地找，不能一下子就找到指定的地方。（希望读到这里的初学者能真正理解，所以有点啰嗦。）
3.2. 逻辑结构和物理结构的关系
顺序表中逻辑上相邻的元素物理存储位置也相邻；
链表中逻辑上相邻的元素物理存储位置不一定相邻。
3.3. 查找操作时间复杂度
按值查找：顺序表无序时时间复杂度为，有序时可以用折半查找，时间复杂度是
，到后面查找算法的地方会再详细学到，可以先不用深究；链表的时间复杂度为
。
按位查找：顺序表可以随机访问，因此时间复杂度是；链表的平均时间复杂度是
。
3.4. 空间分配
顺序表在静态存储分配的情况下，一旦存储空间装满就不能扩充，再加入新元素会出现内存溢出，因此需要预先分配足够大的空间，但过大可能会导致顺序表后部大量闲置。
链表的结点空间只在需要时申请分配且不需要连续，操作灵活高效。
4. 如何选取存储结构（顺序表和链表怎么选择）
4.1. 从存储方面考虑
顺序表存储密度大，但需要预先估计存储规模；
链表不需要预先考虑存储规模，但因为要存储指针所以存储密度低。
4.2. 从时间复杂度考虑
顺序表按位查找时时间复杂度仅为，链表是
，若常用操作是按位查找则应该选择顺序表。
顺序表在进行插入、删除操作时平均需要挪动一半的元素，而链表只需要修改指针（链表进行插入、删除操作也需要先找到插入位置，但只看插入、删除这个操作的话链表更方便。）
总之，比较稳定的线性表可以顺序存储，但如果频繁插入、删除的可以选择链表。