区别
顺序表和链表的比较
顺序表 | 单链表 | |
存取方式 | 可顺序存取,可随机存取 | 只能从表头顺序存取 |
逻辑结构和物理结构 | 顺序存储,逻辑上相邻物理上也相邻 | 链式存储,逻辑上相邻物理上不一定相邻,通过指针链接 |
按值查找 | 按值查找:O(n)(无序) 折半查找 O(log2n)(有序) | O(n) |
按序号查找 | O(1) | O(n) |
插入 | O(n),平均需要移动n/2个元素 | 只需修改相关结点 |
删除 | O(n),平均需要移动n/2个元素 | 只需修改相关结点 |
空间分配 | 可能会出现存储空间大量闲置或空间不足溢出 | 动态申请空间,操作灵活、高效 |
怎样选取存储结构
1、基于存储的考虑
难以估计线性表的长度或存储规模时,不易采用顺序表;但链表的存储密度较低,链式存储结构的存储密度是小于1的。
2、基于运算的考虑
若经常做的运算是按序访问数据元素,则显然顺序表更优。
若经常做插入删除操作,则链式存储结构则更优。
3、基于环境的考虑
顺序表容易实现,链表是基于指针的,相对来讲,前者实现更加简单,实现难易度也是需要考虑的一点。
Last updated