对于单链表与双链表的区别

面试官昨天在面试中问了我关于链表的问题: 情况如下

访者: 请告诉我链接列表和数组之间的区别？

我: 数组静态分配内存，链表动态分配内存；数组在内存中是连续的链表的链表，并且链表不是连续的；数组使用下标定位，时间复杂度为O（1），链表定位元素的时间复杂度为O（n）；在数组中插入或删除元素的时间复杂度为O（n），而链表的时间复杂度为O（1）.

基于以上分析，数组和链表的优缺点如下:

访者: 那么请告诉我单链和双链手表之间的区别？

我:

单链表只有一个指向下一结点的指针，也就是只能next
双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以通过prev()快速找到前一结点，顾名思义，单链表只能单向读取

访者: 根据您的描述，您可以使用二分法的想法来查找和删除双链表链表的链表，这样效率会大大提高，但是为什么目前市场上需要单链表的应用比双链表使用更广泛？

我: ...我真的不知道，然后面试官提醒我从存储效率的角度考虑这个问题...

回到百度后，我发现互联网上的答案主要是关于链表代码的实现，并且对链表的本质没有深入的分析，因此我做了以下工作分析:

单链表和双链表的如下:

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

1. 删除单链列表中的节点时，必须获取要删除的节点的先驱. 有两种获取前体的方法. 第一种方法是找到要删除的节点，同时始终保存当前节点. 节点的前体. 第二种方法是在定位要删除的节点之后，从单链接列表的开头定位前驱. 尽管通常使用方法一. 但是实际上，这两种方法的效率是相同的，指针的总移动操作将有2 * i次. 如果使用双向链表，则无需定位前驱节点. 因此，指针的总移动操作为i倍.

2. 搜索是相同的，我们可以从头（第一个节点）后向搜索操作和最后一个（尾节点）前向搜索操作中借用二分法的思想，从而使双链表的效率可以加倍.

但是为什么市场上的单链表使用冗余的双链表？

从存储结构的角度来看，每个双链表节点比单链表节点多一个指针，并且n的长度需要n * length（32个指针的长度为4个字节）. 位系统（64位系统为8字节），不适用于某些时间效率不高的应用程序，因为它比单链表占用更多空间；那么设计人员将在空间上使用时间. 这是一种总体项目测量.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-252611-1.html

……