线性表_顺序存储结构和链式存储结构的优缺点比较(区别)
线性表的定义:
线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列。
其中:
数据元素的个数n定义为表的长度 = “list”.length() (”list”.length() = 0(表里没有一个元素)时称为空表)
将非空的线性表(n>=0)记作:(a[0],a[1],a[2],…,a[n-1])
数据元素a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以不同
一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的线性表又称为文件。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。
——引自WiKi
----------------------------------------------------------------------------分割线---------------------------------------------------------------------------------
(一)顺序存储结构和链式存储结构的优缺点比较,以及使用情况。
1 优缺点
① 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。
优点:存储密度大(=1),易于查找和修改。
缺点:插入或删除元素时不方便;存储空间利用率低,预先分配内存可能造成存储空间浪费。
②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
优点:插入或删除元素时很方便,使用灵活,存储空间利用率高。
缺点:存储密度小(<1),查找和修改需要遍历整个链表。
2 使用情况
顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;
若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。
3 比较
顺序表与链表的比较
基于空间的比较
顺序表和链表的存储空间均为O(n)
存储分配的方式
顺序表的存储空间是静态分配的
链表的存储空间是动态分配的
存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
基于时间的比较
i存取方式
顺序表可以随机存取,也可以顺序存取
链表是顺序存取的
ii插入/删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素,只需要修改指针