webentwicklung-frage-antwort-db.com.de

Array versus verknüpfte Liste

Warum sollte jemand eine verknüpfte Liste über einem Array verwenden wollen?

Das Codieren einer verknüpften Liste ist zweifellos ein bisschen aufwändiger als die Verwendung eines Arrays, und man mag sich fragen, was den zusätzlichen Aufwand rechtfertigen würde.

Ich denke, das Einfügen neuer Elemente in eine verknüpfte Liste ist trivial, aber es ist eine große Aufgabe in einem Array. Gibt es andere Vorteile bei der Verwendung einer verknüpften Liste zum Speichern eines Datensatzes im Vergleich zum Speichern in einem Array?

Diese Frage ist kein Duplikat von diese Frage , da die andere Frage speziell nach einer bestimmten Java Klasse) fragt, während sich diese Frage mit den allgemeinen Datenstrukturen befasst.

190
  • Es ist einfacher, Daten unterschiedlicher Größe in einer verknüpften Liste zu speichern. Ein Array setzt voraus, dass jedes Element genau die gleiche Größe hat.
  • Wie Sie bereits erwähnt haben, ist es für eine verknüpfte Liste einfacher, organisch zu wachsen. Die Größe eines Arrays muss im Voraus bekannt sein oder neu erstellt werden, wenn es größer werden soll.
  • Das Mischen einer verknüpften Liste ist nur eine Frage der Änderung, was auf was zeigt. Das Mischen eines Arrays ist komplizierter und/oder benötigt mehr Speicher.
  • Solange Ihre Iterationen alle in einem "foreach" -Kontext stattfinden, verlieren Sie keine Leistung bei der Iteration.
145
Ryan

Ein weiterer guter Grund ist, dass verknüpfte Listen sich gut für effiziente Multi-Thread-Implementierungen eignen. Der Grund dafür ist, dass Änderungen in der Regel lokal sind und nur einen oder zwei Zeiger zum Einfügen und Entfernen in einem lokalisierten Teil der Datenstruktur betreffen. Es können also viele Threads an derselben verknüpften Liste arbeiten. Darüber hinaus ist es möglich, mit CAS-Operationen schlossfreie Versionen zu erstellen und schwergewichtige Schlösser zu vermeiden.

Mit einer verknüpften Liste können Iteratoren die Liste auch durchlaufen, während Änderungen vorgenommen werden. In dem optimistischen Fall, dass Änderungen nicht kollidieren, können Iteratoren ohne Konkurrenz fortfahren.

Bei einem Array ist es wahrscheinlich erforderlich, einen großen Teil des Arrays zu sperren, wenn Änderungen an der Größe des Arrays vorgenommen werden. In der Tat erfolgt dies selten ohne eine globale Sperre für das gesamte Array, sodass Änderungen die Welt verändern.

171
Alex Miller

Wikipedia hat einen sehr guten Abschnitt über die Unterschiede.

Verknüpfte Listen bieten gegenüber Arrays mehrere Vorteile. Elemente können auf unbestimmte Zeit in verknüpfte Listen eingefügt werden, während ein Array irgendwann gefüllt wird oder in der Größe geändert werden muss. Dies ist eine kostspielige Operation, die möglicherweise nicht möglich ist, wenn der Speicher fragmentiert ist. In ähnlicher Weise kann ein Array, aus dem viele Elemente entfernt wurden, verschwenderisch leer werden oder muss verkleinert werden.

Auf der anderen Seite erlauben Arrays den wahlfreien Zugriff, während verknüpfte Listen nur den sequentiellen Zugriff auf Elemente erlauben. Einfach verknüpfte Listen können nur in eine Richtung durchlaufen werden. Dies macht verknüpfte Listen für Anwendungen ungeeignet, bei denen es nützlich ist, ein Element schnell anhand seines Index nachzuschlagen, z. B. Heapsort. Der sequenzielle Zugriff auf Arrays ist auf vielen Computern aufgrund der Verweislokalität und der Datencaches auch schneller als bei verknüpften Listen. Verknüpfte Listen erhalten fast keinen Nutzen aus dem Cache.

Ein weiterer Nachteil von verknüpften Listen ist der zusätzliche Speicherbedarf für Verweise, der sie für Listen mit kleinen Datenelementen wie Zeichen oder Booleschen Werten oft unpraktisch macht. Es kann auch langsam und mit einem naiven Allokator verschwenderisch sein, Speicher für jedes neue Element separat zuzuweisen, ein Problem, das im Allgemeinen mit Speicherpools gelöst wird.

http://en.wikipedia.org/wiki/Linked_list

123
Jonas Klemming

Ich füge noch eine hinzu - Listen können als rein funktionale Datenstrukturen fungieren.

Beispielsweise können Sie völlig unterschiedliche Listen haben, die denselben Endabschnitt gemeinsam nutzen

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

d. h .:

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

ohne die Daten, auf die a zeigt, in b und c kopieren zu müssen.

Aus diesem Grund sind sie in funktionalen Sprachen, die unveränderliche Variablen verwenden, so beliebt. prepend- und tail -Operationen können frei ausgeführt werden, ohne dass die Originaldaten kopiert werden müssen. Dies ist eine sehr wichtige Funktion bei der Datenverarbeitung als unveränderlich.

55
Brian

Das Zusammenführen von zwei verknüpften Listen (insbesondere von zwei doppelt verknüpften Listen) ist viel schneller als das Zusammenführen von zwei Arrays (vorausgesetzt, die Zusammenführung ist destruktiv). Ersteres nimmt O (1), letzteres nimmt O (n).

EDIT: Zur Verdeutlichung meinte ich hier "Zusammenführen" im ungeordneten Sinne, nicht wie bei der Zusammenführungssortierung. Vielleicht wäre "Verketten" ein besseres Wort gewesen.

28
rampion

Das Einfügen in die Mitte der Liste ist nicht nur einfacher - es ist auch viel einfacher, aus der Mitte einer verknüpften Liste zu löschen als aus einem Array.

Aber ehrlich gesagt habe ich noch nie eine verknüpfte Liste verwendet. Wann immer ich schnelles Einfügen und Löschen brauchte, brauchte ich auch eine schnelle Suche, also ging ich zu einem HashSet oder einem Dictionary.

28
Tom Ritter

Erstens sollte es in C++ für verknüpfte Listen nicht viel schwieriger sein, mit ihnen zu arbeiten als mit einem Array. Sie können die std :: list oder die boost pointer list für verknüpfte Listen verwenden. Die Hauptprobleme bei verknüpften Listen im Vergleich zu Arrays sind der zusätzliche Platzbedarf für Zeiger und der schreckliche wahllose Zugriff. Sie sollten eine verknüpfte Liste verwenden, wenn Sie

  • sie benötigen keinen wahlfreien Zugriff auf die Daten
  • sie werden Elemente hinzufügen/löschen, insbesondere in der Mitte der Liste
17
David Nehme

Ein weithin unbeachtetes Argument für ArrayList und gegen LinkedList ist LinkedLists sind beim Debuggen unangenehm. Die Zeit, die Wartungsentwickler für das Verständnis des Programms aufwenden, z. Fehler zu finden, erhöht und IMHO rechtfertigt manchmal nicht die Nanosekunden in Leistungsverbesserungen oder Bytes im Speicherverbrauch in Unternehmensanwendungen. Manchmal (naja, natürlich hängt es von der Art der Anwendungen ab) ist es besser, ein paar Bytes zu verschwenden, aber eine Anwendung zu haben, die leichter zu warten oder zu verstehen ist.

In einer Java Umgebung und unter Verwendung des Eclipse-Debuggers zeigt das Debuggen einer ArrayList beispielsweise eine sehr leicht verständliche Struktur:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

Auf der anderen Seite wird das Beobachten des Inhalts einer LinkedList und das Auffinden bestimmter Objekte zu einem klickenden Albtraum, ganz zu schweigen von dem kognitiven Aufwand, der zum Herausfiltern der LinkedList-Interna erforderlich ist:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>
17
mhaller

Für mich ist es so,

  1. Zugriff

    • Verknüpfte Listen Erlaubt nur den sequentiellen Zugriff auf Elemente. Somit ist die algorithmische Komplexität in der Größenordnung von O (n)
    • Arrays erlaubt zufälligen Zugriff auf seine Elemente und somit ist die Komplexität in der Größenordnung von O (1)
  2. Lager

    • Verknüpfte Listen benötigen einen zusätzlichen Speicher für Referenzen. Dies macht sie für Listen kleiner Datenelemente wie Zeichen oder Boolesche Werte unpraktisch.
    • Arrays benötigen keinen zusätzlichen Speicher, um auf das nächste Datenelement zu verweisen. Auf jedes Element kann über Indizes zugegriffen werden.
  3. Größe

    • Die Größe von verknüpfte Listen ist von Natur aus dynamisch.
    • Die Größe von Array ist auf die Deklaration beschränkt.
  4. Einfügen/Löschen

    • Elemente können in verknüpfte Listen auf unbestimmte Zeit eingefügt und gelöscht werden.
    • Das Einfügen/Löschen von Werten in Arrays ist sehr teuer. Es erfordert eine Neuzuweisung des Speichers.
14
Sulman

Zwei Dinge:

Das Codieren einer verknüpften Liste ist zweifellos etwas aufwendiger als die Verwendung eines Arrays, und er fragte sich, was den zusätzlichen Aufwand rechtfertigen würde.

Codieren Sie niemals eine verknüpfte Liste, wenn Sie C++ verwenden. Verwenden Sie einfach die STL. Wie schwierig die Implementierung ist, sollte niemals ein Grund sein, eine Datenstruktur einer anderen vorzuziehen, da die meisten bereits implementiert sind.

Was die tatsächlichen Unterschiede zwischen einem Array und einer verknüpften Liste betrifft, ist für mich das Wichtigste, wie Sie die Struktur verwenden möchten. Ich werde den Begriff Vektor verwenden, da dies der Begriff für ein in der Größe veränderbares Array in C++ ist.

Das Indizieren in eine verknüpfte Liste ist langsam, da Sie die Liste durchlaufen müssen, um zum angegebenen Index zu gelangen, während ein Vektor im Speicher zusammenhängend ist und Sie mithilfe der Zeigermathematik dorthin gelangen können.

Das Anhängen an das Ende oder den Anfang einer verknüpften Liste ist einfach, da Sie nur einen Link aktualisieren müssen. In einem Vektor müssen Sie möglicherweise die Größe ändern und den Inhalt kopieren.

Das Entfernen eines Elements aus einer Liste ist einfach, da Sie nur zwei Verknüpfungen trennen und sie dann wieder zusammenfügen müssen. Das Entfernen eines Elements von einem Vektor kann entweder schneller oder langsamer sein, je nachdem, ob Sie sich für die Reihenfolge interessieren. Das Vertauschen des letzten Elements über das zu entfernende Element ist schneller, während das Verschieben nach dem Herunterfahren langsamer ist, die Reihenfolge jedoch beibehalten wird.

11
bradtgmurray

Eric Lippert hatte kürzlich ein post zu einem der Gründe, warum Arrays konservativ verwendet werden sollten.

10
Rik

Schnelles Einfügen und Entfernen sind in der Tat die besten Argumente für verknüpfte Listen. Wenn Ihre Struktur dynamisch wächst und der Zugriff auf ein Element mit konstanter Zeit nicht erforderlich ist (z. B. dynamische Stapel und Warteschlangen), sind verknüpfte Listen eine gute Wahl.

8
Firas Assaad

Abgesehen vom Hinzufügen und Entfernen aus der Mitte der Liste mag ich verknüpfte Listen eher, da sie dynamisch wachsen und schrumpfen können.

7
Vasil

Linked-List sind besonders nützlich, wenn die Sammlung ständig wächst und schrumpft. Es ist beispielsweise schwer vorstellbar, eine Warteschlange mithilfe eines Arrays zu implementieren (am Ende hinzufügen, von vorne entfernen) - Sie würden Ihre ganze Zeit damit verbringen, Dinge nach unten zu verschieben. Auf der anderen Seite ist es mit einer verknüpften Liste trivial.

7
James Curran

Niemand verschlüsselt mehr seine eigene verknüpfte Liste. Das wäre albern. Die Annahme, dass die Verwendung einer verknüpften Liste mehr Code erfordert, ist einfach falsch.

Heutzutage ist das Erstellen einer verknüpften Liste nur eine Übung für Schüler, damit sie das Konzept verstehen können. Stattdessen verwendet jeder eine vorgefertigte Liste. In C++, basierend auf der Beschreibung in unserer Frage, würde das wahrscheinlich einen stl-Vektor bedeuten (#include <vector>).

Wenn Sie also eine verknüpfte Liste oder ein Array auswählen, müssen Sie vollständig die verschiedenen Merkmale jeder Struktur im Verhältnis zu den Anforderungen Ihrer App abwägen. Die Überwindung des zusätzlichen Programmaufwands sollte sich nicht auf die Entscheidung auswirken.

7
Joel Coehoorn

Hier ist eine kurze Beschreibung: Das Entfernen von Elementen erfolgt schneller.

7
itsmatt

Es ist wirklich eine Frage der Effizienz, der Aufwand zum Einfügen, Entfernen oder Verschieben (wo Sie nicht einfach tauschen) von Elementen in einer verknüpften Liste ist minimal, dh die Operation selbst ist O (1), verses O(n) für ein Array. Dies kann einen signifikanten Unterschied bedeuten, wenn Sie stark mit einer Liste von Daten arbeiten. Sie haben Ihre Datentypen basierend darauf ausgewählt, wie Sie mit ihnen arbeiten werden, und den effizientesten für den Algorithmus ausgewählt, den Sie verwenden benutzen.

6
Steve Baker

Arrays sind sinnvoll, wenn die genaue Anzahl der Elemente bekannt ist und die Suche nach Index sinnvoll ist. Wenn ich zum Beispiel den genauen Status meiner Videoausgabe zu einem bestimmten Zeitpunkt ohne Komprimierung speichern möchte, würde ich wahrscheinlich ein Array mit der Größe [1024] [768] verwenden. Dies liefert mir genau das, was ich brauche, und eine Liste würde viel langsamer sein, um den Wert eines gegebenen Pixels zu erhalten. An Orten, an denen ein Array keinen Sinn ergibt, gibt es im Allgemeinen bessere Datentypen als eine Liste, um effektiv mit Daten umzugehen.

6
tloach

Arrays gegen verknüpfte Liste:

  1. Die Zuweisung des Array-Speichers schlägt manchmal aufgrund eines fragmentierten Speichers fehl.
  2. Das Cachen ist in Arrays besser, da allen Elementen zusammenhängender Speicherplatz zugewiesen wird.
  3. Die Codierung ist komplexer als Arrays.
  4. Keine Größenbeschränkung für verknüpfte Listen im Gegensatz zu Arrays
  5. Das Einfügen/Löschen ist in verknüpften Listen schneller und der Zugriff in Arrays schneller.
  6. Verknüpfte Liste aus Multithreading-Sicht besser.
6
AKS

Bei verknüpften Listen ist der Aufwand höher als bei Arrays. Außerdem ist zusätzlicher Speicher erforderlich. Alle diese Punkte sind vereinbart. Aber es gibt ein paar Dinge, die Array nicht tun kann. Nehmen wir in vielen Fällen an, Sie möchten ein Array mit einer Länge von 10 ^ 9, das Sie nicht erhalten können, da ein zusammenhängender Speicherort vorhanden sein muss. Verknüpfte Liste könnte hier ein Retter sein.

Angenommen, Sie möchten mehrere Dinge mit Daten speichern, dann können diese einfach in der verknüpften Liste erweitert werden.

STL-Container haben normalerweise eine verknüpfte Listenimplementierung hinter den Kulissen.

3
iec2011007

In einem Array haben Sie das Privileg, auf jedes Element in O(1) Zeit zuzugreifen. Daher eignet es sich für Operationen wie die binäre Suche, die schnelle Sortierung usw. Verknüpfte Liste eignet sich dagegen zum Einfügen Das Löschen ist in O(1) Zeit. Beides hat Vor- und Nachteile, und das Vorziehen des einen gegenüber dem anderen läuft darauf hinaus, was Sie implementieren möchten.

- Die größere Frage ist, ob wir eine Mischung aus beidem haben können. Sowas wie was python und Perl als Listen implementieren.

3
pranjal

Angenommen, Sie haben eine geordnete Menge, die Sie auch durch Hinzufügen und Entfernen von Elementen ändern möchten. Außerdem müssen Sie in der Lage sein, einen Verweis auf ein Element so beizubehalten, dass Sie später ein vorheriges oder nächstes Element erhalten können. Zum Beispiel eine Aufgabenliste oder eine Gruppe von Absätzen in einem Buch.

Zunächst sollten wir beachten, dass Sie, wenn Sie Verweise auf Objekte außerhalb der Menge selbst beibehalten möchten, wahrscheinlich Zeiger im Array speichern, anstatt Objekte selbst zu speichern. Andernfalls können Sie keine Objekte in ein Array einfügen. Wenn Objekte in das Array eingebettet sind, werden sie während des Einfügens verschoben und alle Zeiger auf sie werden ungültig. Gleiches gilt für Array-Indizes.

Ihr erstes Problem ist, wie Sie selbst bemerkt haben, das Einfügen einer verknüpften Liste, die das Einfügen in O (1) ermöglicht, aber ein Array würde im Allgemeinen O (n) erfordern. Dieses Problem kann teilweise überwunden werden - es ist möglich, eine Datenstruktur zu erstellen, die eine Array-artige by-ordinal-Zugriffsschnittstelle bietet, bei der sowohl Lesen als auch Schreiben im schlimmsten Fall logarithmisch sind.

Ihr zweites und schwerwiegenderes Problem besteht darin, dass bei einem Element, das das nächste Element findet, O (n) ist. Wenn die Menge nicht geändert würde, könnten Sie den Index des Elements als Referenz anstelle des Zeigers beibehalten und so eine O(1) -Operation durchführen, aber wie es ist alles, was Sie haben, ist Ein Zeiger auf das Objekt selbst und keine Möglichkeit, seinen aktuellen Index im Array zu bestimmen, außer durch Scannen des gesamten "Arrays". Dies ist ein unüberwindbares Problem für Arrays - auch wenn Sie Einfügungen optimieren können, können Sie nichts tun, um sie zu optimieren find-next type operation.

3
DenNukem

Verknüpfte Liste

Es ist vorzuziehen, wenn es um das Einfügen geht! Grundsätzlich geht es darum, dass es sich um den Zeiger handelt

1 -> 3 -> 4

Einfügen (2)

1 ........ 3 ...... 4
..... 2

Endlich

1 -> 2 -> 3 -> 4

Ein Pfeil von den 2 Punkten bei 3 und der Pfeil von 1 Punkten bei 2

Einfach!

Aber von Array

| 1 | 3 | 4 |

Einfügen (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

Nun kann sich jeder den Unterschied vorstellen! Nur für 4 Indexe führen wir 3 Schritte durch

Was ist, wenn die Array-Länge dann eine Million beträgt? Ist das Array effizient? Die Antwort ist nein! :)

Das gleiche gilt für das Löschen! In der verknüpften Liste können wir einfach den Zeiger verwenden und das Element und das nächste in der Objektklasse aufheben! Aber für Array müssen wir shiftLeft () ausführen

Ich hoffe, das hilft! :)

3
Farah Nazifa

da Arrays statischer Natur sind, finden alle Operationen wie die Speicherzuweisung nur zum Zeitpunkt der Kompilierung statt. Der Prozessor muss also zur Laufzeit weniger Aufwand betreiben.

3
debayan

Der einzige Grund für die Verwendung der verknüpften Liste ist, dass das Einfügen des Elements einfach ist (auch das Entfernen).

Ein Nachteil könnte sein, dass Zeiger viel Platz in Anspruch nehmen.

Und darüber ist die Codierung schwieriger: Normalerweise benötigen Sie keine verknüpfte Codeliste (oder nur eine), die in STL enthalten ist, und es ist nicht so kompliziert, wenn du musst es noch tun.

2
user15453

Warum sollte jemand eine verknüpfte Liste über einem Array verwenden wollen?

Dies ist nur ein Grund - wenn Sie eine verknüpfte Listendatenstruktur benötigen und eine von Ihnen verwendete Programmiersprache keine Zeiger unterstützt.

1
Ans

ich denke auch, dass Link-Liste besser als Arrays ist. weil wir in Linklisten, aber nicht in Arrays arbeiten

1
iram Arshad

Neben der Bequemlichkeit beim Einfügen und Löschen unterscheidet sich die Speicherdarstellung der verknüpften Liste von den Arrays. Die Anzahl der Elemente in einer verknüpften Liste ist nicht beschränkt, während Sie in den Arrays die Gesamtanzahl der Elemente angeben müssen. Check this Artikel.

1
Sajjad Abdullah

Warum eine verknüpfte Liste über ein Array? Nun, wie einige bereits gesagt haben, höhere Geschwindigkeit von Einfügungen und Löschungen.

Aber vielleicht müssen wir nicht mit den Grenzen von beidem leben und gleichzeitig das Beste aus beiden herausholen ... wie?

Beim Löschen von Arrays können Sie ein "Gelöschtes" Byte verwenden, um die Tatsache darzustellen, dass eine Zeile gelöscht wurde. Ein erneutes Ordnen des Arrays ist daher nicht mehr erforderlich. Verwenden Sie dazu eine verknüpfte Liste, um das Einfügen oder das schnelle Ändern von Daten zu erleichtern. Wenn Sie sich dann auf sie beziehen, lassen Sie Ihre Logik zuerst eine und dann die andere suchen. Wenn Sie sie also in Kombination verwenden, erhalten Sie das Beste von beiden.

Wenn Sie ein wirklich großes Array haben, können Sie es mit einem anderen, viel kleineren Array oder einer verknüpften Liste kombinieren, in der das kleinere Array die 20, 50, 100 zuletzt verwendeten Elemente enthält. Wenn das benötigte nicht in der kürzeren verknüpften Liste oder dem Array enthalten ist, wechseln Sie zum großen Array. Wenn es dort gefunden wird, können Sie es der kleineren verknüpften Liste/dem Array hinzufügen, vorausgesetzt, dass die zuletzt verwendeten Elemente am häufigsten wiederverwendet werden (und ja, möglicherweise das zuletzt verwendete Element aus der Liste stoßen). Was in vielen Fällen zutrifft und ein Problem löste, das ich in einem Modul zur Prüfung von .ASP-Sicherheitsberechtigungen mit Leichtigkeit, Eleganz und beeindruckender Geschwindigkeit angehen musste.

1
Juan-Carlos

Während viele von Ihnen die wichtigsten Adv./Dis. Von Linked List vs Array angesprochen haben, sind die meisten Vergleiche so, wie einer besser/schlechter ist als der andere.Eg. Sie können einen Direktzugriff im Array ausführen, jedoch nicht in verknüpften Listen und anderen. Dies setzt jedoch voraus, dass Linklisten und Arrays in einer ähnlichen Anwendung angewendet werden. Eine richtige Antwort sollte jedoch sein, wie die Linkliste in einer bestimmten Anwendungsbereitstellung dem Array vorgezogen wird und umgekehrt. Angenommen, Sie möchten eine Wörterbuchanwendung implementieren. Was würden Sie verwenden? Array: mmm es würde ein einfaches Abrufen durch binäre Suche und andere Suchalgorithmen ermöglichen. Aber lassen Sie uns überlegen, wie die Linkliste besser sein kann. Sagen wir, Sie möchten "Blob" im Wörterbuch suchen. Wäre es sinnvoll, eine Linkliste von A-> B-> C-> D ----> Z zu haben und dann jedes Listenelement auch auf ein Array oder eine andere Liste aller Wörter zu verweisen, die mit diesem Buchstaben beginnen.

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

Ist nun der obige Ansatz besser oder eine flache Anordnung von [Adam, Apfel, Banane, Klecks, Katze, Höhle]? Wäre es überhaupt mit Array möglich? Ein wesentlicher Vorteil der Linkliste besteht darin, dass ein Element nicht nur auf das nächste Element, sondern auch auf eine andere Linkliste/Array/Heap/oder einen anderen Speicherort verweisen kann. Array ist ein flacher zusammenhängender Speicher, der in Blöcke der Größe des zu speichernden Elements aufgeteilt ist. Linkliste hingegen ist ein Block von nicht zusammenhängenden Speichereinheiten (kann eine beliebige Größe haben und alles speichern) und auf jedes Element zeigen anders wie du willst. Nehmen wir an, Sie erstellen ein USB-Laufwerk. Möchten Sie nun, dass Dateien als Array oder als Linkliste gespeichert werden? Ich denke, Sie haben die Idee, worauf ich hinweise :)

1
Vikalp Veer

Abhängig von Ihrer Sprache können einige dieser Nachteile und Vorteile berücksichtigt werden:

C Programming Language: Wenn Sie eine verknüpfte Liste verwenden (normalerweise über Strukturzeiger), müssen Sie besonders darauf achten, dass Sie keinen Speicher verlieren. Wie bereits erwähnt, lassen sich verknüpfte Listen leicht mischen, da lediglich die Zeiger geändert wurden. Werden wir uns jedoch daran erinnern, alles freizugeben?

Java: Java hat eine automatische Garbage-Collect-Funktion, so dass Speicherverluste kein Problem darstellen, aber für den Programmierer auf hoher Ebene sind die Implementierungsdetails der verknüpften Elemente verborgen list is. Methoden wie das Entfernen eines Knotens aus der Mitte der Liste sind komplizierter als manche Benutzer der Sprache es erwarten würden.

1
SetSlapShot

Der Unterschied zwischen einem Array und einer verknüpften Liste besteht darin, dass ein Array eine indexbasierte Datenstruktur ist. Jedes Element ist einem Index zugeordnet, während die verknüpfte Liste eine Datenstruktur ist, die Verweise verwendet. Jeder Knoten wird auf einen anderen Knoten verwiesen. In der Array-Größe ist festgelegt, während in der Link-Liste die Größe nicht festgelegt ist.

0
sagar

Personen, die eine Linkliste verwenden, müssen diese lesen. Die Leute werden sich wieder in Array verlieben. Es geht um Out-of-Order-Probleme, Hardware-Prefetch, Speicherlatenz usw.

http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html

0
Ashkrit Sharma