Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
イテレータが 1 つだけの循環リンク リストを使用して、キューを実装する必要があります。私の疑問は、イテレータを最初のアイテムまたは最後のアイテムから維持する、パフォーマンスの点でどちらが良い方法ですか?
最初の項目へのポインターがある場合、リストの最後の操作は O(N) になります。リストの末尾へのポインターを使用すると、O(1) の先頭と末尾の両方で操作を実行できます。一般に、循環的にリンクされたリストがある場合、最初と最後に到達できるようにする必要があるため、答えは、最後へのポインターを使用するとパフォーマンスが向上するということです。