顺序表和链表的⽐较
通常从空间性能和时间性能两个⽅⾯⽐较分析：
1.空间性能的⽐较
线性表长度变化⼤，难以预估存储规模，⽤链表
线性表长度变化不⼤，能事先确定存储⼤⼩，⽤顺序表
a.存储空间的分配
顺序表的存储空间必须预先分配，元素个数扩充受限，易造成存储空间浪费或空间溢出现象；链表⽆需预先分配空间，内存空间允许时，元素个数⽆限制。
b.存储密度的⼤⼩
不考虑顺序表中的空闲区，顺序表存储空间利⽤率为100%，存储密度为1；
链表存储空间利⽤率⼩于100%，存储密度⼩于1，单链表存储密度为0.5。
长度变化不⼤，且事先确定存储⼤⼩，采⽤顺序表可节约存储空间。
2.时间性能的⽐较
很少查，频繁插⼊或删除，⽤链表
频繁查，很少插⼊或删除，⽤顺序表
a.存取元素的效率
顺序表是由数组实现的随机存取结构，根据位置序号实现取值操作，效率⾼时间复杂度O(1)；链表是顺序存取结构，从表头开始依次向后遍历链表，取值效率底时间复杂度O(n)。
b.插⼊和删除操作的效率
数组和链表链表插⼊或删除⽆需移动数据，只修改指针，时间复杂度为O(1);
顺序表插⼊或删除时，平均要移动表中近⼀半的结点，时间复杂度为O(n)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。