1

センチネルとの単一リンクリストがあるとします。O(1) 時間で最後の要素を削除するには、最後の 2 つの要素へのハンドルを維持する必要があります。ただし、最後の 2 つの要素へのハンドルを維持すると、追加操作が複雑になります。

最後の 2 つの要素へのハンドルを維持せずに、O(1) でセンチネルを使用して単一リンク リストの最後の要素を削除する方法はありますか? Javaのサンプルコードをいただければ幸いです。

ありがとう。

4

2 に答える 2

3

通常の方法で実装された単一リンクリストでは、O(N)操作になります。

最後の要素のハンドルを保持することはそれほど複雑ではありません。片方向リストの実装では、多くの場合、 の最後に追加できるようにしますO(1)。ただし、O(1)「最後の削除」操作に直面して最後の要素へのリンクを維持することはできません。

考えてみてください。最後と最後から 2 番目のノードへのポインターを保持する場所があるとします。最後のノードを削除するときは、次のことを行う必要があります。

  1. next最後から 2 番目のノードのポインタを null に更新し、
  2. last最後から 2 番目のノードを指すようにポインターを更新します。
  3. secondToLastその前のノードを指すようにポインターを更新します。

しかし、最初からリストをトラバースせずに最後のステップを実行するにはどうすればよいですか...これはO(N)操作ですか?

ここで、リンクされたリストをコーディングして、最後の要素をO(1) 最初に削除し、O(N)それ以降は最後に新しい要素を追加するまでコード化できると思います。しかし、通常とは異なるユースケースでない限り、この「最適化」は価値がありません。

java.util.LinkedList双方向リンク リストを使用し、removeLast()メソッドがO(1).`である を使用する方がよいでしょう。

于 2012-07-08T01:23:58.677 に答える
2

いいえ、末尾からの削除は二重リンク リストにのみ適用されます。新しい NULL ターミネータを前のリンクに配置するには、バック ポインタが必要です。要件を満たすために、リストを二重にリンクすることをお勧めします。

容器は自作ですか？二重にリンクされている java.util.LinkedList を使用しないのはなぜですか?

于 2012-07-08T01:23:05.613 に答える