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

[miniyao]

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

[KIDJourney]

@BlockBlockBlock
不是很懂，不管你链表装什么，随机读取都不是 O(1)的。

[Wicked]

常数时间删除元素，保序遍历，需要这些特性的场合都可以用

[bobuick]

一大堆用处。
如果只写 web， 只写 CRUD 基本用不到

[akira]

链表的最大作用。。
是为了让人可以继续学习后续的树形结构。。

[hszzz]

@BlockBlockBlock STL 里的 vector，有一个 capacity 和 size 的。capacity 总是大于等于 size 的，用完了就会自动重新申请，一般是 size 的两倍。

[hszzz]

@BlockBlockBlock 防止频繁地申请和释放内存。

[lzjamao]

换个思维。
双向链表有什么优势和劣势。
技术符合需求，不是需求符合技术

[bravecarrot]

@BlockBlockBlock 随机存取的时候 岂不是太慢了..

[BlockBlockBlock]

@bravecarrot
@hszzz
@KIDJourney
@bumz
@snail1988
@jmc891205
@glasslion
@jmc891205

翻倍翻倍翻倍……你们既然都知道翻倍了，两个问题先自己去想清楚了再过了。我发现我们很难交流……

1. 既然空间翻倍了，那翻倍的空间从哪里来？ a) 把内存条从数组的尾端掰断然后再加一段吗？这怕不是要实现边长数组，这是要实现变长内存条，还是能从中间拉长的那种。b) 开一片新内存然后把旧的全部复制过去？嗯，小数组还好，大数组真是酸爽……

2.既然你们都知道翻倍了，那翻倍隐含的 log2(N) 被怪物吃了吗？想想这个 log2(N) 去哪里了……

只会喊些什么，翻倍，O(1)。翻倍怎么翻？ O(1) 怎么来的？想过吗？

[NUT]

JAVA 相关的
Queue
Stack
LinkedList
LinkedHashMap
HashMap
Guava 的 FutureTask （单向列表）
RocketMQ 的 index （单向列表）

[neoblackcap]

@BlockBlockBlock 复制就是这样，当然可以使用 move，而且你的翻倍隐含的 O(logN)时间复杂度跟随机读取的 O(1)根本不冲突

[BlockBlockBlock]

@neoblackcap

看不懂就算了……不多做解释了

[neoblackcap]

@BlockBlockBlock allocator 对于可变长数组不是必要，内存分配是 allocator 的事情。我是没看到 CPython 里面的 List 是有 LinkedList 的实现，C++的 vector 也不是。你说有请拿事实说话。

[KIDJourney]

@hitmanx 我看了下实现，这样搞就不是双向队列了啊。

[jmc891205]

@BlockBlockBlock
翻倍的复制操作不影响变长数组插入操作的平均时间复杂度是 O(1)。这叫 amortized analysis。大多数教科书对此问题都有讨论。你可以自行查找。

[jmc891205]

@BlockBlockBlock 如果你手边没有任何算法与数据结构的教科书 你可以参考 Wikipedia 上的 Dynamic array 词条： https://en.wikipedia.org/wiki/Dynamic_array

[lauix]

java 里的 list map 有个神马对象 就是

[jmc891205]

我在#55 楼里说的“插入操作”不严谨 我指的是 push_back 操作 即在数组末尾插入元素

[hitmanx]

@jmc891205 对的,是 amortized O(1)

[hszzz]

@BlockBlockBlock 好的，谢谢你，有时间我去了解一下。