为什么在音乐播放器中使用带有“下一步”和“上一步”按钮的双链接列表，而使用列表更简单？

Question

我正在学习Codecademy上的链表，有一条说明说

Before moving on, take a moment to think about doubly-linked lists. What do you think are some possible real-life uses?

有些用处

• 带有“下一步”和“上一步”按钮的音乐播放器
• 一个显示地铁线路位置的应用程序
• web浏览器中的“撤消”和“重做”功能

---

使用列表会更简单吗

使用链表执行这些任务有什么好处

例如，使用音乐播放器的“下一步”和“上一步”按钮列表

counter = 0
playlist = ['song', 'song2', 'song3', 'song4']
current_song = playlist[counter]
next_song = playlist[min(counter+1, len(playlist)-1]

Answer 1

从算法角度来看，有不同的序列容器类型：

• 静态阵列

  它是最简单的容器，具有静态（最大）大小和直接访问（通过数字索引）

• 动态数组

  您仍然可以使用数字索引直接访问，但大小可以任意增长（受可用内存限制）。Python列表实际上落在这里。缺点是，当它们达到分配的大小时，可能需要完全重新分配和复制。移除元件也是一项成本高昂的操作

• 单链表

  在头部添加和删除元素很容易，就像在已经找到的另一个元素之后插入一个新元素（或删除一个）一样。您只能在一个方向上扫描它们，并且查找知道其位置的元素相当长（无法直接访问）。它的开销是每个节点一个索引

• 双链表

  与单链接列表相比，您可以在元素容易插入（或删除）之前，在两个方向上扫描它们。也没有直接访问，开销是每个节点两个索引

在大多数语言中，动态数组是多用途的工作平台，是标准的Python列表。只需很少的添加和删除，即可提供易用性和正确的性能。但是其他容器也有用例。例如，fifo队列可以很容易地实现为单链表

我同意一点：在已知元素列表上具有prev和next按钮的音乐播放器可以实现为一个数组（Python列表是什么）。但深度有限的撤销/重做功能是双链接列表的最佳用例：

• 您希望能够从两侧删除（一旦达到深度，每次添加都必须删除最旧的元素）
• 您只需要从一个元素开始走一步（在任何方向上）

Answer 2

来自官方Documentation

Python’s lists are really variable-length arrays, not Lisp-style linked lists. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array and the array’s length in a list head structure. This makes indexing a list a[i] an operation whose cost is independent of the size of the list or the value of the index. When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don’t require an actual resize.

因此，python列表只是可变长度数组。我深入研究了cpython的source code，在扩展宏时，基本结构被定义为：

typedef struct { 
    PyObject_VAR_HEAD 
    PyObject **ob_item; 
    Py_ssize_t allocated; 
} PyListObject; 

谈到他们选择双链接列表的原因：

•向后/向前跳过-由于双链接列表中的每个节点都有指向上一个和下一个节点的指针，因此很容易实现向前/向后跳过功能

•播放下一首曲目-指向下一个节点的指针还可以在曲目结束时轻松启动下一首曲目

•追加当您向播放列表中添加新曲目时，您会将其固定在播放列表的末尾。在链表中，添加新元素是常量时间-O（1）操作。请注意，当歌曲从数据源读入并添加到播放列表中时，这将作为一系列附加调用来完成

•开始/结束-最后，由于链接列表具有头和尾属性，因此提供了一种简单的方法来描绘播放列表的开始和结束

Answer 3

链表占用有限的内存，如果有更多数据，双链表可以分配更多内存。链表将保留对下一个元素的引用，其中双链表将保留对上一个和下一个元素的引用

由于双链表的两边都有引用，所以访问元素的内存消耗更大，但效率更高（同样是反向迭代（BACK/NEXT））

Reference means - Address of next / previous element

撤消和重做-我相信，它只需要一个链表，因为它只需要较少的内存，只需从一侧执行插入和删除操作即可完成简单任务

请参考Dictionary best data structure for train routes?了解“一个显示地铁在火车线上位置的应用程序”

删除和插入的时间复杂度为O（1），而搜索的时间复杂度为O（n）

请参阅了解时间复杂性https://www.oreilly.com/library/view/php-7-data/9781786463890/c5319c42-c462-43a1-b33d-d683f3ef7e35.xhtml

请参阅了解python中链表的更多信息Does python have built-in linkedList data structure?