Was ist der Unterschied zwischen der internen Arbeit der doppelt verknüpften Liste von LinkedList und ArrayList in Java

Question

Manipulation mit LinkedList ist schneller als ArrayList, weil es doppelt verknüpfte Liste verwendet, so dass keine Bitverschiebung im Speicher erforderlich ist. Aber im Falle von ArrayList, wenn ein Element aus dem Array entfernt wird, werden alle Bits im Speicher verschoben.

Also, was ist der interne Mechanismus, mit dem LinkedList diesen Vorteil für Datenmanipulation erreichen?

Answer 1

Ein ArrayList verwendet ein Array zum Speichern der Elemente. So könnte ein Array 4 Elemente wie diese

[1][2][3][4] 

und das dritte Element entfernen lassen würde

[1][2][empty][4] 

was bedeutet, dass der Programmierer haben würde manuell, um die Elemente zu bewegen zu bekommen

[1][2][4] 

Die verkettete Liste verwendet jedoch Zeiger, so dass im obigen Beispiel der zweite Knoten (der mit dem Wert 2) nur so aktualisiert werden kann, dass er auf den Knoten zeigt, der 4 speichert.