平时用到双向链表的机会少，有哪些场景下使用双向链表是比较好的选择？
推荐学习书目
› Learn Python the Hard Way
Python Sites
› PyPI - Python Package Index
› http://diveintopython.org/toc/index.html
› Pocoo
值得关注的项目
› PyPy
› Celery
› Jinja2
› Read the Docs
› gevent
› pyenv
› virtualenv
› Stackless Python
› Beautiful Soup
› 结巴中文分词
› Green Unicorn
› Sentry
› Shovel
› Pyflakes
› pytest
Python 编程
› pep8 Checker
Styles
› PEP 8
› Google Python Style Guide
› Code Style from The Hitchhiker's Guide
This topic created in 3150 days ago, the information mentioned may be changed or developed.
 |
1
lru
|
1 |
2
面试
|
 |
zpxshlMar 20, 2018 via Android
3
linkedlist 就是...
|
 |
lingerzMar 20, 2018 via Android
4
考级
|
 |
congeecMar 20, 2018
5
|
 |
vegito2002Mar 20, 2018
6
LRU
|
 |
yeeptMar 20, 2018
7
LRU
|
 |
nl101531Mar 20, 2018 via Android
8
fork join 的工作窃取，一个从头一个从尾，降低冲突概率。
|
 |
dobeleeMar 20, 2018 via Android
9
这个很少暴露在高级语言中，通常会有集合或替代方案。主要还是考试和面试吧。当然有助于新人理解数据结构模型。
|
 |
snailsirMar 20, 2018
10
区块链？
|
 |
11
hashtable + 双链表 LRU
|
 |
chu1337Mar 20, 2018
12
用单链多一点
|
 |
BlockBlockBlockMar 20, 2018
13
不然你觉得你用的那些可变长度的数组在底层都是怎么存的？
|
 |
TestSmirkMar 20, 2018
14
面试?
|
 |
hx1997Mar 20, 2018 via Android
15
底层开发很多吧… 像操作系统
|
 |
16
@BlockBlockBlock 真没拿双向链表去实现可变长度的数组的
|
 |
kljsandjbMar 20, 2018 via iPhone
17
LRU :)
|
 |
jmc891205Mar 20, 2018
18
@BlockBlockBlock 用双向链表实现数组的话 访问元素的时间复杂度太高了
|
|
jmc891205Mar 20, 2018
19
不是很懂这个问题为啥发在 Python 节点
以我粗浅的知识 在写 Python 的时候 无论是后端开发、机器学习、运维脚本 都不会用到双向链表。 |
 |
weicsMar 20, 2018
20
LinkedList 就是双向链表，获取元素的时候，如果元素在后面，直接用双向链表反向获取
|
 |
linhanqiuMar 20, 2018
21
面试必考？平常的时候写小东西时提高效率？
|
 |
swullingMar 20, 2018 via iPhone
22
双向链表是很常用的数据结构啊，因为单向链表没啥实用价值，基本用的链表都是双向的
比如 Redis 的双向链表，http://redisbook.com/preview/adlist/implementation.html，具体的用处有发布订阅机制，客户端维护，列表键底层实现之一，等等 |
 |
vjnjcMar 20, 2018
23
以前都喜欢自己写结构，tree，node，链表，后来发现都有现成实现。。。
|
 |
RubyJackMar 20, 2018
24
和 hashmap 一起搞 lru
|
|
BlockBlockBlockMar 20, 2018
25
哦，原来在 python 节点下……那就怪不得有人不懂了……
|
 |
sohoerMar 20, 2018
26
Queue
|
 |
aheadleadMar 20, 2018
27
STL 的 deque 了解一下
|
 |
bumzMar 20, 2018
31
|
|
BlockBlockBlockMar 20, 2018
32
|
|
BlockBlockBlockMar 20, 2018 via iPhone
33
@bumz
我不明白你是怎么脑补出来我说的链表每个节点是装着一个元素的？如果每个链表节点装的是一片内存空间呢？这是典型的内存片的管理方式你们大学时候上操作系统课不学的吗？ |
 |
vincenttoneMar 20, 2018
34
php 的 array，redis 的 list 等等等等
|
 |
safeoyMar 20, 2018
35
LRU
|
 |
wcsjtuMar 20, 2018 via Android
36
Django 的 lru cache 了解一下？
|
 |
snail1988Mar 20, 2018
37
@BlockBlockBlock 要求随机存取 O(1)的数据结构为什么用链表，上来就喷别人
|
|
BlockBlockBlockMar 20, 2018
38
|
 |
orangeadeMar 20, 2018 via Android
39
python 里多了去了，有空多看看 python 解释器，pypy 和官方库的源码
|
 |
40
@snail1988 我觉得他说的可能是类似 std::deque 的实现,实际上本质是 fixed-sized 的 vector 的 list,通过把每个 vector(chunk)的首地址 cache 起来,是可以做到 O(1)的 random access 的.但是实际上这个 cache 首地址的数据结构,就是一个 vector
https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl http://en.cppreference.com/w/cpp/container/deque |
 |
KIDJourneyMar 20, 2018
41
@BlockBlockBlock
不是很懂，不管你链表装什么，随机读取都不是 O(1)的。 |
 |
WickedMar 20, 2018 via iPhone
42
常数时间删除元素，保序遍历，需要这些特性的场合都可以用
|
 |
bobuickMar 20, 2018
43
一大堆用处。
如果只写 web， 只写 CRUD 基本用不到 |
 |
akiraMar 20, 2018
44
链表的最大作用。。
是为了让人可以继续学习后续的树形结构。。 |
 |
hszzzMar 20, 2018 via Android
45
@BlockBlockBlock STL 里的 vector，有一个 capacity 和 size 的。capacity 总是大于等于 size 的，用完了就会自动重新申请，一般是 size 的两倍。
|
|
hszzzMar 20, 2018 via Android
46
@BlockBlockBlock 防止频繁地申请和释放内存。
|
 |
lzjamaoMar 21, 2018 via Android
47
换个思维。
双向链表有什么优势和劣势。 技术符合需求，不是需求符合技术 |
 |
bravecarrotMar 21, 2018 via iPhone
48
@BlockBlockBlock 随机存取的时候 岂不是太慢了..
|
|
BlockBlockBlockMar 21, 2018
49
@bravecarrot
@hszzz @KIDJourney @bumz @snail1988 @jmc891205 @glasslion @jmc891205 翻倍翻倍翻倍……你们既然都知道翻倍了，两个问题先自己去想清楚了再过了。我发现我们很难交流…… 1. 既然空间翻倍了，那翻倍的空间从哪里来？ a) 把内存条从数组的尾端掰断然后再加一段吗？这怕不是要实现边长数组，这是要实现变长内存条，还是能从中间拉长的那种。b) 开一片新内存然后把旧的全部复制过去？嗯，小数组还好，大数组真是酸爽…… 2.既然你们都知道翻倍了，那翻倍隐含的 log2(N) 被怪物吃了吗？想想这个 log2(N) 去哪里了…… 只会喊些什么，翻倍，O(1)。翻倍怎么翻？ O(1) 怎么来的？想过吗？ |
 |
NUTMar 21, 2018
50
JAVA 相关的
Queue Stack LinkedList LinkedHashMap HashMap Guava 的 FutureTask （单向列表） RocketMQ 的 index （单向列表） |
 |
neoblackcapMar 21, 2018
51
@BlockBlockBlock 复制就是这样，当然可以使用 move，而且你的翻倍隐含的 O(logN)时间复杂度跟随机读取的 O(1)根本不冲突
|
|
BlockBlockBlockMar 21, 2018
52
|
|
neoblackcapMar 21, 2018
53
@BlockBlockBlock allocator 对于可变长数组不是必要，内存分配是 allocator 的事情。我是没看到 CPython 里面的 List 是有 LinkedList 的实现，C++的 vector 也不是。你说有请拿事实说话。
|
|
KIDJourneyMar 21, 2018
54
@hitmanx 我看了下实现，这样搞就不是双向队列了啊。
|
|
jmc891205Mar 21, 2018
55
@BlockBlockBlock
翻倍的复制操作不影响变长数组插入操作的平均时间复杂度是 O(1)。这叫 amortized analysis。大多数教科书对此问题都有讨论。你可以自行查找。 |
|
jmc891205Mar 21, 2018
56
@BlockBlockBlock 如果你手边没有任何算法与数据结构的教科书 你可以参考 Wikipedia 上的 Dynamic array 词条： https://en.wikipedia.org/wiki/Dynamic_array
|
 |
lauixMar 21, 2018
57
java 里的 list map 有个神马对象 就是
|
|
jmc891205Mar 21, 2018
58
我在#55 楼里说的“插入操作”不严谨 我指的是 push_back 操作 即在数组末尾插入元素
|
|
hszzzMar 21, 2018 via Android
60
@BlockBlockBlock 好的，谢谢你，有时间我去了解一下。
|
|
glasslionMar 21, 2018
61
@hszzz 别听那个 @BlockBlockBlock 胡说，vector/deque 都不是用链表实现的
|
|
KIDJourneyMar 21, 2018
62
|
|
bumzMar 21, 2018
64
@BlockBlockBlock
看了你的上一条回复，我还以为你说的链表其实是 malloc 内部实现隐含的链表（还取决于具体实现） 我原本以为你知道我们说的 O(1) 是 amortized O(1) 看到你提到操作系统课，我原以为你知道高级语言的层面和系统底层具体实现的层面不可混为一谈 现在我终于明白了你用户名的含义，谢谢你的最后一条回复。 |
|
KIDJourneyMar 22, 2018
65
@BlockBlockBlock 举个例子呗？
|
 |
CaturraMar 22, 2018
66
@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)的遍历,你也忽略了非连续空间访问速度上的差异,感性上效率很糟糕,实际上确实也挺糟糕的(别问为什么,我试过) |
|
CaturraMar 22, 2018
67
list 实现这玩意的复杂度和是否等长无关,缺乏睡眠有点语无伦次了
|
Select Language