ほぼすべての Java インタビューで聞かれる質問: ArrayList と LinkedList の違いについての話

まえがき

みなさん、こんにちは。私はあなたの古い友人、Qing Geです。寂しがっていると思いますので、またここに来ました。そうですか?

Java のデータ構造が面接の焦点です。Java の面接に参加した学生ならある程度の経験があると思います。面接官がこのような質問をするとき、単に「使い方を知っている」というレベルにとどまるのではなく、Java で一般的に使用されるデータ型の基礎となる構造を学習したかどうかを確認したいことがよくあります。では、面接中にこの質問にうまく答え、面接官を満足させるにはどうすればよいでしょうか?

今回は、Java の高周波テスト ポイント ArrayList と LinkedList の原理を分析し、皆様のお役に立てれば幸いです。

ArrayList と LinkedList の概要

ArrayList最下層は、次の型の配列です。オブジェクト。初期容量は 10 で、動的拡張をサポートします。拡張された容量は現在の容量の 1.5 倍です。最大容量は Integer.MAX_VALUE - 8 (ただし、Integer.MAX_VALUE まで拡張できます)。空いた 8 ビットについては、 、現在の説明は、一部のマシンのメモリ オーバーフローを回避し、エラーの可能性を減らすためですです。

LinkedList最下層は、初期容量が 0 の双方向リンク リストです。容量を拡張するには、新しいノードを作成し、そのノードにポインタを指定するだけです。

これを口頭で表現可能な言​​語に簡略化し、面接中に学生が面接官に説明しやすくするために、ここではソース コードの補助的な説明を掲載しません。興味のある学生は自分でソース コードを確認してください。 . この領域の理解を深めるための内部構造とメソッド。

#違い

クエリ

• ArrayList のランダム アクセスは、要素が順番に格納されるため、非常に効率的です。添字インデックスを通じて、メモリ内のクエリされたデータの位置を知ることができます。アドレス指定は高速で、時間計算量は O(1);
• LinkedList のクエリ効率は低く、指定されたデータをクエリする場合、リンク リストを 1 つずつたどる必要があり、時間計算量は O(n) です。

挿入

• ArrayList は最後に効率的に挿入し、時間計算量は O(1) ですが、 in 他の位置での挿入効率は比較的低く、大量のデータ移動が必要となり、時間計算量は O(n) です;
• LinkedList は先頭への要素の挿入の方が効率的です次数はO(1)ですが、途中の指定位置に要素を挿入するには、要素の位置をトラバースして見つけてから挿入する必要があります。複雑さは O(n) です。

Delete

• ArrayList から要素を削除するには、終了ノードを除く大量のデータの移動が必要です。 O(n);
• LinkedList は要素の削除に比較的効率的です。ポインタのポイントを変更するだけで済みますが、要素を削除するにはデータの場所をクエリするためのトラバースが必要です。時間計算量は O (n) です。

メモリ空間

• ArrayList は配列をベースに実装されており、拡張ごとに容量が固定されるため、スペースの一部を予約する;
• LinkedList は二重リンク リストに基づいているため、データの保存に加えて、各ノードは前と次のノードのポインターも保存する必要があります。 、ある程度のスペースを消費します。

展開メカニズム

• ArrayList を展開するたびに、元の配列の要素を新しい配列;
• LinkedList はリンクされたリストであり、展開はありません。

同じ点

スレッドの安全性

ArrayList と LinkedList はどちらもスレッド セーフではないため、マルチスレッド環境では簡単にダーティ リーディングの問題が発生する可能性があります。Collections.synchronizedList() メソッドを使用すると、スレッド セーフを確保できます

ストレージ機能

保存された要素はすべて順序付けされており、繰り返すことができます。新しい要素はリストの最後に保存されます。

以上がほぼすべての Java インタビューで聞かれる質問: ArrayList と LinkedList の違いについての話の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。