为什么在带有“下一个”和“上一个”按钮的音乐播放器中使用双向链表，而使用列表更简单？
Why is a doubly-linked-list used in a music player with “next” and “previous” buttons while using list is simpler?
我正在 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]
来自官方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;
说到他们选择双向链表的原因：
• Skip Back/Forward- 因为双链表中的每个节点都有一个指向前一个和下一个节点的指针，所以很容易实现 skip forward/backward 功能。
• 播放下一首曲目 - 指向下一个节点的指针也使得在曲目结束时开始下一首曲目变得非常容易。
• 附加 当您将新曲目添加到播放列表时，您会将其附加到末尾。在链表中，添加一个新元素是常数时间——O(1) 操作。请注意，当从数据源读取歌曲并将其添加到播放列表时，这将作为一系列附加调用来完成。
• Beginning/End- 最后，由于链表具有头部和尾部属性，这提供了一种简单的方法来描述播放列表的开头和结尾
链表消耗的内存有限，如果你有更多的数据，双向链表可以分配更多的内存。链表将保留下一个元素的引用，双向链表将保留上一个和下一个元素的引用。
由于双向链表对两侧都有引用，因此内存消耗更多但访问元素的效率更高（反向迭代也是如此（BACK/NEXT））
Reference means - Address of next / previous element
撤消和重做 - 我相信，它只需要一个链表，因为它只需要较少的内存和从一侧进行插入和删除操作对于简单任务
请参考Dictionary best data structure for train routes?了解“一个显示地铁在火车线路上的位置的应用程序”
删除和插入的时间复杂度为O(1)，查找为O(n)
链表知识请参考pythonDoes python have built-in linkedList data structure?
从算法的角度来看，有不同的序列容器类型：
静态数组
它是最简单的容器，具有静态（最大）大小和直接访问（通过数字索引）
动态数组
您仍然可以直接访问数字索引，但大小可以任意增长（受可用内存限制）。 Python lists 其实落在这里。缺点是当它们达到分配的大小时，它们可能需要完全重新分配和复制。移除元素也是一个代价高昂的操作
单链表
在头部添加和删除元素很容易，就像在已找到的其他元素之后插入一个新元素（或删除一个元素）一样。您只能在一个方向上扫描它们，并且找到一个知道其位置相当长的元素（无法直接访问）。每个节点有一个索引的开销
双向链表
与单向链表相比，您可以双向扫描它们并且在元素之前插入（或删除）很容易。也没有直接访问，开销是每个节点两个索引
动态数组是大多数语言中的多用途工具，并且是标准的Python列表。只需添加和删除很少的内容，它们就可以提供易用性和正确的性能。但是其他容器确实有用例。例如，一个 fifo 队列可以很容易地实现为一个单向链表。
我同意一点：在已知元素列表上带有上一个和下一个按钮的音乐播放器可以实现为一个数组（Python列表是什么).但是深度有限的 undo/redo 功能是双向链表的绝佳用例：
- 你希望能够从两侧移除（一旦达到深度，每次添加都必须删除最旧的元素）
- 你只需要从一个元素开始（向任何方向）迈出一步
根据我在许多不同问题领域的编程经验，几乎没有使用链表的理由，无论是单链表还是双向链表。
理论上的优势是链表支持在链表的任意位置插入和移除O(1)。但是在今天的硬件上，你需要一个相当大的列表（几千到几万项）并且你需要非常频繁地进行插入和删除操作，然后这个优势才真正开始发挥作用练习。
我正在 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]
来自官方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;
说到他们选择双向链表的原因：
• Skip Back/Forward- 因为双链表中的每个节点都有一个指向前一个和下一个节点的指针，所以很容易实现 skip forward/backward 功能。
• 播放下一首曲目 - 指向下一个节点的指针也使得在曲目结束时开始下一首曲目变得非常容易。
• 附加 当您将新曲目添加到播放列表时，您会将其附加到末尾。在链表中，添加一个新元素是常数时间——O(1) 操作。请注意，当从数据源读取歌曲并将其添加到播放列表时，这将作为一系列附加调用来完成。
• Beginning/End- 最后，由于链表具有头部和尾部属性，这提供了一种简单的方法来描述播放列表的开头和结尾
链表消耗的内存有限，如果你有更多的数据，双向链表可以分配更多的内存。链表将保留下一个元素的引用，双向链表将保留上一个和下一个元素的引用。
由于双向链表对两侧都有引用，因此内存消耗更多但访问元素的效率更高（反向迭代也是如此（BACK/NEXT））
Reference means - Address of next / previous element
撤消和重做 - 我相信，它只需要一个链表，因为它只需要较少的内存和从一侧进行插入和删除操作对于简单任务
请参考Dictionary best data structure for train routes?了解“一个显示地铁在火车线路上的位置的应用程序”
删除和插入的时间复杂度为O(1)，查找为O(n)
链表知识请参考pythonDoes python have built-in linkedList data structure?
从算法的角度来看，有不同的序列容器类型：
静态数组
它是最简单的容器，具有静态（最大）大小和直接访问（通过数字索引）
动态数组
您仍然可以直接访问数字索引，但大小可以任意增长（受可用内存限制）。 Python lists 其实落在这里。缺点是当它们达到分配的大小时，它们可能需要完全重新分配和复制。移除元素也是一个代价高昂的操作
单链表
在头部添加和删除元素很容易，就像在已找到的其他元素之后插入一个新元素（或删除一个元素）一样。您只能在一个方向上扫描它们，并且找到一个知道其位置相当长的元素（无法直接访问）。每个节点有一个索引的开销
双向链表
与单向链表相比，您可以双向扫描它们并且在元素之前插入（或删除）很容易。也没有直接访问，开销是每个节点两个索引
动态数组是大多数语言中的多用途工具，并且是标准的Python列表。只需添加和删除很少的内容，它们就可以提供易用性和正确的性能。但是其他容器确实有用例。例如，一个 fifo 队列可以很容易地实现为一个单向链表。
我同意一点：在已知元素列表上带有上一个和下一个按钮的音乐播放器可以实现为一个数组（Python列表是什么).但是深度有限的 undo/redo 功能是双向链表的绝佳用例：
- 你希望能够从两侧移除（一旦达到深度，每次添加都必须删除最旧的元素）
- 你只需要从一个元素开始（向任何方向）迈出一步
根据我在许多不同问题领域的编程经验，几乎没有使用链表的理由，无论是单链表还是双向链表。
理论上的优势是链表支持在链表的任意位置插入和移除O(1)。但是在今天的硬件上，你需要一个相当大的列表（几千到几万项）并且你需要非常频繁地进行插入和删除操作，然后这个优势才真正开始发挥作用练习。