数据结构之顺序表和链表的比较[2]

链表的优缺点基本上与顺序表是相反在实际应用中选取哪种存储结构应根据实际情况在存储和操作上进行权衡考虑

基于存储的考虑

顺序表的存储空间是静态分配的在程序执行之前必须明确规定它的存储规模也就是说事先对MAXSIZE要有合适的设定过大造成浪费过小造成溢出如果对线性表的长度或存储规模难以估计时不宜采用顺序表;链表不用事先估计存储规模但链表的存储密度较低(存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比)

基于操作的考虑

在顺序表中按序号访问元素的时间性能为O()而链表中按序号访问的时间性能是O(n)所以如果经常做的运算是按序号访问数据元素显然顺序表优于链表;而在顺序表中做插入删除时需移动元素当数据元素的信息量较多且表较长时这一点是不应忽视的;在链表中作插入删除虽然也要找插入位置但主要是比较操作从这个角度考虑显然链表较优

基于开发语言的考虑

顺序表容易实现任何高级语言中都有数组类型链表的操作是基于指针的有些语言不支持指针类型并且相对指针来讲顺序表较简单

总之两种存储结构各有长短选择那一种存储方式应由实际问题决定通常较稳定的线性表选择顺序存储而频繁做插入删除的即动态性较强的线性表宜选择链式存储

[] []