访问第一个和最后一个节点的恒定时间

Question

如何修改基于链表的队列，以便无论队列中的数据节点如何，都可以在恒定时间内访问第一个和最后一个节点？

Answer 1

您将保留两个指针/引用变量，一个用于队列的头部，另一个用于尾部。当您插入一个项目时，您会将尾部设置为最后插入的项目，当您移除一个项目后，您的头显然会转到队列中的下一个项目。由于head和tail有两个变量，因此访问它们将是一个恒定的时间操作。

这是创建具有链表本身的队列的一般方法，这将需要从队列中插入项目和删除项目，这里没有什么特别的。