Eine Frage, die in fast allen Java-Interviews gestellt wird: Sprechen Sie über den Unterschied zwischen ArrayList und LinkedList

Vorwort

Hallo zusammen, ich bin dein alter Freund Qing Ge. Ich weiß, dass du mich vermisst, also bin ich wieder hier?

Die Datenstruktur von Java steht im Mittelpunkt des Interviews Sie haben an Java teilgenommen. Ich glaube, alle Studenten, die das Interview geführt haben, haben dies erlebt. Wenn Interviewer solche Fragen stellen, möchten sie oft überprüfen, ob Sie die zugrunde liegenden Strukturen häufig verwendeter Datentypen in Java studiert haben, anstatt einfach auf der Ebene des „Wissens, wie man sie verwendet“ zu bleiben. Wie beantworten wir diese Frage im Vorstellungsgespräch gut und stellen den Interviewer zufrieden?

In dieser Ausgabe werde ich mich auf Java-Hochfrequenztestpunkte konzentrierenAnalysieren Sie die Prinzipien von ArrayList und LinkedList, ich hoffe, es kann Ihnen helfen. ArrayList和LinkedList的原理进行分析，希望能帮助到你。

ArrayList和LinkedList简介

ArrayList底层是一个Object类型的数组，初始容量是10，支持动态扩容，扩容后的容量是当前容量的1.5倍，它的最大容量是 Integer.MAX_VALUE - 8（但是仍可以扩容到Integer.MAX_VALUE），对于空出的8位，目前的解释是避免一些机器内存溢出，减少出错几率。

LinkedList

Einführung in ArrayList und LinkedList

🎜 🎜🎜

LinkedListDie unterste Ebene ist eine doppelt verknüpfte Liste. Die anfängliche Kapazität beträgt 0. Bis Erweitern Sie die Kapazität, erstellen Sie einfach eine neue. Zeigen Sie einfach mit dem Knoten auf den Zeiger. 🎜🎜🎜Um es in einer verbal ausdrückbaren Sprache zu vereinfachen und es den Schülern zu erleichtern, es dem Interviewer während des Interviews zu erklären, werde ich hier keine Hilfsanweisungen für den Quellcode veröffentlichen. Interessierte Schüler können den Quellcode überprüfen, um die interne Struktur und Methode zu sehen. Vertiefen Sie Ihr Verständnis für diesen Bereich. 🎜

Difference

Query

• ArrayList ist beim Direktzugriff sehr effizient, da die Speicherung von Elementen geordnet ist und der Speicherort der abgefragten Daten im Speicher über den Index ermittelt werden kann Index. Die Adresse ist schnell und die Zeitkomplexität beträgt O(1). N).
• Insertion

ArrayList ist bei der Endeinfügung effizienter, mit einer zeitlichen Komplexität von O(1), aber die Einfügungseffizienz an anderen Stellen ist relativ gering und erfordert eine große Menge an Datenbewegungen mit einer Zeit Komplexität von O(n);

• LinkedList ist beim Einfügen von Elementen am Kopf und am Ende effizienter und die Zeitkomplexität beträgt O(1). Zuerst muss die Position des Elements durchquert und dann eingefügt werden, was komplex ist.
• Delete

Das Entfernen von Elementen aus ArrayList erfordert eine große Datenbewegung, mit Ausnahme des Endknotens, und die Zeitkomplexität beträgt O(n);

• LinkedList ist beim Löschen von Elementen relativ effizient Es muss nur die Ausrichtung des Zeigers geändert werden, aber das Löschen von Elementen erfordert das Durchlaufen und Abfragen der Position der Daten mit einer zeitlichen Komplexität von O(n).
• Speicherplatz

ArrayList wird basierend auf Arrays implementiert. Die Kapazität wird nach jeder Erweiterung festgelegt, sodass am Ende ein Teil des Speicherplatzes reserviert wird Verknüpfte Listen, also jeder Knoten Zusätzlich zum Speichern der Daten müssen Sie auch die Zeiger des vorherigen und nächsten Knotens speichern, was etwas Platz beansprucht.

• Erweiterungsmechanismus
ArrayList muss die Elemente des ursprünglichen Arrays bei jeder Erweiterung in ein neues Array kopieren;

LinkedList ist eine verknüpfte Liste und es gibt keine Erweiterung.

• Gleichheit

Thread-Sicherheit

ArrayList und LinkedList sind beide Thread-unsicher und können in Multithread-Umgebungen leicht zu schmutzigen Leseproblemen führen. Sie können die Collections.synchronizedList()-Methode verwenden, um die Thread-Sicherheit sicherzustellen.

Speicherfunktionen

Die gespeicherten Elemente sind alle geordnet wiederholt, und neue Elemente werden am Ende der Liste gespeichert.

Das obige ist der detaillierte Inhalt vonEine Frage, die in fast allen Java-Interviews gestellt wird: Sprechen Sie über den Unterschied zwischen ArrayList und LinkedList. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!