假设我有一个由三个元素组成的数据结构{1,2,3}
如果我只想执行以下操作,那么什么样的数据结构和时间复杂性会给我带来最好的结果？
- 将最后一个元素移动到数据结构的"前" - 删除(现在)最后一个元素
我找到了这个页面:http://essays.hexapodia.net/datastructures/它说一个双链表有一些操作的O(1)？
但是,我需要每次都保留元素的顺序,以便我可以进行转换.如果我有{1,2,3}我想要转移,得到3,1,2然后删除,留下3,1然后删除,留下1
如果我使用双链表,我的复杂性是O(1)???
是的,删除和添加两端的元素是双链表中的O(1),它保持指向头部和尾部的指针.由于可以通过这两个操作实现移位,因此也是O(1).
在循环链接列表中,您甚至可以通过执行自己的移位操作(仍然是O(1),但更快)
head = tail
if (tail != null) tail = tail.prev
| 归档时间： |
|
| 查看次数： |
804 次 |
| 最近记录： |