移动和移除头部元素的最佳bigO时间复杂度是多少？

Question

假设我有一个由三个元素{1,2,3}组成的数据结构

如果我只想执行以下操作，什么样的数据结构和时间复杂度会给我带来最好的结果？

现在，将最后一个元素放在数据结构的“-Shifting”前面。(现在)最后一个元素

我发现了这个页面：http://essays.hexapodia.net/datastructures/，它说一个双向链表对于某些操作有O(1)？

然而，我每次都需要保持元素的顺序，这样我才能进行移位。如果我有{1,2,3}，我会想要移位，获取3,1,2，然后移除，留下3,1，然后移除，留下1

如果我使用双向链表，复杂度会是O(1)吗？

Answer 1

是的，删除和添加两端的元素在双向链表中是O(1)，该双向链表保持指向头部和尾部的指针。因为移位可以用这两个操作来实现，所以它也是O(1)。

在循环链表中，您甚至可以通过执行以下操作来实现自己的移位操作(仍然是O(1)，但速度更快

head = tail
if (tail != null) tail = tail.prev

Answer 2

使用deque，它是用于在两端插入或移除的O(1)。

Answer 3

在我看来，如果旋转是你唯一想做的操作，那么使用一个循环数组(正常的数组，头部可以在尾部之后)

使用循环，您将节省% 1。删除% 2。插入

你所要做的就是改变头部和尾部指针。