顺序表和链表的结构特点(顺序表和链表的适用范围)

导语：数据结构——顺序表和链表的优缺点

数据存储结构的差异

通过对顺序表和链表的学习，可以得知它们都属于线性表，但数据存储结构有本质的不同：

顺序表需要在存储数据前申请一块足够大的存储空间，然后将数据按照次序逐一存储，数据之间紧密地贴合在一起。空间一旦开辟之后，则无法改变大小。链表和顺序表不同，在存储数据时才申请存储空间，数据之间的逻辑关系是根据指针域维持。当存储数据的个数无法提前确定，又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时，使用链表更有助于问题的解决。

两者的结构如图所示：

空间利用率

从空间利用率的角度上看，顺序表的空间利用率显然要比链表高。链表在申请结点内存空间时，内存地址是随机的。虽然这种方式有利于解决数据个数不确定的场景，但也会产生内存碎片，造成空间浪费。不仅如此，由于链表中每个数据元素都必须携带至少一个指针，因此，链表对所申请空间的利用率也没有顺序表高。

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

时间复杂度

顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度为 O(1)；顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n)。

链表中访问数据元素，需要从表头依次遍历，直到找到指定节点，花费的时间复杂度为 O(n)；链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)。

本文内容由小悦整理编辑！