序表和链表的区别(通俗易懂)

简介: 序表和链表的区别(通俗易懂)

1.存储密度

顺序表的存储密度高


链表中的结点除了存储数据,还要存储指向下一结点的指针


2.存取方式

顺序表可以随机存取,因为顺序表是连续存储的,并且每个元素的大小相同,只要知道第一个元素的地址,就能知道第i个元素的地址


链表要寻找第i个结点时,必须从头结点开始依次往后寻找,不可以随机存取。


3.分配空间

顺序表中的元素是在一片连续的空间存储的,所以给顺序表分配空间与改变顺序表容量大小较麻烦


链表各个结点是离散存放在不同的空间中,所以每次添加结点只需要用malloc申请空间即可


4.初始化表

顺序表在初始化时需要预分配大片连续空间,若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源。


链表只需要分配一个头结点(或者不分配头结点,只是声明头结点)


5.删除表

链表的删除可以通过循环将各个结点依次遍历删除(free(p))


顺序表占用空间的回收分两种情况


静态分配是声明一个静态数组,请求系统分配,删除表时系统会自动回收


动态分配是声明一个动态数组(malloc),malloc函数申请的空间是属于内存的堆区,堆区的内存空间不会由系统自动回收,删除表时,就需要用(free(p)),所以malloc和free是成对出现的


6.插入和删除表

顺序表插入和删除表都要对i后续的元素进行整体后移或前移


时间复杂度O(n)开销主要来自于移动元素


链表的插入和删除只需要修改指针的指向就可以了


时间复杂度O(n)开销主要来自于遍历查找目标元素


7.查找元素

顺序表


按位查找 O(1)


按值查找


若顺序表中的元素无序,就要从第一个元素开始查找,时间复杂度是O(n)


若是有序的,就可以利用折半查找等方法,将时间复杂度降为O()


链表:都是从头结点开始遍历查找


按位查找:O(n)


按值查找:O(n)


总结:


表长难以预估,经常要增加/删除元素        --链表


表长可预估,查询(搜索)操作较多         --顺序表


目录
相关文章
|
3月前
|
存储
数组与链表有什么区别
数组与链表有什么区别
|
5月前
|
存储 调度 C语言
链表,栈,队列的区别及其应用
链表,栈,队列的区别及其应用
|
5月前
|
存储 算法 C语言
链表带头和不带头的区别及其应用
链表带头和不带头的区别及其应用
|
5月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
数据结构 - 链表和数组的区别
数据结构 - 链表和数组的区别
79 0
|
5月前
|
存储 Java
【链表的说明、方法---顺序表与链表的区别】
【链表的说明、方法---顺序表与链表的区别】
55 0
|
5月前
|
算法 索引 Python
leetcode-138:复制带随机指针的链表 (python中copy与deepcopy区别)
leetcode-138:复制带随机指针的链表 (python中copy与deepcopy区别)
60 0
|
存储 缓存 内存技术
对于顺序表和链表的区别
对于顺序表和链表的区别
88 0
|
存储 JavaScript 前端开发
栈,队列和链表三者之间的关系与区别
栈,队列和链表三者之间的关系与区别
236 0
栈,队列和链表三者之间的关系与区别
|
存储 算法 前端开发
【前端算法】链表和数组实现队列的区别
比较链表和数组实现队列的性能
174 0