链表与顺序表的区别

xiaoxiao2021-02-27  278



       顺序表存储位置是相邻连续的,可以随即访问的一种数据结构,一个顺序表在使用前必须指定起长度,一旦分配内存,则在使用中不可以动态的更改。他的优点是访问数据是比较方便,可以随即的访问表中的任何一个数据。       链表是通过指针来描述元素关系的一种数据结构,他可以是物理地址不连续的物理空间。不能随即访问链表元素,必须从表头开始,一步一步搜索元素。它的优点是:对于数组,可以动态的改变数据的长度,分配物理空间。        在使用中:如果一个数组在使用中,查询比较多,而插入,删除数据比较少,数组的长度不变时,选顺序表比较合理。如果插入,删除,长度不定的数组,可以选链表。

基于空间的比较

n存储分配的方式

u顺序表的存储空间是静态分配的

u链表的存储空间是动态分配的

n存储密度= 结点数据本身所占的存储量/结点结构所占的存储总量

u顺序表的存储密度= 1

u链表的存储密度<1 基于时间的比较 n存取方式 u顺序表可以随机存取也可以顺序存取 u链表是顺序存取的 n插入/删除时移动元素个数 u顺序表平均需要移动近一半元素 u链表不需要移动元素,只需要修改指针 u若插入/删除仅发生在表的两端,宜采用带尾指针的循环链表

转载请注明原文地址: https://www.6miu.com/read-12270.html

最新回复(0)