Array versus verknüpfte Liste

Ein weiterer guter Grund ist, verknüpfte Listen eignen sich gut, um eine effiziente multi-Thread-Implementierungen. Der Grund dafür ist, dass die Veränderungen tendenziell lokale, die nur einen Zeiger oder zwei, die für das einfügen und entfernen in einer lokalisierten Teil der Datenstruktur. So können Sie viele threads arbeiten auf der gleichen verlinkten Liste. Mehr noch, es ist möglich zu erstellen-lock-freien Versionen mit CAS-Typ-Operationen und vermeiden, schwere Schlösser insgesamt.

Mit einer verknüpften Liste Iteratoren können auch Durchlaufen Sie die Liste, während änderungen auftreten. Im optimistischen Fall, in dem änderungen nicht kollidieren, Iteratoren können weiterhin ohne Streit.

Mit einem array, dass jede änderung, ändert die Größe des Arrays wird wahrscheinlich erfordern eine Verriegelung, die einen großen Teil des Arrays, und in der Tat, es ist selten, dass dies geschieht, ohne dass eine Globale Sperre über das ganze array, so dass änderungen werden aufhören, die Welt Angelegenheiten.

InformationsquelleAutor der Antwort Alex Miller

Werde ich weitere hinzufügen - Listen können als rein funktional Datenstrukturen.

Können Sie zum Beispiel komplett unterschiedliche Listen, die dieselben end-Abschnitt

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 kopieren der Daten wird darauf durch a in b und c.

Dies ist der Grund, warum Sie so beliebt sind in funktionalen Sprachen, die unveränderliche Variablen - prepend und tail Operationen auftreten können frei ohne kopieren der original-Daten - sehr wichtige Funktionen, wenn Sie die Behandlung von Daten als unveränderlich.

InformationsquelleAutor der Antwort Brian

Neben dem einfügen in die Mitte der Liste wird einfacher - es ist auch viel einfacher zu entfernen aus der Mitte einer verknüpften Liste als ein array.

Aber ehrlich gesagt, ich habe noch nie verwendet eine verknüpfte Liste. Wann immer ich brauchte, das schnelle einfügen und löschen, außerdem musste ich schnell nachschlagen, ich ging also in ein HashSet oder ein Wörterbuch.

InformationsquelleAutor der Antwort Tom Ritter

Einem weithin unbeachtet argument für ArrayList und gegen LinkedList ist, dass LinkedLists sind unangenehm beim Debuggen. Der Zeitaufwand für Wartungs-Entwickler, um das Programm zu verstehen, z.B. um Fehler zu finden, erhöht und IMHO macht manchmal nicht rechtfertigen, die in Nanosekunden performance-Verbesserungen oder bytes im Speicher den Verbrauch in Unternehmen applicatons. Manchmal (na gut, es kommt natürlich auf die Art der Anwendungen), ist es besser, zu verschwenden ein paar Byte, sondern haben eine Anwendung, die mehr wartbar und einfacher zu verstehen.

Beispielsweise in einer Java-Umgebung und mit dem Eclipse-debugger, der das Debuggen einer ArrayList wird zeigen, eine 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, beobachtete den Inhalt einer LinkedList und die Suche nach bestimmten Objekten wird die Erweitern-Den-Baum-Klick Alptraum, nicht zu schweigen von den kognitiven Aufwand benötigt, um filter aus der LinkedList Innenteile:

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>

InformationsquelleAutor der Antwort

Zwei Dinge:

Codierung einer verknüpften Liste ist, kein Zweifel, ein bisschen mehr Arbeit, als ein array verwenden, und er fragte sich, was rechtfertigen würde den zusätzlichen Aufwand.

Nie code einer verlinkten Liste bei der Verwendung von C++. Verwenden Sie einfach die STL. Wie schwer ist es umzusetzen, sollte nie ein Grund sein, wählen Sie eine Daten-Struktur über eine andere, denn die meisten sind bereits implementiert, die es gibt.

Als für die tatsächlichen Unterschiede zwischen einem array und eine verkettete Liste, die große Sache für mich ist, wie Sie planen, über die Verwendung der Struktur. Ich verwende den Begriff, Vektor, da der Begriff für ein in der Größe veränderbares array in C++.

Indizierung in einer verknüpften Liste ist langsam, da haben Sie zum Durchlaufen der Liste zu erhalten, die zu dem gegebenen index, während ein Vektor ist zusammenhängend im Speicher und man kann es mit Zeiger math.

Anfügen an das Ende oder den Anfang einer verketteten Liste, ist einfach, da Sie nur zu aktualisieren, einen link, wo sich in einem Vektor, die Sie haben können, um die Größe und kopieren Sie den Inhalt über.

Entfernen eines Elements aus einer Liste ist ganz einfach, denn Sie müssen nur zu brechen ein paar von links und dann bringen Sie Sie wieder zusammen. Entfernen eines Elements aus einem Vektor kann entweder schneller oder langsamer, je nachdem, ob Sie kümmern sich um Ordnung. Swapping in dem letzten Artikel über das Element, das Sie entfernen möchten, ist schneller beim schalten alles nach unten es ist langsamer, aber behält Bestellung.

InformationsquelleAutor der Antwort bradtgmurray

Schnelles einfügen und entfernen in der Tat sind die besten Argumente für die verknüpften Listen. Wenn die Struktur wächst dynamisch und die Konstante Zeit Zugang zu jedem element ist nicht erforderlich (wie z.B. dynamische stacks und queues), verknüpfte Listen sind eine gute Wahl.

InformationsquelleAutor der Antwort Firas Assaad

Verknüpften Listen sind besonders nützlich, wenn die Sammlung wächst ständig & verkleinern. Zum Beispiel, es ist schwer zu vorstellen versucht zu implementieren eine Queue (hinzufügen am Ende, entfernen Sie von der Vorderseite) mit einem array-Sie würde es sein, die Ausgaben alle Ihre Zeit verschieben sich die Dinge nach unten. Auf der anderen Seite ist es trivial mit einer verlinkten Liste.

InformationsquelleAutor der Antwort James Curran

Es ist wirklich eine Sache der Effizienz, der Aufwand zum einfügen, entfernen oder verschieben (wo Sie nicht einfach austauschen) - Elemente in einer verknüpften Liste ist minimal, D. H. die eigentliche operation ist O(1), Verse O(n) für ein array. Dies kann einen großen Unterschied machen, wenn Sie stark auf eine Liste von Daten. Sie wählten Ihre Daten-Typen, basierend auf, wie Sie die Bedienung auf Sie zu und wählen Sie die effizienteste für den Algorithmus, die Sie verwenden.

InformationsquelleAutor der Antwort Steve Baker

Arrays Vs. Verkettete Liste:

1. Array Speicher-Allokation Versagen manchmal, weil der Speicher fragmentiert.
2. Caching ist besser in Arrays alle Elemente werden zugewiesen, zusammenhängenden Speicherplatz.
3. Codierung komplexer ist, als Arrays.
4. Keine Größe-Einschränkung auf Verlinkten Liste, im Gegensatz zu Arrays
5. Einfügen/Löschen ist schneller in der Verlinkten Liste und der Zugriff ist schneller, Arrays.
6. Verkettete Liste besser aus multi-threading-Sicht.

InformationsquelleAutor der Antwort

Angenommen, Sie haben eine geordnete Menge, die Sie wollen auch zu ändern, indem Sie Elemente hinzufügen und entfernen. Weitere, Sie müssen die Möglichkeit behalten, eine Referenz auf ein element in einer Weise, dass Sie später bekommen können, einer vorherigen oder nächsten element. Zum Beispiel, eine to-do-Liste oder eine Reihe von Absätzen in einem Buch.

Zunächst sollten wir beachten, dass, wenn Sie wollen, behalten Sie Referenzen auf Objekte außerhalb des Satzes selbst, werden Sie wahrscheinlich am Ende speichern-Zeiger in das array, anstatt Speicherung der Objekte selbst. Andernfalls werden Sie nicht in der Lage das einfügen in ein array - wenn Objekte eingebettet sind in die Reihe der von Ihnen bewegen wird, während Insertionen und alle Zeiger auf Sie ungültig werden. Gleiches gilt für die array-Indizes.

Ihre erste problem, als Sie gemerkt haben, Sie sich, ist insertion - verknüpften Liste ermöglicht das einfügen in O(1), sondern ein array würde erfordern in der Regel O(n). Dieses problem kann teilweise zu überwinden - es ist möglich, erstellen Sie eine Daten-Struktur, die gibt array-like durch-Ordnungszahl-access-Schnittstelle, wo sowohl das Lesen und schreiben sind, im schlimmsten Fall, logarithmisch.

Ihre zweite und schwerwiegendere problem ist, dass, gegeben ein element finden, das nächste element ist O(n). Wenn das set wurde nicht geändert, Sie behalten den index des Elements als Referenz anstelle des Zeigers somit finden Sie-neben einem O(1) operation, aber es ist alles, was Sie haben, ist ein Zeiger auf das Objekt selbst und keine Möglichkeit zu bestimmen, Ihren aktuellen index in das array anders als durch die Erfassung der gesamten "array". Dies ist ein unüberwindliches problem für arrays - auch wenn Sie optimiert Insertionen, es gibt nichts, was Sie tun können, um zu optimieren, finden Sie-neben der Art der Bedienung.

InformationsquelleAutor der Antwort

Verlinkten Liste

Mehr vorzuziehen, wenn es darum geht über einfügen! Im Grunde, was es tut, ist, dass es befasst sich mit dem Zeiger

1 -> 3 -> 4

Einfügen (2)

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

.....2

Schließlich

1 -> 2 -> 3 -> 4

Einen Pfeil aus dem 2-Punkte auf 3 und die Pfeil-1 Punkte bei 2

Einfach!

Aber aus Array

| 1 | 3 | 4 |

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

Gut jeder kann visualisieren den Unterschied!
Nur für 4-index führen wir 3 Schritte

Was ist, wenn die array-Länge ist ein Millionen dann? Array effizient?
Die Antwort ist NEIN! 🙂

Das gleiche gilt für die Löschung!
In der Verlinkten Liste können wir einfach die Zeiger und bewirken das element und der nächste in der object-Klasse!
Aber der array, den wir brauchen, um shiftLeft()

Hoffe, das hilft! 🙂

InformationsquelleAutor der Antwort

Unterschied zwischen ArrayList und LinkedList

ArrayList und LinkedList beide implementiert List - Schnittstelle und pflegt die insertion um. Beide sind nicht synchronisiert Klassen.
Aber es gibt viele Unterschiede zwischen ArrayList und LinkedList Klassen, die unten gegeben.

ArrayList -

1. ArrayList intern verwendet dynamisches array zur Speicherung der Elemente.

2. Manipulation mit ArrayList ist langsam, da es intern verwendet, array.
   Wenn alle Elemente aus dem array entfernt, alle bits sind verschoben
   Speicher.

3. ArrayList Klasse kann als eine Liste, nur weil es
   implementiert List nur.
4. ArrayList ist besser für die Speicherung und
   Zugriff auf Daten.

LinkedList -

1. LinkedList intern verwendet doppelt verkettete Liste zum speichern der Elemente.

2. Manipulation mit LinkedList ist schneller als ArrayList weil es verwendet doppelt verkettete Liste, so dass keine bit-shifting erforderlich ist, im Speicher.

3. LinkedList Klasse kann als Liste und Warteschlange weil es implementiert List und Deque-Schnittstellen.

4. LinkedList ist besser für die Manipulation von Daten.

InformationsquelleAutor der Antwort

ich denke auch, dass die link-Liste ist besser als arrays.
da wir durchqueren in der link-Liste, aber nicht in arrays

InformationsquelleAutor der Antwort

Je auf Ihre Sprache, einige dieser Nachteile und Vorteile können in Betracht gezogen werden:

Programmierung in C: Wenn Sie eine verlinkte Liste (durch struct-Pointer in der Regel) Besondere Beachtung muss darauf geachtet werden, dass Sie nicht undicht Speicher. Wie zuvor erwähnt wurde, verknüpfte Listen sind einfach zu mischen, weil alle Taten, ist ändern der Zeiger, aber werden wir uns zu erinnern, um Kostenlose alles?

Java: Java hat eine automatische garbage sammeln, so undicht Speicher kein Problem sein, aber versteckt von der high-level-Programmierer ist die Implementierung details von dem, was eine verkettete Liste ist. Methoden wie das entfernen eines Knotens aus der Mitte der Liste ist komplizierter ein Verfahren, als die einige Benutzer der Sprache es erwarten würde.

InformationsquelleAutor der Antwort

Während viele von Euch berührt haben, die auf großen adv./dis der verlinkten Liste vs. array, die meisten sind die Vergleiche, wie man besser/schlechter als die andere.ZB. Sie können tun, random access in der Reihe, aber nicht möglich in der verlinkten Liste und andere. Dies ist jedoch vorausgesetzt, link-Listen und array werden in einer ähnlichen Anwendung. Aber eine richtige Antwort sollte sein, wie link-Liste wäre vorzuziehen array und Umgekehrt in einer bestimmten Anwendung aus.
Angenommen, Sie implementieren möchten eine Wörterbuch-Anwendung, was würden Sie verwenden ?
Array : mmm würde es ermöglichen den einfachen Abruf durch binäre Suche und auf anderen such-algo .. aber mal denken, wie link-Liste besser sein kann..Sagen Sie, Sie wollen zu suchen "Blob" im Wörterbuch. Würde es Sinn machen, eine link-Liste von A->B->C->D---->Z und dann jedes element in der Liste auch zeigt auf ein array oder eine andere Liste aller Wörter mit diesem Anfangsbuchstaben ..

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

Nun ist der obige Ansatz besser oder ein flaches array von [Adam,Apfel,Banane,Blob,Katze,Höhle] ? Würde es sogar möglich sein mit einem array ?
So ein großer Vorteil der link-Liste ist, können Sie ein element haben, das nicht nur zeigt auf das nächste element, sondern auch einige andere link-Liste/array/heap/oder irgendwelche anderen Speicher-Ort.
Array ist ein ein flat-contigous Speicher in Scheiben geschnitten in Blöcke der Größe des Elements wird es zu laden.. Link-Liste auf der anderen Seite ist ein Brocken von non-contigous-Speicher-Einheiten (kann beliebig groß sein und kann speichern alles) und zeigen einander, wie Sie wollen.
In ähnlicher Weise können sagen, Sie machen einen USB-Stick. Nun möchten Sie die Dateien gespeichert werden als ein array oder als link-Liste ? Ich denke, Sie bekommen die Idee, was ich darauf zu 🙂

InformationsquelleAutor der Antwort