数据结构 ——— 顺序表和链表的区别以及各自的优缺点
目录
顺序表和链表的区别
一、存储空间上
二、下标的随机访问
三、任意位置插入或者删除元素
四、添加数据
五、应用场景
六、缓存利用率
顺序表和链表的优缺点
顺序表的缺点
链表的优点（和顺序表的缺点对应）
顺序表的优点
链表的缺点（和顺序表的优点对应）
小结
顺序表和链表的区别
一、存储空间上
- 顺序表的存储空间物理上一定连续
- 链表的存储空间逻辑上连续，但物理上不一定连续
二、下标的随机访问
- 顺序表支持下标的随机访问（有效空间内），且时间复杂度为：O(1)
- 链表不支持下标的随机访问，查询节点数据的时间复杂度为：O(N)
三、任意位置插入或者删除元素
- 顺序表在头插或者中间插入数据时，要挪动元素，效率低，最坏的情况下时间复杂度为：O(N)
- 链表在任意位置插入或删除数据时，只需要修改指针的指向即可，在查询到指定节点的情况下，插入删除的时间复杂度为O(1)
四、添加数据
- 动态顺序表添加数据时，当空间不够时需要扩容，扩容就会存在原地扩容、异地扩容和浪费空间的情况，降低了效率，也浪费存储空间，因为是连续的物理空间，不能部分释放
- 链表没有扩容的概念，是按需申请空间，按需释放空间，不会存在浪费的情况
五、应用场景
顺序表应用在元素高效存储和频繁访问，因为支持下标的随机访问
链表应用场景在任意位置的插入和删除频繁
六、缓存利用率
顺序表的缓存利用率高
链表的缓存利用率低
顺序表和链表的优缺点
顺序表的缺点
前面部分的插入删除数据的效率低，因为需要挪动数据，最坏的情况下是O(N)
当空间不够的时候就需要扩容，且只要存储的数据越来越多，基本都是异地扩容，那么效率就会底下，且还存在空间浪费的情况
链表的优点（和顺序表的缺点对应）
在缺点指定的节点情况下，任意位置的插入删除数据都是O(1)
且不存在扩容的情况，因为是按需申请释放空间
顺序表的优点
支持下标的随机访问，可不要小看下标的随机访问，只要支持，就能实现效率为 O(long N) 的二分查找法等其他操作
尾插尾删的效率不错，在有 size 有效数据长度的情况下，配合下标的随机访问，效率为O(1)
链表的缺点（和顺序表的优点对应）
不支持下标的随机访问，那么就实现不了二分才查找法和及其相关的操作
小结
顺序表和链表各有各的优缺点，在实际应用场景中，可以根据不同的需求，应用不同的结构
当需要支持下标的随机访问时，可以考虑使用顺序表
当要在任意位置频繁插入删除数据时，可以考虑使用链表