0

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

4

1 に答える 1

1

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

于 2012-05-07T17:04:44.147 に答える