V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
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
miniyao
V2EX  ›  Python

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

  •  
  •   miniyao · 2018-03-20 07:33:01 +08:00 · 9463 次点击
    这是一个创建于 2201 天前的主题,其中的信息可能已经有所发展或是发生改变。
    平时用到双向链表的机会少,有哪些场景下使用双向链表是比较好的选择?
    67 条回复    2018-03-22 12:56:05 +08:00
    kunluanbudang
        1
    kunluanbudang  
       2018-03-20 07:57:11 +08:00 via Android   ❤️ 1
    lru
    tamlok
        2
    tamlok  
       2018-03-20 07:58:40 +08:00 via Android   ❤️ 3
    面试
    zpxshl
        3
    zpxshl  
       2018-03-20 08:01:12 +08:00 via Android
    linkedlist 就是...
    lingerz
        4
    lingerz  
       2018-03-20 08:04:27 +08:00 via Android
    考级
    vegito2002
        6
    vegito2002  
       2018-03-20 08:17:27 +08:00
    LRU
    yeept
        7
    yeept  
       2018-03-20 08:49:43 +08:00
    LRU
    nl101531
        8
    nl101531  
       2018-03-20 08:55:57 +08:00 via Android
    fork join 的工作窃取,一个从头一个从尾,降低冲突概率。
    dobelee
        9
    dobelee  
       2018-03-20 08:58:04 +08:00 via Android
    这个很少暴露在高级语言中,通常会有集合或替代方案。主要还是考试和面试吧。当然有助于新人理解数据结构模型。
    snailsir
        10
    snailsir  
       2018-03-20 10:04:49 +08:00
    区块链?
    Srar
        11
    Srar  
       2018-03-20 10:08:15 +08:00   ❤️ 1
    hashtable + 双链表 LRU
    chuhades
        12
    chuhades  
       2018-03-20 10:12:25 +08:00
    用单链多一点
    BlockBlockBlock
        13
    BlockBlockBlock  
       2018-03-20 10:26:48 +08:00
    不然你觉得你用的那些可变长度的数组在底层都是怎么存的?
    TestSmirk
        14
    TestSmirk  
       2018-03-20 10:27:52 +08:00
    面试?
    hx1997
        15
    hx1997  
       2018-03-20 10:30:39 +08:00 via Android
    底层开发很多吧… 像操作系统
    glasslion
        16
    glasslion  
       2018-03-20 10:40:53 +08:00   ❤️ 1
    @BlockBlockBlock 真没拿双向链表去实现可变长度的数组的
    kljsandjb
        17
    kljsandjb  
       2018-03-20 10:42:11 +08:00 via iPhone
    LRU :)
    jmc891205
        18
    jmc891205  
       2018-03-20 11:11:38 +08:00
    @BlockBlockBlock 用双向链表实现数组的话 访问元素的时间复杂度太高了
    jmc891205
        19
    jmc891205  
       2018-03-20 11:16:57 +08:00
    不是很懂这个问题为啥发在 Python 节点
    以我粗浅的知识 在写 Python 的时候 无论是后端开发、机器学习、运维脚本 都不会用到双向链表。
    weics
        20
    weics  
       2018-03-20 11:55:19 +08:00
    LinkedList 就是双向链表,获取元素的时候,如果元素在后面,直接用双向链表反向获取
    linhanqiu
        21
    linhanqiu  
       2018-03-20 12:11:21 +08:00
    面试必考?平常的时候写小东西时提高效率?
    swulling
        22
    swulling  
       2018-03-20 12:14:19 +08:00 via iPhone
    双向链表是很常用的数据结构啊,因为单向链表没啥实用价值,基本用的链表都是双向的


    比如 Redis 的双向链表,http://redisbook.com/preview/adlist/implementation.html,具体的用处有发布订阅机制,客户端维护,列表键底层实现之一,等等
    vjnjc
        23
    vjnjc  
       2018-03-20 12:26:38 +08:00
    以前都喜欢自己写结构,tree,node,链表,后来发现都有现成实现。。。
    RubyJack
        24
    RubyJack  
       2018-03-20 12:28:05 +08:00
    和 hashmap 一起搞 lru
    BlockBlockBlock
        25
    BlockBlockBlock  
       2018-03-20 12:31:58 +08:00
    哦,原来在 python 节点下……那就怪不得有人不懂了……
    sohoer
        26
    sohoer  
       2018-03-20 12:36:18 +08:00
    Queue
    aheadlead
        27
    aheadlead  
       2018-03-20 12:38:13 +08:00
    STL 的 deque 了解一下
    bumz
        28
    bumz  
       2018-03-20 12:41:21 +08:00
    @aheadlead deque 一般不是链表实现的
    bumz
        29
    bumz  
       2018-03-20 12:47:06 +08:00
    @bumz STL deque 不能用链表实现,因为 STL deque 的 random access 是 O(1)
    aheadlead
        30
    aheadlead  
       2018-03-20 12:47:28 +08:00
    @bumz 是我错了…应该是 list
    bumz
        31
    bumz  
       2018-03-20 12:49:01 +08:00
    @BlockBlockBlock 变长数组随机是 O(1),不能用链表实现

    变长数组一般用空间自动翻倍的数组实现
    BlockBlockBlock
        32
    BlockBlockBlock  
       2018-03-20 14:15:11 +08:00
    @bumz

    翻倍的空间从哪里来?怎么管理?
    BlockBlockBlock
        33
    BlockBlockBlock  
       2018-03-20 14:22:09 +08:00 via iPhone
    @bumz
    我不明白你是怎么脑补出来我说的链表每个节点是装着一个元素的?如果每个链表节点装的是一片内存空间呢?这是典型的内存片的管理方式你们大学时候上操作系统课不学的吗?
    vincenttone
        34
    vincenttone  
       2018-03-20 14:27:50 +08:00
    php 的 array,redis 的 list 等等等等
    safeoy
        35
    safeoy  
       2018-03-20 14:37:15 +08:00
    LRU
    wcsjtu
        36
    wcsjtu  
       2018-03-20 16:09:22 +08:00 via Android
    Django 的 lru cache 了解一下?
    snail1988
        37
    snail1988  
       2018-03-20 19:56:08 +08:00
    @BlockBlockBlock 要求随机存取 O(1)的数据结构为什么用链表,上来就喷别人
    BlockBlockBlock
        38
    BlockBlockBlock  
       2018-03-20 20:09:02 +08:00
    @snail1988

    请问你看懂我在说什么了吗?
    如果没看懂我也不多做解释了……
    我不是你计算机老师,不负责教你计算机基础知识……
    orangeade
        39
    orangeade  
       2018-03-20 20:11:02 +08:00 via Android
    python 里多了去了,有空多看看 python 解释器,pypy 和官方库的源码
    hitmanx
        40
    hitmanx  
       2018-03-20 20:37:24 +08:00   ❤️ 1
    @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
    KIDJourney
        41
    KIDJourney  
       2018-03-20 20:40:38 +08:00
    @BlockBlockBlock
    不是很懂,不管你链表装什么,随机读取都不是 O(1)的。
    Wicked
        42
    Wicked  
       2018-03-20 21:08:36 +08:00 via iPhone
    常数时间删除元素,保序遍历,需要这些特性的场合都可以用
    bobuick
        43
    bobuick  
       2018-03-20 21:58:57 +08:00
    一大堆用处。
    如果只写 web, 只写 CRUD 基本用不到
    akira
        44
    akira  
       2018-03-20 22:52:46 +08:00
    链表的最大作用。。
    是为了让人可以继续学习后续的树形结构。。
    hszzz
        45
    hszzz  
       2018-03-20 23:15:40 +08:00 via Android
    @BlockBlockBlock STL 里的 vector,有一个 capacity 和 size 的。capacity 总是大于等于 size 的,用完了就会自动重新申请,一般是 size 的两倍。
    hszzz
        46
    hszzz  
       2018-03-20 23:16:54 +08:00 via Android
    @BlockBlockBlock 防止频繁地申请和释放内存。
    lzjamao
        47
    lzjamao  
       2018-03-21 00:19:44 +08:00 via Android
    换个思维。
    双向链表有什么优势和劣势。
    技术符合需求,不是需求符合技术
    bravecarrot
        48
    bravecarrot  
       2018-03-21 01:51:23 +08:00 via iPhone
    @BlockBlockBlock 随机存取的时候 岂不是太慢了..
    BlockBlockBlock
        49
    BlockBlockBlock  
       2018-03-21 08:23:10 +08:00
    @bravecarrot
    @hszzz
    @KIDJourney
    @bumz
    @snail1988
    @jmc891205
    @glasslion
    @jmc891205

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

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

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

    只会喊些什么,翻倍,O(1)。翻倍怎么翻? O(1) 怎么来的?想过吗?
    NUT
        50
    NUT  
       2018-03-21 08:49:35 +08:00
    JAVA 相关的
    Queue
    Stack
    LinkedList
    LinkedHashMap
    HashMap
    Guava 的 FutureTask (单向列表)
    RocketMQ 的 index (单向列表)
    neoblackcap
        51
    neoblackcap  
       2018-03-21 09:30:43 +08:00
    @BlockBlockBlock 复制就是这样,当然可以使用 move,而且你的翻倍隐含的 O(logN)时间复杂度跟随机读取的 O(1)根本不冲突
    BlockBlockBlock
        52
    BlockBlockBlock  
       2018-03-21 09:34:22 +08:00
    @neoblackcap

    看不懂就算了……不多做解释了
    neoblackcap
        53
    neoblackcap  
       2018-03-21 10:25:19 +08:00
    @BlockBlockBlock allocator 对于可变长数组不是必要,内存分配是 allocator 的事情。我是没看到 CPython 里面的 List 是有 LinkedList 的实现,C++的 vector 也不是。你说有请拿事实说话。
    KIDJourney
        54
    KIDJourney  
       2018-03-21 10:47:44 +08:00
    @hitmanx 我看了下实现,这样搞就不是双向队列了啊。
    jmc891205
        55
    jmc891205  
       2018-03-21 10:51:50 +08:00
    @BlockBlockBlock
    翻倍的复制操作不影响变长数组插入操作的平均时间复杂度是 O(1)。这叫 amortized analysis。大多数教科书对此问题都有讨论。你可以自行查找。
    jmc891205
        56
    jmc891205  
       2018-03-21 10:57:44 +08:00
    @BlockBlockBlock 如果你手边没有任何算法与数据结构的教科书 你可以参考 Wikipedia 上的 Dynamic array 词条: https://en.wikipedia.org/wiki/Dynamic_array
    lauix
        57
    lauix  
       2018-03-21 11:01:00 +08:00
    java 里的 list map 有个神马对象 就是
    jmc891205
        58
    jmc891205  
       2018-03-21 11:02:47 +08:00
    我在#55 楼里说的“插入操作”不严谨 我指的是 push_back 操作 即在数组末尾插入元素
    hitmanx
        59
    hitmanx  
       2018-03-21 11:50:00 +08:00
    @jmc891205 对的,是 amortized O(1)
    hszzz
        60
    hszzz  
       2018-03-21 12:44:12 +08:00 via Android
    @BlockBlockBlock 好的,谢谢你,有时间我去了解一下。
    glasslion
        61
    glasslion  
       2018-03-21 14:44:41 +08:00
    @hszzz 别听那个 @BlockBlockBlock 胡说,vector/deque 都不是用链表实现的
    KIDJourney
        62
    KIDJourney  
       2018-03-21 16:51:56 +08:00
    @hitmanx 口胡,这样搞就不是用双向链表实现的了。

    @BlockBlockBlock 你举个例子吧?我下午看了下 c++ vector 和 list 的实现,都没有用链表。
    hszzz
        63
    hszzz  
       2018-03-21 17:49:02 +08:00 via Android
    @glasslion 哈哈,初学者不敢和前辈们争论啊。其实我也不信,毕竟 primer 不是那样说的。
    bumz
        64
    bumz  
       2018-03-21 22:32:30 +08:00
    @BlockBlockBlock

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

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

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

    现在我终于明白了你用户名的含义,谢谢你的最后一条回复。
    KIDJourney
        65
    KIDJourney  
       2018-03-22 11:50:17 +08:00
    @BlockBlockBlock 举个例子呗?
    Caturra
        66
    Caturra  
       2018-03-22 12:50:38 +08:00
    @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
        67
    Caturra  
       2018-03-22 12:56:05 +08:00
    list 实现这玩意的复杂度和是否等长无关,缺乏睡眠有点语无伦次了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5241 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 89ms · UTC 09:16 · PVG 17:16 · LAX 02:16 · JFK 05:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.