与顺序表相比，在链表上实现顺序访问，其算法的效率比较低对吗

Question

如题所述

Answer 1

作为线性表的两种基本的存储结构：顺序表和链表。它们在存储和操作上各有优缺点，列表比较如下：
　　顺序表链表
　　优点1、方法简单，各种高级语言中都有数组，容易实现；
　　2、不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度大；
　　3、具有按元素序号随机访问的特点，查找速度快。
　　1、插入、删除时，只要找到对应前驱结点，修改指针即可，无需移动元素；
　　2、采用动态存储分配，不会造成内存浪费和溢出。
　　缺点1、插入删除操作时，需要移动元素，平均移动大约表中一半的元素，对元素较多的顺序表效率低。
　　2、采用静态空间分配，需要预先分配足够大的存储空间，会造成内存的浪费和溢出。
　　1、在有些语言中，不支持指针，不容易实现；
　　2、需要用额外空间存储线性表的关系，存储密度小
　　3、不能随机访问，查找时要从头指针开始遍历。
　　数据结构之顺序表和链表的比较[2]
　　链表， 顺序， 结构， 链表， 顺序， 结构
　　链表的优缺点基本上与顺序表是相反。在实际应用中选取哪种存储结构应根据实际情况在存储和操作上进行权衡考虑：
　　1．基于存储的考虑
　　顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。如果对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比）。
　　2．基于操作的考虑
　　在顺序表中按序号访问元素的时间性能为O（1），而链表中按序号访问的时间性能是O（n），所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时需移动元素，当数据元素的信息量较多且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但主要是比较操作，从这个角度考虑显然链表较优。
　　3．基于开发语言的考虑
　　顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，有些语言不支持指针类型，并且相对指针来讲顺序表较简单。
　　总之，两种存储结构各有长短，选择那一种存储方式应由实际问题决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。