Java のリスト: ArrayList および LinkedList 実装インターフェイスの簡単な紹介-＆＃＆チュートリアル-php.cn

Java のリスト: ArrayList および LinkedList 実装インターフェイスの簡単な紹介

php是最好的语言

リリース： 2018-07-26 14:22:00

オリジナル

3273 人が閲覧しました

ArrayList は配列に基づいて実装されており、C 言語でメモリを動的に適用して動的に拡張するのと同様に、容量が自動的に拡張できる動的配列です。 LinkedList は、双方向循環リンクリストに基づいて実装されています (ソースコードから簡単に確認できます)。リンクリストとして動作するだけでなく、スタック、キュー、および両端キューとしても使用できます。

1. List の概要

2. ArrayList の特徴

ArrayList は配列に基づいて

実装されており、その

容量は、 C言語メモリを適用して動的にメモリを増やします。 ArrayList はスレッド安全ではありません、シングルスレッド環境でのみ使用できます マルチスレッド環境では、Collections.synchronizedList(List list) 関数を使用してスレッドセーフな ArrayList を返すことを検討できます。クラスを使用するか、パッケージの下で同時 CopyOnWriteArrayList クラスを使用することもできます。

ArrayListはSerializableインターフェイスを実装しているため、シリアル化をサポートしており、シリアル化を通じて送信できますArrayListはRandomAccessインターフェイスを実装し、高速ランダムアクセスをサポートしています。これは実際には

添字付きシリアル番号による高速アクセスです

実装されたCloneableインターフェイス、

クローン作成可能

その3つの異なる構築方法に注目してください。パラメータなしのコンストラクタで構築される ArrayList の容量はデフォルトで 10 です。Collection パラメータを持つコンストラクタは、Collection を配列に変換し、ArrayList 実装配列の elementData に割り当てます。

容量を拡張する方法、ensureCapacityに注意してください。要素が ArrayList (1 またはグループの場合もあります) に追加されるたびに、十分な容量を確保するためにこのメソッドを呼び出す必要があります。容量が現在の要素数を収容するのに十分でない場合、新しい容量は古い容量の 1.5 倍に 1 を加えた値に設定されます。設定された新しい容量が十分でない場合、新しい容量は渡されたパラメータ (つまり、は必要な容量です)、次に Arrays.copyof() メソッドを使用して要素を新しい配列にコピーします (詳細については、以下のポイント 3 を参照してください)。このことから、容量が足りない場合は、要素を追加するたびに元の要素を新しい配列にコピーする必要があり、非常に時間がかかることがわかります。そのため、ArrayList を使用するのは、次の場合のみにすることをお勧めします。要素の数は事前に決定できますが、それ以外の場合は LinkedList を使用することをお勧めします。 Arrays.copyof() メソッドと System.arraycopy() メソッドは、ArrayList の実装で広範囲に呼び出されます。これら 2 つのメソッドの実装について深く理解する必要があります。

まず、Arrays.copyof() メソッドを見てみましょう。多くのオーバーロードされたメソッドがありますが、実装の考え方は同じです。ジェネリックバージョンのソースコードを見てみましょう:

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

ログイン後にコピー

明らかに、別の copyof メソッドが呼び出されます。これには 3 つのパラメーターがあり、最後のパラメーターは変換を指定します。の要素が新しい配列にコピーされます。

System.arraycopy() メソッドを見てみましょう。このメソッドはネイティブとしてマークされており、システムの C/C++ コードを呼び出します。JDK では見ることができませんが、そのソースコードは openJDK で見ることができます。この関数は実際には、最終的に C 言語の memmove() 関数を呼び出すため、同じ配列内の要素の正しいコピーと移動を保証でき、一般的なコピー方法よりもはるかに効率的であり、配列のバッチ処理に非常に適しています。 Java では、効率を高めるために、多数の配列要素をコピーする場合にこのメソッドを使用することを強くお勧めします。

静的配列に変換される ArrayList の 2 つの toArray メソッドに注目してください。

最初の Object[] toArray() メソッド。このメソッドは、下方変換メソッドを直接使用して ArrayList コレクション全体を指定された型の Array 配列に変換する場合、java.lang.ClassCastException 例外をスローすることがあります。 Array 配列をダウンキャストしても、各要素をダウンキャストしても、この例外はスローされません。明らかに、配列内の要素を 1 つずつダウンキャストするのは効率的ではなく、不便です。

2 番目、 T[] toArray(T[] a) メソッド。このメソッドは、ArrayList から変換された Array をそのまま全体として下方向に変換することができます (実際に変換はこのメソッドのソースコード内で実装されています)。このメソッドのソースコードを見ると、パラメータ a のサイズが不足している場合に次のことがわかります。、内部的に Arrays.copyOf メソッドが呼び出されます。このメソッドは内部的に新しい配列を作成してそれを返すため、このメソッドの一般的な形式は次のとおりです:

public static Integer[] vectorToArray2(ArrayList<Integer> v) {  
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);  
    return newText;  
}

ログイン後にコピー

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

三、LinkedList

LinkedList的特点

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用；

LinkedList同样是非线程安全的，只在单线程下适合使用；

LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输；

实现了Cloneable接口，能被克隆；