浅谈单链表与双链表的区别

2024-09-05 22:58

本文主要是介绍浅谈单链表与双链表的区别,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数组的优点
随机访问性强(通过下标进行快速定位)
查找速度快
数组的缺点
插入和删除效率低(插入和删除需要移动数据)
可能浪费内存(因为是连续的,所以每次申请数组之前必须规定数组的大小,如果大小不合理,则可能会浪费内存)
内存空间要求高,必须有足够的连续内存空间。
数组大小固定,不能动态拓展
链表的优点
插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)
内存利用率高,不会浪费内存(可以使用内存中细小的不连续空间(大于node节点的大小),并且在需要空间的时候才创建空间)
大小没有固定,拓展很灵活。
链表的缺点
不能随机查找,必须从第一个开始遍历,查找效率低
 

面试官:那请说一下单链表和双链表的区别?

 

我:

单链表只有一个指向下一结点的指针,也就是只能next
双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点,顾名思义,单链表只能单向读取
面试官:从你的描述来看,双链表的在查找、删除的时候可以利用二分法的思想去实现,那么这样效率就会大大提高,但是为什么目前市场应用上单链表的应用要比双链表的应用要广泛的多呢?

我:……这个我真的不知道,然后面试官就提醒我从存储效率上来考虑问题……

我回来后百度了下,发现网上的回答大都是关于链表的代码实现的,并没有关于链表本质深层次的分析,于是我便做以下分析:

单链表与双链表的结构图如下:

从以上结构可以得出双链表具有以下优点:

1、删除单链表中的某个结点时,一定要得到待删除结点的前驱,得到该前驱有两种方法,第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后,重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的,指针的总的移动操作都会有2*i次。而如果用双向链表,则不需要定位前驱结点。因此指针总的移动操作为i次。

2、查找时也一样,我们可以借用二分法的思路,从head(首节点)向后查找操作和last(尾节点)向前查找操作同步进行,这样双链表的效率可以提高一倍。

可是为什么市场上单链表的使用多余双链表呢?

从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这时一种工程总体上的衡量。

 
--------------------- 
作者:kangxidagege 
来源:CSDN 
原文:https://blog.csdn.net/kangxidagege/article/details/80211225 
版权声明:本文为博主原创文章,转载请附上博文链接!

这篇关于浅谈单链表与双链表的区别的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140297

相关文章

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

分辨率三兄弟LPI、DPI 和 PPI有什么区别? 搞清分辨率的那些事儿

《分辨率三兄弟LPI、DPI和PPI有什么区别?搞清分辨率的那些事儿》分辨率这个东西,真的是让人又爱又恨,为了搞清楚它,我可是翻阅了不少资料,最后发现“小7的背包”的解释最让我茅塞顿开,于是,我... 在谈到分辨率时,我们经常会遇到三个相似的缩写:PPI、DPI 和 LPI。虽然它们看起来差不多,但实际应用

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

GORM中Model和Table的区别及使用

《GORM中Model和Table的区别及使用》Model和Table是两种与数据库表交互的核心方法,但它们的用途和行为存在著差异,本文主要介绍了GORM中Model和Table的区别及使用,具有一... 目录1. Model 的作用与特点1.1 核心用途1.2 行为特点1.3 示例China编程代码2. Tab

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Spring中@RestController和@Controller的使用及区别

《Spring中@RestController和@Controller的使用及区别》:本文主要介绍Spring中@RestController和@Controller的使用及区别,具有很好的参考价... 目录Spring中@RestController和@Controller使用及区别1. 基本定义2. 使

Qt 中 isHidden 和 isVisible 的区别与使用小结

《Qt中isHidden和isVisible的区别与使用小结》Qt中的isHidden()和isVisible()方法都用于查询组件显示或隐藏状态,然而,它们有很大的区别,了解它们对于正确操... 目录1. 基础概念2. 区别清见3. 实际案例4. 注意事项5. 总结1. 基础概念Qt 中的 isHidd