Liste in Java: Eine kurze Einführung in die Implementierungsschnittstellen ArrayList und LinkedList

ArrayList wird basierend auf Arrays implementiert. Es handelt sich um ein dynamisches Array, dessen Kapazität automatisch wachsen kann, ähnlich wie bei der dynamischen Beantragung von Speicher und dem dynamisch wachsenden Speicher in der Sprache C. LinkedList basiert auf einer bidirektionalen zirkulären verknüpften Liste (was aus dem Quellcode leicht ersichtlich ist). Sie kann nicht nur als verknüpfte Liste betrieben werden, sondern auch als Stapel, Warteschlange und doppelendige Warteschlange.

1. Einführung in List

Eigenschaften von ArrayList

ArrayList wird

basierend auf Array implementiert

und ist ein Dynamisches Array, seine Kapazität kann automatisch wachsen, ähnlich der dynamischen Beantragung von Speicher und dem dynamisch wachsenden Speicher in der Sprache C. ArrayList ist

Thread-unsicher

kann nur in einer Single-Thread-Umgebung verwendet werden. In einer Multi-Thread-Umgebung können Sie die Verwendung von Collections.synchronizedList in Betracht ziehen (Listenliste) Funktion zum Zurückgeben Eine threadsichere ArrayList-Klasse. Sie können auch die CopyOnWriteArrayList-Klasse unter dem gleichzeitigen Paket verwenden. ArrayList implementiert die Serializable-Schnittstelle, unterstützt also die Serialisierung, kann durch Serialisierung übertragen werden

ArrayList implementiert die RandomAccess-Schnittstelle und unterstützt schnellen Direktzugriff, was eigentlich Schneller Zugriff durch Subskription der Seriennummer

implementiert die klonbare Schnittstelle, kann geklont werden

Beachten Sie die drei verschiedenen Konstruktionsmethoden. Die Kapazität der vom Parameterlosen Konstruktor erstellten ArrayList beträgt standardmäßig 10. Der Konstruktor mit Sammlungsparametern konvertiert die Sammlung in ein Array und weist sie dem ArrayList-Implementierungsarray elementData zu. Es gibt auch einen Konstruktor, der die Kapazität angibt. Achten Sie auf die Methode zur Kapazitätserweiterung und stellen Sie die Kapazität sicher. Jedes Mal, wenn ein Element zu ArrayList hinzugefügt wird (es kann 1 oder eine Gruppe sein), muss diese Methode aufgerufen werden, um eine ausreichende Kapazität sicherzustellen. Wenn die Kapazität nicht ausreicht, um die aktuelle Anzahl von Elementen aufzunehmen, wird die neue Kapazität auf das 1,5-fache der alten Kapazität plus 1 gesetzt. Wenn die eingestellte neue Kapazität nicht ausreicht, wird die neue Kapazität direkt auf den übergebenen Parameter (das) gesetzt ist die erforderliche Kapazität) und verwenden Sie dann die Methode Arrays.copyof(), um die Elemente in ein neues Array zu kopieren (Einzelheiten siehe Punkt 3 unten). Daraus ist ersichtlich, dass, wenn die Kapazität nicht ausreicht, jedes Mal, wenn ein Element hinzugefügt wird, die ursprünglichen Elemente in ein neues Array kopiert werden müssen, was sehr zeitaufwändig ist. Daher wird empfohlen, ArrayList nur zu verwenden Die Anzahl der Elemente kann im Voraus bestimmt werden, ansonsten wird die Verwendung von LinkedList empfohlen.

Die Implementierung von ArrayList ruft eine große Anzahl der Methoden Arrays.copyof() und System.arraycopy() auf. Für uns ist ein tiefgreifendes Verständnis der Umsetzung dieser beiden Methoden erforderlich.

Schauen wir uns zunächst die Methode Arrays.copyof() an. Es gibt viele überladene Methoden, aber die Implementierungsideen sind die gleichen. Schauen wir uns den Quellcode der generischen Version an:

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

Offensichtlich wird eine andere copyof-Methode aufgerufen, die drei Parameter hat. Der letzte Parameter gibt an Der zu konvertierende Datentyp lautet wie folgt:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

Es ist deutlich zu erkennen, dass diese Methode tatsächlich ein Array mit der Länge newlength erstellt und die Methode System.arraycopy() aufruft die Elemente im ursprünglichen Array in das neue Array.

Schauen wir uns die Methode System.arraycopy() an. Diese Methode ist als nativ gekennzeichnet und ruft den C/C++-Code des Systems auf. Er ist im JDK nicht sichtbar, sein Quellcode ist jedoch im openJDK sichtbar. Diese Funktion ruft letztendlich die memmove()-Funktion der C-Sprache auf, sodass sie das korrekte Kopieren und Verschieben von Elementen im selben Array sicherstellen kann. Sie ist viel effizienter als die allgemeine Kopiermethode und eignet sich sehr gut für die Stapelverarbeitung von Arrays. Java empfiehlt dringend, diese Methode beim Kopieren einer großen Anzahl von Array-Elementen zu verwenden, um eine höhere Effizienz zu erzielen.

Achten Sie auf die beiden toArray-Methoden von ArrayList, die in statische Arrays konvertiert werden.

Die erste, Object[] toArray()-Methode. Diese Methode löst möglicherweise eine java.lang.ClassCastException-Ausnahme aus, wenn Sie die gesamte ArrayList-Sammlung direkt in ein Array-Array des angegebenen Typs konvertieren. Wenn Sie sie jedoch nicht konvertieren Ein Array-Array, Downcasting, aber das Downcasting jedes Elements löst diese Ausnahme nicht aus. Offensichtlich ist das Downcasting der Elemente im Array einzeln nicht effizient und unpraktisch.

Zweitens T[] toArray(T[] a) Methode. Diese Methode kann das von ArrayList konvertierte Array als Ganzes direkt nach unten transformieren (die Transformation ist tatsächlich im Quellcode dieser Methode implementiert), und aus dem Quellcode dieser Methode ist ersichtlich, dass die Größe des Parameters a nicht ausreicht , wird intern die Methode Arrays.copyOf aufgerufen. Diese Methode erstellt intern ein neues Array und gibt es zurück. Die übliche Form dieser Methode lautet also wie folgt:

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接口，能被克隆；

相关推荐：

接口测试基础之入门篇

视频教程：

去除ArrayList集合中的重复自定义对象元素案例

Das obige ist der detaillierte Inhalt vonListe in Java: Eine kurze Einführung in die Implementierungsschnittstellen ArrayList und LinkedList. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!