顺序表和链表的优缺点及总结

目录

一、顺序表

顺序表的优点：

顺序表的缺点：

二、链表

无头单向非循环链表的优点：

无头单向非循环链表缺点：

带头双向循环链表的优点：

带头双向循环链表的缺点：

总结：

---

计算机中主要有两种基本的存储结构用于存放线性表：顺序存储结构和链式存储结构

一、顺序表

顺序表的优点：

1、顺序表的本质是数组，物理空间是连续的。

2、可以下标随机访问。

3、尾插尾删效率高，不需要挪动数据，时间复杂度是O(1)。

4、cpu高速缓存命中率高。

顺序表的缺点：

1、当空间不够时需要扩容，扩容有一定的性能消耗，一般是扩容2倍，但也存在一定的空间浪费

2、头部或中间位置插入删除效率低下，需要挪动数据，时间复杂度是0(n)。

二、链表

链表有多种结构，实际中最常用的是无头单向非循环链表和带头双向循环链表。

无头单向非循环链表的优点：

1、可以按需申请和释放空间，不用考虑空间不够问题。

2、头部和中间位置插入删除效率高，不需要挪动数据。

无头单向非循环链表缺点：

1、不支持随机访问，查找元素效率低下。

2、对链表中间或者尾部位置插入删除，需要遍历结点，时间复杂度是0(n)。

带头双向循环链表的优点：

1、可以按需申请和释放空间，不用考虑空间不够问题。

2、任意位置插入删除的时间复杂度是0(1)。

带头双向循环链表的缺点：

1、不支持下标随机访问。

总结：

1、链表的本质是针对顺序表的缺点设计的，因此在不同情况下可以选择不同的存储结构

2、如果线性表的主要操作是查找，很少做插入或删除操作，可以选择顺序表作为存储结构。

3、如果线性表要频繁进行插入或删除操作，可以选择链表作为存储结构。

4、无头单向非循环链表一般不会单独用来存放数据，实际中更多是作为其他数据结构的子结构，例如哈希桶、图的邻接矩阵。

5、带头双向循环链表一般用在单独存放数据，也是实际中常用的链表数据结构。