引入
我们基本学习了如何创建、删除、插入、修改一个单链表，那么单链表跟顺序表比真的高效嘛？单链表又适用于什么情况呢？单链表跟顺序表的优缺点呢？我们一起来看看！
效率观察
我们发现，无论是插入还是删除单链表中的元素，其实就分两步
- 遍历查找第 i 个元素
- 实现插入和删除
从算法的角度很容知道它们的时间复杂度都是 O(n);
那么单链表和顺序表岂不是都一样了？既然都是 O(n)，那链表的优势在哪呢？
对比
从第 i 个位置开始，连续插入10个元素
对于顺序存储结构
- 没插入一个都要移动 n-i 个位置
- 每次都是 O(n)
对于链表
- 找到第 i 个位置的指针，此时时间复杂度为 O(n)
- 接下来的赋值移动指针的时间复杂度为 O(1)
所以，对于删除和操作频繁的操作，单链表的效率就越高。
优缺点的对比
我们发现，对于不同的操作，可以使用顺序表或者单链表来完成最优的操作。我们从存储分配方式、时间性能和空间性能三方便来比较看看。
存储分配方式
- 顺序表存储结构：用一段连续的存储空间依次存储线性表的数据元素。
- 单链表：采用链式存储结构，用一组任意的存储单元存放线性表的元素。
时间性能
查找
- 顺序存储结构 ：O（1），有下标就能找到。
- 单链表：O（n），因为要一个接一个的找。
插入和删除
- 顺序存储结构：平均要移动表长一半的元素，时间位 O（n）
- 单链表：找到指针后，插入删除永远都是 O（1），只要赋值就行了。
空间性能
- 顺序存储结构：预分配存储空间，分大了浪费，分小了不够，就溢出了。
- 单链表：不需要预先分配存储空间，只要有就可以分配，元素个数也不受限制。
总结
线性表，查找频繁，少插入，那就用顺序存储结构。
线性表，插删频繁，查找少，那就用单链表。
例如
- 会员注册，一次注册是插入，剩下的都是查找并显示信息，顺序表就比较好。
- 物品交易，从一个用户交易到另一个用户，老用户删除、新用户增加，这种频繁插入删除的就适合单链表。
- 元素个数变化大，或者根本不知道会变成多大的时候，用线性表，因为不用预先分配存储空间，弹性好。
- 元素个数确定，不会改变，比如一周七天等等，确定元素的，不会插入删除、只是频繁的查找，这样的话效率会高很多。
总之
线性表的顺序存储结构和单链表都各有优点，不能简单的说谁好谁不好，要不然干嘛不淘汰了呢…所以我们要根据实际情况综合平衡，看看那种数据结构更能满足我们的需求。
尾巴
这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。
