数据结构与算法——第2章-顺序表、链表的优缺点(2.4)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
1.开辟空间的方式
2.空间利用率
3.时间复杂度

二 顺序表和链表结构不同

1
2
3
顺序表和链表虽然同属于线性表，但数据的存储结构有本质的不同：
-顺序表存储数据时需预先申请一整块足够大的存储空间，然后将数据按次序逐一存储，数据之间紧密贴合，不留一丝空隙。
-链表的存储数据时，什么时候存储，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持

图示

三 不同之处

基于不同的存储结构，顺序表和链表有以下几点不同

3.1 开辟空间的方式

1
2
3
4
5
顺序表存储数据之前先开辟好足够的存储空间，空间一旦开辟后期无法改变大小（使用动态数组的情况除外）。

链表存储数据时一次只开辟存储一个节点的物理空间，如果后期需要还可以再申请。

因此，当存储数据的个数无法提前确定，或物理空间使用紧张以致无法一次性申请到足够大小的空间时，使用链表

3.2 空间利用率

1
2
3
4
5
6
顺序表的空间利用率显然要比链表高，因为链表在存储数据时，每次只申请一个节点的空间，且空间的位置是随机的

这种申请存储空间的方式会产生很多空间碎片，一定程序上造成了空间浪费。
不仅如此，由于链表中每个数据元素都必须携带至少一个指针，因此，链表对所申请空间的利用率也没有顺序表高。

空间碎片：指某些容量很小（1KB 甚至更小）以致无法得到有效利用的物理空间

图示

3.3 时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
解决不同类型的问题，顺序表和链表对应的时间复杂度也不同。


主要涉及访问元素（插入、删除和移动操作极少）时，使用顺序表
 -顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度为O(1)
 -链表中访问数据元素需从表头依次遍历，直到找到指定节点，时间复杂度为O(n)

主要涉及元素的插入、删除和移动（访问元素的需求很少）时，使用链表
 -链表中数据元素之间的逻辑关系靠节点之间的指针，当需要在链表中某处插入或删除节点时，
 只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为O（1)

 -顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度为O(n)

四 如何选择

1
不同类型的场景，选择合适的存储结构会使解决问题效率成倍数地提高

五 参考

  • CSDN—顺序表、链表的优缺点