Arrays speichern Elemente an zusammenhängenden Speicherplätzen, was zu leicht berechenbaren Adressen für die gespeicherten Elemente führt und einen schnelleren Zugriff auf ein Element bei einem bestimmten Index ermöglicht. Verknüpfte Listen sind in ihrer Speicherstruktur weniger starr, und die Elemente werden in der Regel nicht an zusammenhängenden Stellen gespeichert, weshalb sie mit zusätzlichen Tags gespeichert werden müssen, die einen Verweis auf das nächste Element enthalten. Dieser Unterschied im Datenspeicherschema entscheidet darüber, welche Datenstruktur für eine bestimmte Situation besser geeignet ist.

Datenspeicherschema eines Arrays

Datenspeicherschema einer verketteten Liste

Die wichtigsten Unterschiede sind im Folgenden aufgeführt:

• Größe: Da Daten in einem Array nur in zusammenhängenden Speicherblöcken gespeichert werden können, kann ihre Größe zur Laufzeit nicht geändert werden, da die Gefahr besteht, dass andere Daten überschrieben werden. In einer verknüpften Liste verweist jedoch jeder Knoten auf den nächsten, so dass Daten an verstreuten (nicht zusammenhängenden) Adressen existieren können; dies ermöglicht eine dynamische Größe, die sich zur Laufzeit ändern kann.
• Speicherzuweisung: Für Arrays zur Kompilierzeit und zur Laufzeit für verknüpfte Listen.
• Speichereffizienz: Bei gleicher Anzahl von Elementen verbrauchen verkettete Listen mehr Speicher, da zusammen mit den Daten auch ein Verweis auf den nächsten Knoten gespeichert wird. Allerdings kann die Größenflexibilität in verknüpften Listen dazu führen, dass sie insgesamt weniger Speicher verbrauchen; dies ist nützlich, wenn Unsicherheit über die Größe besteht oder die Größe der Datenelemente stark schwankt; bei der Verwendung von Arrays muss Speicher in Höhe der Obergrenze der Größe zugewiesen werden (auch wenn nicht alles davon verwendet wird), während verknüpfte Listen ihre Größe schrittweise proportional zur Datenmenge erhöhen können.
• Ausführungszeit: Auf jedes Element in einem Array kann direkt mit seinem Index zugegriffen werden; im Falle einer verknüpften Liste müssen jedoch alle vorherigen Elemente durchlaufen werden, um ein beliebiges Element zu erreichen. Außerdem kann die bessere Cache-Lokalität in Arrays (aufgrund der Zuweisung von zusammenhängendem Speicher) die Leistung erheblich verbessern. Infolgedessen sind einige Operationen (wie die Änderung eines bestimmten Elements) in Arrays schneller, während andere (wie das Einfügen/Löschen eines Elements in den Daten) in verknüpften Listen schneller sind.

Nachfolgend die Punkte, die für Linked Lists sprechen.
(1) Die Größe der Arrays ist fest: Wir müssen also die Obergrenze der Anzahl der Elemente im Voraus kennen. Außerdem ist der zugewiesene Speicher im Allgemeinen gleich der Obergrenze, unabhängig von der Verwendung, und in der Praxis wird die Obergrenze selten erreicht.

(2) Das Einfügen eines neuen Elements in ein Array von Elementen ist kostspielig, weil für die neuen Elemente ein Platz geschaffen werden muss und zur Schaffung von Platz vorhandene Elemente verschoben werden müssen.

Angenommen, wir führen eine sortierte Liste von IDs in einem Array id.

id = .

Und wenn wir eine neue ID 1005 einfügen wollen, dann müssen wir, um die sortierte Reihenfolge beizubehalten, alle Elemente nach 1000 (außer 1000) verschieben.

Löschen ist bei Arrays ebenfalls teuer, es sei denn, es werden spezielle Techniken verwendet. Um zum Beispiel 1010 in id zu löschen, muss alles nach 1010 verschoben werden.

Verknüpfte Listen bieten also die folgenden zwei Vorteile gegenüber Arrays
1) Dynamische Größe
2) Einfaches Einfügen/Löschen

Verknüpfte Listen haben folgende Nachteile:
1) Zufälliger Zugriff ist nicht erlaubt. Wir müssen auf die Elemente sequentiell zugreifen, beginnend mit dem ersten Knoten. Wir können also keine binäre Suche mit verknüpften Listen durchführen.
2) Für jedes Element der Liste wird zusätzlicher Speicherplatz für einen Zeiger benötigt.
3) Arrays haben eine bessere Cache-Lokalität, die einen ziemlich großen Unterschied in der Leistung machen kann.