顺序表和链表不同环境下优缺点比较

简介: 顺序表和链表不同环境下优缺点比较

1.存取(读写)方式


顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取。一个是数组的存储方式另一个是头指针的存储形式。


2.逻辑结构和物理结构


顺序表存储时逻辑上是相邻的元素,对应的物理位置也是相邻的。采用链式存储时,逻辑上相邻的元素,物理存储位置不一定相邻,对应的逻辑关系是通过指针链接来表示的。


3.查找、插入和删除


对于按值查找,顺序表无序时,两者的时间复杂度均为O(n);存储的队列有序时,顺序表可用折半查找,此时的时间复杂度为O()。


对于按序号查找,顺序表时间复杂度为O(1),而链表的平均时间复杂度为O(n)。


插入和删除操作顺序表平均需要移动半个表长,而链表只需要修改相关节点的指针域即可。


4.空间分配


顺序表存储就是数组存储,数组确定了存储空间不能扩充,若加入新元素则会出现内存溢出。动态存储虽然可以扩充但是需要移动大量元素,操作效率低。链式存储的节点空间只在需要时申请分配,操作灵活高效。


选取策略


1.基于存储的考虑


难以估计线性表的长度或存储规模时用链表存储,有固定长度的用顺序表存储方便。


2.基于运算的考虑


常做按序号访问元素时,顺序表时间复杂度为O(1),链表为O(n),显然用顺序表。

按值访问元素时二者一样。

常进行插入、删除操作时,最优使用链表存储。


3.基于使用环境的考虑


顺序表存储较为容易实现,任何语言中都有数组类型;而链表操作是基于指针的较为复杂,指针也不稳定,出错问题就复杂。

目录
相关文章
|
21天前
|
存储
数据结构链表详解(不仅顺序表可以,我链表也可以)
数据结构链表详解(不仅顺序表可以,我链表也可以)
20 0
|
15天前
|
存储 缓存
[数据结构]——顺序表和链表
[数据结构]——顺序表和链表(下):https://developer.aliyun.com/article/1515507
|
22天前
|
存储 Java
数据结构奇妙旅程之顺序表和链表
数据结构奇妙旅程之顺序表和链表
|
22天前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表(C语言)
初阶数据结构之---顺序表和链表(C语言)
|
22天前
|
存储 缓存
【顺序表和链表的对比】
【顺序表和链表的对比】
|
22天前
|
存储 人工智能 缓存
数据结构顺序表和链表(超详细)
数据结构顺序表和链表(超详细)
51 1
|
22天前
|
算法
顺序表、链表相关OJ题(2)
顺序表、链表相关OJ题(2)
|
22天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
22天前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
10天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
20 1