现实生活中使用双向链表

Question

什么时候使用双向链表似乎是现实生活场景中的最佳选择？有人可以建议实际使用吗？

Answer 1

添加到templatetypedef的答案.

您考虑以下应用程序:

- A music player which has next and prev buttons.
- Represent a deck of cards in a game.
- The browser cache which allows you to hit the BACK-FORWARD pages.
- Applications that have a Most Recently Used list (a linked list of file names)
- Undo-Redo functionality

您想要从特定点遍历两侧的任何应用程序.

Answer 2

在许多操作系统中,线程调度程序(选择哪些进程需要在哪些时间运行的东西)维护一个双向链接的列表,其中包含随时运行的所有进程.这使得将进程从一个队列(例如,需要转向运行的活动进程列表)移动到另一个队列(例如,被阻止并等待释放它们的进程列表)变得容易.这里使用双链表允许这些拼接和重新连接中的每一个在时间O(1)中运行并且没有任何内存分配,并且双链表结构适用于使用队列实现调度程序(仅限于您需要从前面拉出东西.)