c++ - 使用循环链表遍历队列

Question

我必须使用只有一个迭代器的循环链表来实现一个队列。我的疑问是在性能方面哪个是更好的方法，维护第一项或最后一项的迭代器？

Answer 1

好吧，如果你有一个指向第一项的指针，那么列表末尾的操作将是 O(N)。使用指向列表末尾的指针，您可以在 O(1) 中对开头和结尾进行操作。一般来说，如果你有一个循环链表，那么你希望能够到达开头和结尾，所以答案是使用指向结尾的指针你的性能会更好。