线性表的顺序存储结构和链式的对比

作者: fuxi | 来源:发表于2016-08-15 08:51 被阅读0次

数据结构之有序线性表的链式存储结构
数据结构之线性表
线性表的顺序存储与链式存储
线性链表
数据结构之线性表的链式存储结构
2019-07-14 线性表详解
线性表--顺序存储结构
线性表的链式存储--单链表
数据结构与算法（二）--- 单向循环链表
C++线性表的链式存储结构

顺序存储结构：
优点：
a.不用为表中元素的逻辑关系去增加多余的存储空间，
b.能够快速存取任意位置的元素
缺点：
a.插入和删除操作需要大量移动元素，效率不高
b.线性表长度有较大变化是时，它的存储空间容量会难以确定。
c.顺序存储结构在申请空间时会大块的申请，容易造成碎片，碎片空间会被浪费。

顺序存储结构与单链表结构的优缺点对比
1、时间性能上
1）查找
顺序存储结构O(1)
单链表O(n)
2）插入和删除
顺序存储结构需要平均移动表长的一半，时间为O（n）
单链表在计算出某个位置的指针以后，插入和删除的时间为O（1）。
2、空间性能
顺序存储结构要先分配存储空间，容易造成内存空间不足或者浪费
单链表存储结构不需要分配存储空间。

简单总结，但是还是需要实际情况实际分析。
若线性表需要频繁进行查找，很少进行插入和删除，就适合顺序存储结构
如果情况相反，就比较适合单链表存储结构。
如果线性表中元素个数变化较大或者和根本不知道大小的话，就可以用单链表结构，
如果实现就知道线性表的大致长度，可以选择顺序存储结构。