在今天的一次采访中,我被问到了这个问题。
除了回答倒序和前后遍历外,面试官还不断强调其中的一些“基本点”。我放弃了,当然在面试后做了一些调查。在双链表中插入和删除似乎比单链表更有效。我不太清楚如何才能更有效地使用双链接列表,因为显然需要更改更多的引用。有人能解释背后的秘密吗?老实说,我做了相当多的研究,但未能理解我的主要问题是,仍然需要对双链接列表进行O(n)搜索。
以下是我对双链接列表的看法:
>
您已准备好访问\insert的两端。
它可以同时作为队列和堆栈工作。
节点删除不需要额外的指针。
您可以应用爬山遍历,因为您已经可以访问两端。
如果您正在存储数值,并且列表已排序,则可以为中值保留一个指针/变量,然后使用统计方法可以实现高度优化的搜索操作。
这里有一些代码让我更清楚。。。有:
class Node{
Node next;
Node prev;
}
删除单个链接列表中的节点-O(n)-
您不知道哪个是前面的节点,所以您必须遍历列表,直到找到它:
deleteNode(Node node){
prevNode = tmpNode;
tmpNode = prevNode.next;
while (tmpNode != null) {
if (tmpNode == node) {
prevNode.next = tmpNode.next;
}
prevNode = tmpNode;
tmpNode = prevNode.next;
}
}
删除双链接列表中的节点-O(1)-
您只需更新如下链接:
deleteNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
在单链表中,插入显然是较少的工作,只要您满足于总是在头部或某些已知元素之后插入。也就是说,您不能在已知元素之前插入,但请参阅下文。)
另一方面,删除更为棘手,因为您需要在要删除的元素之前知道该元素。
实现这一点的一种方法是使deleteapi与要删除的元素的前一个一起工作。这反映了insertapi,它采用的元素将是新元素的前身,但它不是很方便,而且很难记录。不过,这通常是可能的。一般来说,您通过遍历列表来获得列表中的元素。
当然,您可以从头开始搜索列表,找到要删除的元素,这样您就知道它的前身是什么了。这假设删除API包括列表的头部,这也很不方便。此外,搜索速度慢得愚蠢。
几乎没有人使用,但实际上非常有效的方法是定义一个单链表迭代器,作为迭代器当前目标之前元素的指针。这很简单,只比直接使用指向元素的指针慢一个间接方向,并且使得插入和删除都很快。缺点是删除一个元素可能会使其他迭代器无效以列出元素,这很烦人。(它不会使被删除元素的迭代器无效,这对于删除某些元素的遍历来说很好,但这并没有太大的补偿。)
如果删除并不重要,可能是因为数据结构是不可变的,那么单链表提供了另一个真正有用的特性:它们允许结构共享。一个单链表很可能是多个头的尾巴,这对于一个双链表来说是不可能的。因此,单链表传统上是函数式语言选择的简单数据结构。
在今天的一次采访中,我被问到了这个问题。 除了回答倒序和前后遍历外,面试官还不断强调其中的一些“基本点”。我放弃了,当然在面试后做了一些调查。在双链表中插入和删除似乎比单链表更有效。我不太清楚如何才能更有效地使用双链接列表,因为显然需要更改更多的引用。有人能解释背后的秘密吗?老实说,我做了相当多的研究,但未能理解我的主要问题是,仍然需要对双链接列表进行O(n)搜索。
我创建了一个单链表函数,我的教授说,为了获得额外的学分,我们可以将其更改为双链表。我读了一些东西,比如添加一个prev_节点函数,比如这样。 然而,我不知道从那里去哪里。我知道我需要像这里一样加上一个尾巴和一个脑袋。 谁能告诉我,(不要为我做这件事),我必须做什么才能把我的链接列表变成一个双重链接列表?我知道我现在必须参考尾巴和头部,但我对如何做到这一点很困惑。
我目前正在上Java课,教授告诉我们,理解链接的一个好方法是制作双向链表。我做了一个单链表,但是我很难把它转换成双向链表。所以我想知道是否有人能给我任何建议,以确保我的最后一个号码与前一个号码相连?如果前面的数字和最后一个数字连接到null。这是代码的一部分,如果你想得到更多,只要问,我会发布。 用于添加元素等的代码。这是我试图让尾部连接到最后一个数字的尝试。 下面的代码是insert函数,我需要
我写了一个程序,通过双链表管理银行账户,但我发现取消程序有问题。 我仍然有同样的问题,即使我尝试了这个方法:-(pnt)-
本文向大家介绍双向链表和双向循环链表?相关面试题,主要包含被问及双向链表和双向循环链表?时的应答技巧和注意事项,需要的朋友参考一下 双向链表: 包含两个指针,一个prev指向前一个节点,一个next指向后一个节点。 双向循环链表: 最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。
主要内容:双向链表的创建目前我们所学到的 链表,无论是动态链表还是 静态链表,表中各节点中都只包含一个指针(游标),且都统一指向直接后继节点,通常称这类链表为 单向链表(或 单链表)。 虽然使用单链表能 100% 解决逻辑关系为 "一对一" 数据的存储问题,但在解决某些特殊问题时,单链表并不是效率最优的存储结构。比如说,如果算法中需要大量地找某指定结点的前趋结点,使用单链表无疑是灾难性的,因为单链表更适合 "从前往后"
链表作为数组之外的一种常用序列抽象, 是大多数高级语言的基本数据类型, 因为 C 语言本身不支持链表类型, 大部分 C 程序都会自己实现一种链表类型, Redis 也不例外 —— 实现了一个双端链表结构。 双端链表作为一种常见的数据结构, 在大部分的数据结构或者算法书里都有讲解, 因此, 这一章关注的是 Redis 双端链表的具体实现, 以及该实现的 API , 而对于双端链表本身, 以及双端链表
双向链表 结构体 struct rt_list_node 双向链表节点 更多... 宏定义 #define rt_container_of(ptr, type, member) ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) 获取type结构体中member成员在这个结构体中的偏移 #de