Circular Linked list and the iterator

Question

I have a question in my algorithm class in data structures.

For which of the following representations can all basic queue operations be performed in constant worst-case time?

To perform constant worst case time for the circular linked list, where should I have to keep the iterator?

They have given two choices:

1. Maintain an iterator that corresponds to the first item in the list
   
2. Maintain an iterator that corresponds to the last item in the list.
   

My answer is that to get the worst case time we should maintain the iterator that correspond to the last item in the list but I don't know how to justify and explain. So what are important points needed for this answer justification.

Answer 1

For which of the following representations can all basic queue operations be performed in constant worst-case time?

My answer is that to get the worst case time we should maintain the iterator that correspond to the last item

Assuming that your circular list is singly-linked, and that "the last item" in the circular list is the one that has been inserted the latest, your answer is correct ^*. In order to prove that you are right, you need to demonstrate how to perform these four operations in constant time:

1. Get the front element - Since the queue is circular and you have an iterator pointing to the latest inserted element, the next element from the latest inserted is the front element (i.e. the earliest inserted).
2. Get the back element - Since you maintain an iterator pointing to the latest inserted element, getting the back of the queue is a matter of dereferencing the iterator.
3. Enqueue - This is a matter of inserting after the iterator that you hold, and moving the iterator to the newly inserted item.
4. Dequeue - Copy the content of the front element (described in #1) into a temporary variable, re-point the next link of the latest inserted element to that of the front element, and delete the front element.

Since none of these operations require iterating the list, all of them can be performed in constant time.

^* With doubly-linked circular lists both answers would be correct.