リンクされたリストは、いつもタイトルのような

Question

のようなデータ構造を使用しています。私の質問は、リンクされたリストが使用する最良のデータ構造である場合の例を挙げることができます。私は本当に何かを考えるのに苦労しており、私のコードではハッシュマップやリストなどを使うだけです。

http://bigocheatsheet.com/ここでは、さまざまな操作のBig O'sのチートシートを見ることができます。リンクされたリストは、複雑さの点でスタックやキューよりも優れていません。そして、私は誰かがリンクされたリストをこれらの上で例えば使用するかもしれないか知りたいと思った？完璧な答えは、「私はXYZをやろうとしていたとしましょう。配列の場合は{コードを入力してください}のようになりますが、リンクされたリストを使うと{より多くのコード}。複雑さやスペースは、リンクされたリストの方が実質的に優れています。

私は誰かが私にリンクリストが何であるか教えてくれるとは思わない。私はリンクされたリストが何であり、どのように実装されているのか知っています。あなたは人々のラインアップを持っている、とどこか途中であなたは多くの人々を追加したい場合は

おかげ

Answer 1

を考えてみましょう。従来のArrayListを使用した場合は、それ以降のすべての要素をシフトする必要があるため、1人あたりのインデックス作成のためO（N）！ LinkedListでは、各人物はO（1）、O（N）は中間になります。リンクされたリストは、何かを再インデックスしたり、ローカルポインタを調整したりする必要がないので、要素を途中で追加すると非常に素早くなります。

Answer 2

誰かがC++標準テンプレートライブラリを調査し、リンクリストがすべての共通基本構造のうちで最も少なく使用されていることがわかりました。だからあなたは正しいです。彼らはあまり使われていません。配列をランダムにアクセスする必要がないとき、Nを知らないときやNの上限が適度にあるとき、そして挿入と削除が共通していて時間が重大なときに便利です。途中の挿入は配列の場合と同様にO（N）ですが、実際の操作はかなり安価です（メモリのシフトではなくポインタ逆参照）。先頭の挿入はO（1）です。終了ポインタ。