顺序表和链表的优缺点总结
- 引言
- 顺序表
- 链表
- 一、两者的优缺点
- 1. 顺序表的优点
- 2. 顺序表的缺点
- 3. 链表的优点
- 4. 链表的缺点
- 二、按照三个角度看待问题
引言
顺序表和链表都属于线性表，它们都是用来存储数据的结构。
线性表：零个或多个数据元素的有限序列。
顺序表即表示线性表的顺序存储，链表即表示线性表的链式存储。
顺序表
顺序表：顺序表底层是一个数组，它在逻辑上和物理结构上都是连续的。因为我们可以按照下标进行各种操作，每个元素都是连续存放的。
顺序表按位查找的时间复杂度为：O(1)
顺序表按值查找的时间复杂度为：O(n)
中间插入、中间删除的时间复杂度为：O(n)
头插、头删的时间复杂度为：O(n)
尾插、尾删的时间复杂度为：O(1)
链表
链表：链表是一个由若干节点组成的结构，它在逻辑上是连续的，但在物理结构上是非连续的，或者说，内存上不是紧挨着的。
链表按位查找的时间复杂度为：O(n)
链表按值查找的时间复杂度为：O(n)
链表在找到指定元素的位置后，插入和删除操作的时间复杂度为：O(1)
单链表在插入和删除操作时，需要找到前驱域，这也是较为麻烦的。
而双向链表的插入和删除操作效率就较为高效，因为双向链表中的每个节点不仅存储了后继域，也存储了前驱域。但显然，双向链表是利用了更多的空间换取了时间。
一、两者的优缺点
1. 顺序表的优点
顺序表可以通过索引（下标）快速地存、取表中元素。
2. 顺序表的缺点
① 顺序表的插入和删除操作，会使得表中的大量元素进行移动，效率较低。
② 顺序表在面对扩容问题的时候，比较繁琐。当顺序表放满的时候，我们需要进行扩容。而扩容的大小需要面对不同的情况，若扩容的容量较大，那么会使得空间利用率较低；若扩容的容量较小，在后续的代码执行过程中，又需要不断地扩容操作，这使得代码变得更加繁琐。
3. 链表的优点
① 链表的插入和删除操作的效率较高，可以把通过指针 (地址) 直接改变节点的指向。
② 链表不需要考虑扩容问题。
4. 链表的缺点
链表在查找元素的时候，执行效率较低，需要从头开始，依次往后找。
二、按照三个角度看待问题
1. 基于存取方式
顺序表可以顺序存取，也可以随机存取；链表只能从表头开始往后顺序存取元素。
2. 基于查找方式
顺序表按照位序查找的时间复杂度为 O(1)；链表按照位序查找的时间复杂度为 O(n).
3. 基于插入和删除的方式
一般来说，顺序表的插入和删除需要挪动大量元素，时间复杂度为 O(n)；链表需要从表头遍历找到待操作的元素位置的前驱，时间复杂度也为 O(n)，但是链表在找前驱的位置时，主要是遍历操作，此外，链表在找到元素前驱的位置之后，插入和删除操作的时间复杂度只为 O(1)，效率极高。所以这样比较来看，链表的插入和删除操作效率显然要比顺序表的插入和删除操作要高！
综上所述：
① 若我们存储数据的时候，在后续的操作中，需要对数据进行频繁查找，很少进行插入和删除操作时，宜采用顺序表。
② 若我们存储数据的时候，无法确定数据个数的变化，此外使用插入和删除的操作较频繁时，宜采用链表。