時間計算のArrayListとLinkedListの

第一パートから最後の要素を削除中： - 私は本で読んでいた時間計算のArrayListとLinkedListの

- LinkedListのから最後の要素を削除するための「データ構造とアルゴリズムをJavaで簡単に作られた」時間の複雑さということと、 ArraylistはO（n）です。しかしLinkedlistは内部的にDoublyLinkedlistを実装しているため、時間の複雑さはO（1）で、Arraylistの場合もArrayを内部実装するのでO（1）にする必要があります。

2パート： -

またのLinkedListの終了の要素の挿入はO（N）の時間計算量を有するが、LinkedListのは、端と前部に両方のポインタを維持することを言います。それでこの声明は正しい？さらに、最後にarraylistに要素を挿入する時間の複雑さは、配列がいっぱいでない場合はO（1）、配列がいっぱいの場合はO（n）です。なぜアレイがいっぱいならO（n）ですか？

第1部にお返事いただきありがとうございます。誰も第2部を説明してください。ありがとう:)

出典

2017-03-31 user3747182

本は間違っています。 Amazonのレビューの16％は本に多くの誤りがあり、1つか2つの星を付けていると言います。自分自身をより良い本にするのは良い時だと思う。 – dasblinkenlight

本では、これらの名前を持つjava.utilクラス、または同じ名前のデータ構造を参照していますが、本の中で提供されている別の実装がありますか？ –

それはあなたが呼んでいる方法によって異なります。

LinkedList.removeLast()を呼び出すと、O（1）と表示されます。 LinkedListは、リスト内の最初と最後のノードの両方にポインタを保持します。したがって、最後のノードに到達するためにリストをトラバースする必要はありません。

最後の要素のインデックスを持つLinkedList.remove(index)を呼び出すことは、最も近い終端からリストを横断するため、O（1）でもあります。 [ユーザー@andreasが以下のコメントで通知しました]

LinkedList.remove(Object)を呼び出している場合は、最初に一致するノードのO（n）検索があります。

同様に、ArrayListの場合、最後の要素のインデックスでArrayList.remove(index)を呼び出している場合は、O（1）です。他のすべてのインデックスについては、System.arrayCopy()コールがあります。これはO（n）でもかまいませんが、最後の要素については完全にスキップされています。

しかし、ArrayList.remove(Object)を呼び出すと、最初に一致するノードのO（n）検索があります。

出典

2017-03-31 16:27:19

'linkedList.remove（lastIndex）'は['LinkedList']（https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html）から_O（1）_です。 *リストにインデックスを付けるオペレーションは、指定されたインデックスに近い方の先頭または最後の**からリストをトラバースします* – Andreas

@アンドレアス：良い点;上の答えで、帰属とともに追加されました。 –

@AndyThomas私の質問の2番目の部分についても説明できます。ありがとう – user3747182

リンクリストの最後の要素を削除すると、すべてのレコードを最後まで移動する必要がある場合はO（n）が必要になります。しかし、二重にリンクされたjava.util.LinkedListの実装ではheadのみ参照を保持するのではなく、tailの参照を保持し、O（1）の最後を削除することもできます。これは、指定されたインデックスに近いほうのリストの先頭から最後を辿るように巧みに実装されています

出典

2017-03-31 16:30:12

「あなたは最後にO（1）を削除できますか？ – Andreas

これは、テールの参照を保持し、それを直接削除できるため、リストを最初からトラバースしないことを意味します。 –

あなたの答えは誤解を招きます。なぜなら理論では、リンクされたリストの最後の要素を削除するとO（n）が必要だとは言わないからです。理論（と事実）は、任意の要素を取り除くことはO（1）を要すると述べている。 *削除する要素の検索*は、検索方法やリンクされたリストが単独でリンクされているか二重にリンクされているかに応じて_O（n）_を取ることができますが、答えの最初のステートメントは何も言わず、したがって間違っています。少なくとも、誤解を招く。 – Andreas

時間計算のArrayListとLinkedListの

答えて

関連する問題