python - 为什么在带有 “next” 和 “previous” 按钮的音乐播放器中使用双向链表，而使用列表更简单？

Question

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

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

有一些用途

• 带有“下一个”和“上一个”按钮的音乐播放器
• 一个应用程序，可以显示您的地铁在火车线上的位置
• 网络浏览器中的“撤消”和“重做”功能

---

使用列表会不会更简单？

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

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

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 队列可以很容易地实现为一个单向链表。

我同意一点:在已知元素列表上带有上一个和下一个按钮的音乐播放器可以实现为一个数组(什么是 Python 列表)。但是深度有限的撤消/重做功能是双向链表的绝佳用例:

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