c++ - 循環リンクリストを使用してキューを反復処理する

Question

イテレータが 1 つだけの循環リンク リストを使用して、キューを実装する必要があります。私の疑問は、イテレータを最初のアイテムまたは最後のアイテムから維持する、パフォーマンスの点でどちらが良い方法ですか?

Answer 1

最初の項目へのポインターがある場合、リストの最後の操作は O(N) になります。リストの末尾へのポインターを使用すると、O(1) の先頭と末尾の両方で操作を実行できます。一般に、循環的にリンクされたリストがある場合、最初と最後に到達できるようにする必要があるため、答えは、最後へのポインターを使用するとパフォーマンスが向上するということです。