双向链表有哪些比较实用的应用场景？

[miniyao]

平时用到双向链表的机会少，有哪些场景下使用双向链表是比较好的选择？

[glasslion]

@hszzz 别听那个 @BlockBlockBlock 胡说，vector/deque 都不是用链表实现的

[KIDJourney]

@hitmanx 口胡，这样搞就不是用双向链表实现的了。

@BlockBlockBlock 你举个例子吧？我下午看了下 c++ vector 和 list 的实现，都没有用链表。

[hszzz]

@glasslion 哈哈，初学者不敢和前辈们争论啊。其实我也不信，毕竟 primer 不是那样说的。

[bumz]

@BlockBlockBlock

看了你的上一条回复，我还以为你说的链表其实是 malloc 内部实现隐含的链表（还取决于具体实现）

我原本以为你知道我们说的 O(1) 是 amortized O(1)

看到你提到操作系统课，我原以为你知道高级语言的层面和系统底层具体实现的层面不可混为一谈

现在我终于明白了你用户名的含义，谢谢你的最后一条回复。

[KIDJourney]

@BlockBlockBlock 举个例子呗？

[Caturra]

@BlockBlockBlock

如果可变长度数组是所谓的 list 分块实现,单个随机访问是 O(logn),所以 n 个遍历就最坏而言是 O(nlogn),为什么?你知道你的 list 长到哪了吗?

而所谓的复制规模是关于 2 的幂递增的,即使算上复制的时间复杂度也是 O(n),
给你一个粗糙的计算方法,随机访问常数级别,O(n),复制规模是 1+2+4+...+2^log2(n)的上取整,高中数学还记得的话可算出是 O(n),均摊 O(1)没毛病

哪怕你是搞了一套算法用非等长 list 实现 O(1)就可算出访问地址以达到 O(n)的遍历,你也忽略了非连续空间访问速度上的差异,感性上效率很糟糕,实际上确实也挺糟糕的(别问为什么,我试过)

[Caturra]

list 实现这玩意的复杂度和是否等长无关,缺乏睡眠有点语无伦次了