循環鏈表和迭代器

Question

我在數據結構中的算法類中有一個問題。

對於以下哪種表示法，所有基本隊列操作都可以在恆定的最差情況下執行？

要爲循環鏈表執行常數最差情況時間，我應該在哪裏保持迭代器？

他們給了兩個選擇：

1. 保持對應的第一個項目在列表中
   
2. 保持對應列表中的最後一個項目一個迭代的迭代器。
   

我的回答是，讓最壞的情況時，我們應該保持這種對應列表中的最後一個項目的迭代器，但我不知道該如何辯解和解釋。那麼這個答案的理由需要什麼重點。

Answer 1

對於以下哪種表示，所有基本隊列操作都可以在恆定的最差情況下執行？

我的回答是，讓最壞的情況時，我們應該保持相對應的最後一個項目

假設你的循環列表單鏈表的迭代器，並說：「最後一個項目」在通告清單是最新插入的清單，你的回答是正確的^*。爲了證明你是正確的，你需要演示如何在固定時間內執行這四項行動：

1. 獲得前件 - 由於隊列是圓形的，你有指向最新的迭代器插入的元素中，來自最近插入的下一個元素是前面元素（即最早插入的元素）。
2. 獲取返回元素 - 由於您維護指向最新插入元素的迭代器，因此獲取隊列的後面是取消引用迭代器的問題。
3. 入隊 - 這是一個插入你持有的迭代器之後，並將迭代器移動到新插入的項目的問題。
4. 出列 - 將前面元素的內容（在＃1中描述）複製到臨時變量中，將最新插入元素的下一個鏈接重新指向前面元素的下一個鏈接，並刪除前面元素。

由於這些操作都不需要迭代列表，所有這些操作都可以在恆定時間內執行。

^*使用雙向鏈接的圓形列表，兩個答案都是正確的。