Array versus verknüpfte Liste

200

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

Das Codieren einer verknüpften Liste ist zweifellos etwas mehr Arbeit als das Verwenden eines Arrays, und man kann 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 gegenüber dem Speichern in einem Array?

Diese Frage ist kein Duplikat dieser Frage, da sich die andere Frage speziell auf eine bestimmte Java-Klasse bezieht, während sich diese Frage mit den allgemeinen Datenstrukturen befasst.

Onorio Catenacci
quelle
1
Verwandte - Wann wird LinkedList <> über ArrayList <> verwendet? - Es ist Java, aber Arrays (ArrayList) und verknüpfte Listen haben vermutlich in jeder Sprache die gleiche Leistung.
Bernhard Barker
1
@rootTraveller Eigentlich wäre diese Frage ein Duplikat dieser Frage, da meine Frage zuerst gestellt wurde.
Onorio Catenacci

Antworten:

147
  • Es ist einfacher, Daten unterschiedlicher Größe in einer verknüpften Liste zu speichern. Ein Array setzt voraus, dass jedes Element genau dieselbe 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 wachsen muss.
  • Das Mischen einer verknüpften Liste ist nur eine Frage der Änderung, was auf was verweist. 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.
Ryan
quelle
19
Wie werden Artikel unterschiedlicher Größe unterschiedlich behandelt? Eine verknüpfte Liste verwendet entweder eine feste Struktur mit einem nächsten Feld (erfordert eine feste Größe) oder speichert einen Zeiger auf die Daten im Auto (variable Größe OK). Beide Ansätze sind mit einem Vektor genauso einfach. Das gleiche gilt für das Mischen.
Brian
32
Ich würde sagen, das Mischen eines Arrays ist weniger kompliziert.
Hugh Allen
23
Diese Antwort ist falsch und irreführend. (außer dass Sie die Größe eines Arrays kennen müssen, wenn Sie es deklarieren)
Robert Paulson
35
Wäre das Iterieren einer verknüpften Liste aufgrund der Datenlokalität nicht langsamer?
Firas Assaad
6
@Rick, Vektoren ordnen normalerweise den benötigten Speicherplatz zu, sodass sie nicht jedes Mal, wenn die Größe zunimmt, neuen Speicherplatz zuweisen müssen. Das Ergebnis ist, dass Vektoren in der Regel viel weniger speicherintensiv sind und nicht mehr als verknüpfte Listen.
Winston Ewert
179

Ein weiterer guter Grund ist, dass sich verknüpfte Listen gut für effiziente Multithread-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. Sie können also viele Threads haben, die an derselben verknüpften Liste arbeiten. Darüber hinaus ist es möglich, sperrfreie Versionen mit CAS-Operationen zu erstellen und schwere Sperren insgesamt zu vermeiden.

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

Bei einem Array erfordert jede Änderung, die die Größe des Arrays ändert, wahrscheinlich das Sperren eines großen Teils des Arrays. Tatsächlich wird dies selten ohne eine globale Sperre für das gesamte Array durchgeführt, sodass Änderungen die Weltgeschehen stoppen.

Alex Miller
quelle
9
Alex - das ist eine interessante Überlegung, die mir nie in den Sinn gekommen wäre. Sehr gute Antwort. Ich würde dich zweimal bewerten, wenn ich könnte. :-)
Onorio Catenacci
5
Sehen Sie sich die Überspringlisten (insbesondere ConcurrentSkipListMap in Java 6) an, um eine gute Vorstellung davon zu erhalten, wohin Sie damit gehen können. CSLM ist eine sortierte, gleichzeitige Karte mit hervorragender Leistung. Weit, weit besser als eine synchronisierte TreeMap. tech.puredanger.com/2007/10/03/skip-lists
Alex Miller
… Außer dass ConcurrentSkipListMapoder ConcurrentSkipListMapsind keine Listen, auch wenn „Liste“ irgendwo in ihrem Namen vorkommt. Beide erfordern Schlüssel, die sortiert und eindeutig sind. Wenn Sie eine ListDatenstruktur benötigen , die doppelte Elemente in einer beliebigen Reihenfolge zulässt, ist dies nicht geeignet, und Sie müssten große Anstrengungen unternehmen, um eine Datenstruktur wie LinkedListeine gleichzeitig aktualisierbare Sache zu erstellen . Wenn Sie nur eine gleichzeitige Warteschlange oder Deque benötigen, gibt es sogar Beispiele, aber eine gleichzeitige List… Ich bin nicht davon überzeugt, dass dies überhaupt möglich ist.
Holger
128

Wikipedia hat einen sehr guten Abschnitt über die Unterschiede.

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

Auf der anderen Seite ermöglichen Arrays den wahlfreien Zugriff, während verknüpfte Listen nur den sequentiellen Zugriff auf Elemente ermöglichen. Einfach verknüpfte Listen können tatsächlich nur in eine Richtung durchlaufen werden. Dies macht verknüpfte Listen für Anwendungen ungeeignet, bei denen es nützlich ist, ein Element anhand seines Index schnell nachzuschlagen, z. B. Heapsort. Der sequentielle Zugriff auf Arrays ist aufgrund der Lokalität von Referenz- und Datencaches auf vielen Computern auch schneller als auf verknüpften Listen. Verknüpfte Listen profitieren fast nicht vom Cache.

Ein weiterer Nachteil von verknüpften Listen ist der zusätzliche Speicherplatz, der für Referenzen benötigt wird, was sie für Listen kleiner Datenelemente wie Zeichen oder Boolesche Werte häufig 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 mithilfe von Speicherpools gelöst wird.

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

Jonas Klemming
quelle
4
Dies ist die perfekte Antwort. Beschreibt kurz die Vor- und Nachteile von beiden.
Rick
danke)) ganz einfach, aber ich habe es nicht im Wiki gesehen)
Timur Fayzrakhmanov
58

Ich werde noch eine hinzufügen - Listen können als rein funktionale Datenstrukturen fungieren .

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

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

dh:

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

ohne die Daten, auf die von verwiesen wird, ain bund kopieren zu müssen c.

Aus diesem Grunde sind sie so beliebt in funktionalen Sprachen sind, die unveränderlichen Variablen - prependund tailOperationen auftreten können frei ohne die Originaldaten kopieren zu müssen - sehr wichtige Eigenschaften , wenn Sie Daten als unveränderlich sind zu behandeln.

Brian
quelle
4
Noch eine sehr interessante Überlegung, die ich mir nie ausgedacht hätte. Danke dir.
Onorio Catenacci
Wie kann ich das in Python machen?
Überaustausch
29

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

Aber ehrlich gesagt habe ich noch nie eine verknüpfte Liste verwendet. Wann immer ich schnelles Einfügen und Löschen benötigte, musste ich auch schnell nachschlagen, also ging ich zu einem HashSet oder einem Wörterbuch.

Tom Ritter
quelle
2
Sehr wahr, das Einfügen und Löschen erfolgt nach der Suche die meiste Zeit, daher muss auch die Summe der Zeitkomplexitäten berücksichtigt werden.
MA Hossain Tonu
28

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 beim Zusammenführen. Vielleicht wäre "Verketten" ein besseres Wort gewesen.

Rampion
quelle
2
Nur wenn Sie einfach eine Liste an die andere anhängen. Wenn Sie tatsächlich zwei sortierte Listen zusammenführen, wird ein Protokoll mit mehr als O (1) benötigt.
Herms
3
@Herms, aber Sie können zwei sortierte verknüpfte Listen zusammenführen, ohne zusätzlichen Speicher zuzuweisen. Sie müssen nur beide Listen durchlaufen und die Zeiger entsprechend einstellen. Das Zusammenführen von zwei Arrays würde normalerweise mindestens ein zusätzliches Array erfordern.
Paul Tomblin
1
Ja, das Zusammenführen von Listen ist speichereffizienter, aber das habe ich nicht wirklich kommentiert. Zu sagen, dass das Zusammenführen verknüpfter Listen O (1) ist, ist ohne Klärung des Falls sehr irreführend.
Herms
Das Zusammenführen von Listen mit @Herms ist nicht speichereffizienter als das Zusammenführen von Arrays unter einem vernünftigen Datenmodell.
Alexei Averchenko
2
Alexei Averchenko: Das Verketten von zwei Listen oder sogar das Zusammenführen von zwei sortierten Listen mit O (1) -Speicher kann an Ort und Stelle erfolgen. Das Verketten von zwei Arrays erfordert zwangsläufig O (n) Speicher, es sei denn, die Arrays sind bereits im Speicher benachbart. Ich denke, der Punkt, den Sie anstreben, ist der, bei dem eine Liste von n Elementen und ein Array von n Elementen beide O (n) Speicher beanspruchen, aber der Koeffizient für verknüpfte Listen höher ist.
Rampion
17

Ein weithin nicht anerkanntes Argument für ArrayList und gegen LinkedList ist, dass LinkedLists beim Debuggen unangenehm sind . Die Zeit, die Wartungsentwickler benötigen, um das Programm zu verstehen, z. B. um Fehler zu finden, nimmt zu, und IMHO rechtfertigt manchmal nicht die Nanosekunden für Leistungsverbesserungen oder Bytes für den Speicherverbrauch in Unternehmensanwendungen. Manchmal (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 wartbarer oder leichter 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 Finden bestimmter Objekte zu einem Alptraum beim Klicken auf Expand-The-Tree, ganz zu schweigen vom 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>
mhaller
quelle
17

Zunächst sollte es in C ++ nicht viel schwieriger sein, mit verknüpften Listen zu arbeiten als mit einem Array. Sie können die std :: list oder die Boost-Zeigerliste für verknüpfte Listen verwenden. Die Hauptprobleme bei verknüpften Listen und Arrays sind zusätzlicher Speicherplatz für Zeiger und ein schrecklicher Direktzugriff. 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
David Nehme
quelle
14

Für mich ist es so,

  1. Zugriff

    • Verknüpfte Listen erlauben nur den sequentiellen Zugriff auf Elemente. Somit ist die algorithmische Komplexität in der Größenordnung von O (n)
    • Arrays ermöglichen den wahlfreien Zugriff auf ihre Elemente und daher ist die Komplexität in der Größenordnung von O (1).
  2. Lager

    • Verknüpfte Listen erfordern 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 verknüpfter Listen ist von Natur aus dynamisch.
    • Die Größe des Arrays ist auf die Deklaration beschränkt.
  4. Einfügen / Löschen

    • Elemente können auf unbestimmte Zeit in verknüpfte Listen eingefügt und gelöscht werden.
    • Das Einfügen / Löschen von Werten in Arrays ist sehr teuer. Es erfordert eine Neuzuweisung des Speichers.
Sulman
quelle
Sie haben 2 Nummer 2 und 2 Nummer 3 :)
Hengameh
Wir können ein leeres Array deklarieren und dann nach Bedarf weitere Daten hinzufügen. Wie macht es noch eine feste Größe?
HebleV
11

Zwei Dinge:

Das Codieren einer verknüpften Liste ist zweifellos etwas mehr Arbeit als das Verwenden 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 anpassbares Array in C ++ ist.

Die Indizierung 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, wobei Sie in einem Vektor möglicherweise die Größe ändern und den Inhalt kopieren müssen.

Das Entfernen eines Elements aus einer Liste ist einfach, da Sie nur ein paar Links trennen und sie dann wieder zusammenfügen müssen. Das Entfernen eines Elements aus einem Vektor kann entweder schneller oder langsamer sein, je nachdem, ob Sie sich für eine Bestellung interessieren. Das Vertauschen des letzten Elements über das Element, das Sie entfernen möchten, ist schneller, während das Verschieben nach dem Herunterfahren langsamer ist, aber die Reihenfolge beibehält.

Bradtgmurray
quelle
Wie ich oben jemandem sagte, habe ich nur versucht, die Frage so zu beschreiben, wie sie mir gestellt wurde. Ich würde in C ++ sowieso nie ein Array (oder eine eigene verknüpfte Liste) verwenden - ich würde die STL-Versionen von beiden verwenden.
Onorio Catenacci
10

Eric Lippert hatte kürzlich einen Beitrag über einen der Gründe, warum Arrays konservativ verwendet werden sollten.

Rik
quelle
2
Zugegeben, ein guter Beitrag, aber nicht relevant in einer verknüpften Liste im Vergleich zur Diskussion des Arrays.
Robert Paulson
2
Ich würde vorschlagen, dass ein Großteil von Erics Artikel relevant ist, da er sowohl die Nachteile von Arrays als auch die Vorteile von Listen behandelt, unabhängig von der Listenimplementierung.
Bevan
8

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

Firas Assaad
quelle
7

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

itsmatt
quelle
7

Verknüpfte Listen sind besonders nützlich, wenn die Sammlung ständig wächst und schrumpft. Zum Beispiel ist es schwer vorstellbar, eine Warteschlange (am Ende hinzufügen, von vorne entfernen) mithilfe eines Arrays zu implementieren - 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.

James Curran
quelle
4
Sie könnten eine Array-basierte Warteschlange ohne zu viel Arbeit haben, die immer noch schnell / effizient ist. Sie müssten nur verfolgen, welcher Index der "Kopf" und welcher der "Schwanz" war. Dies funktioniert ziemlich gut, wenn Sie eine Warteschlange mit fester Größe benötigen (z. B. Tastaturpuffer in einem Kernel).
Herms
3
Und wird als "Kreispuffer" bezeichnet, wenn Sie ihn in Ihrer bevorzugten Algorithmusreferenz nachschlagen möchten.
Steve Jessop
7

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

Vasil
quelle
6
Vektoren (= im Grunde genommen Arrays) können dies auch, und die amortisierten Kosten für sie sind aufgrund von Problemen mit der Referenzlokalität normalerweise geringer als die für Listen.
Konrad Rudolph
7

Niemand codiert mehr seine eigene verknüpfte Liste. Das wäre dumm. 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 die Schüler, damit sie das Konzept verstehen können. Stattdessen verwendet jeder eine vorgefertigte Liste. In C ++ würde das, basierend auf der Beschreibung in unserer Frage, wahrscheinlich einen stl-Vektor ( #include <vector>) bedeuten .

Daher geht es bei der Auswahl einer verknüpften Liste im Vergleich zu einem Array ausschließlich darum, die verschiedenen Merkmale jeder Struktur im Verhältnis zu den Anforderungen Ihrer App abzuwägen. Die Überwindung des zusätzlichen Programmieraufwands sollte keinen Einfluss auf die Entscheidung haben.

Joel Coehoorn
quelle
2
Er..umm .. Der std :: vector ist ein Array, keine verknüpfte Liste. Die Standard-Linkliste ist std :: list.
James Curran
1
Ja, aber ich denke, Vektor ist näher an dem, was die Operation verlangt - ein dynamischer Array-Ersatz.
Joel Coehoorn
@ Joel, ich habe nur versucht, die Frage in Beziehung zu setzen, wie sie mir von diesem Kerl gestellt wurde, der versucht, C ++ zu lernen. Ich würde mich auch nicht darum kümmern, meine eigene verknüpfte Liste zu codieren, aber so fragte er mich. :-)
Onorio Catenacci
In Umgebungen mit eingeschränktem Speicher (Mikrocontroller), für die es benutzerdefinierte Compiler gibt, ist nicht die gesamte Sprache (z. B. Container in C ++) implementiert. Es kann also sein, dass Sie Ihre eigene verknüpfte Liste codieren müssen. nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus
Minh Tran
6

Es ist wirklich eine Frage der Effizienz, der Aufwand für das Einfügen, Entfernen oder Verschieben von Elementen (wo Sie nicht einfach tauschen) innerhalb einer verknüpften Liste ist minimal, dh die Operation selbst ist O (1), Verse O (n) für ein Array. Dies kann einen erheblichen Unterschied machen, wenn Sie stark mit einer Datenliste arbeiten. Sie haben Ihre Datentypen basierend auf der Art und Weise ausgewählt, wie Sie sie bearbeiten, und den effizientesten für den von Ihnen verwendeten Algorithmus ausgewählt.

Steve Baker
quelle
6

Arrays sind sinnvoll, wenn die genaue Anzahl der Elemente bekannt ist und wenn die Suche nach Index sinnvoll ist. Wenn ich beispielsweise den genauen Status meiner Videoausgabe zu einem bestimmten Zeitpunkt ohne Komprimierung speichern möchte, würde ich wahrscheinlich ein Array der Größe [1024] [768] verwenden. Dies liefert mir genau das, was ich brauche, und eine Liste wäre viel, viel langsamer, um den Wert eines bestimmten 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.

tloach
quelle
6

Arrays Vs Linked List:

  1. Die Zuweisung des Array-Speichers schlägt manchmal aufgrund eines fragmentierten Speichers fehl.
  2. Das Caching ist in Arrays besser, da allen Elementen zusammenhängender Speicherplatz zugewiesen wird.
  3. Die Codierung ist komplexer als Arrays.
  4. Im Gegensatz zu Arrays gibt es keine Größenbeschränkung für verknüpfte Listen
  5. Das Einfügen / Löschen in verknüpften Listen ist schneller und der Zugriff in Arrays ist schneller.
  6. Verknüpfte Liste aus Multithreading-Sicht besser.
AKS
quelle
-1: All dies muss begründet und nicht nur aufgezählt werden.
John Saunders
Jeder Punkt wurde bereits in den obigen Antworten erläutert. Als Nachzügler hatte ich keine andere Wahl als aufzuzählen. Übrigens, welches möchten Sie erklären lassen?
AKS
Wenn sie bereits erklärt wurden, warum antworten Sie dann?
John Saunders
2
Damit erhalten Sie einen zusammenfassenden Überblick über die Diskussion. Und ich mag solche Antworten, damit ich nicht immer wieder dieselbe Erklärung lesen muss. Und ich habe es für diejenigen getan, die den gleichen Denkstil haben wie ich. Unterschiedliche Menschen haben unterschiedliche Stile. Nichts Neues.
AKS
3

Da Arrays statischer Natur sind, werden alle Operationen wie die Speicherzuweisung nur zum Zeitpunkt der Kompilierung ausgeführt. Der Prozessor muss sich also weniger um seine Laufzeit bemühen.

debayan
quelle
3

Angenommen, Sie haben einen geordneten Satz, den 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 Reihe von Absätzen in einem Buch.

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

Ihr erstes Problem ist, wie Sie selbst bemerkt haben, das Einfügen - eine verknüpfte Liste ermöglicht das Einfügen in O (1), 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-ähnliche, ordinale Zugriffsschnittstelle bietet, bei der sowohl Lesen als auch Schreiben im schlimmsten Fall logarithmisch sind.

Ihr zweites und schwerwiegenderes Problem ist, dass bei einem Element, das das nächste Element findet, O (n) ist. Wenn die Menge nicht geändert wurde, können Sie den Index des Elements als Referenz anstelle des Zeigers beibehalten, wodurch find-next zu einer O (1) -Operation wird. Sie haben jedoch nur einen Zeiger auf das Objekt selbst und auf keinen Fall um seinen aktuellen Index im Array zu bestimmen, außer durch Scannen des gesamten "Arrays". Dies ist ein unüberwindbares Problem für Arrays. Selbst wenn Sie Einfügungen optimieren können, können Sie nichts tun, um die Suche nach dem nächsten Typ zu optimieren.

DenNukem
quelle
Könnten Sie dies bitte näher erläutern: "Es ist möglich, eine Datenstruktur zu erstellen, die eine Array-ähnliche, ordinale Zugriffsschnittstelle bietet, bei der sowohl Lesen als auch Schreiben im schlimmsten Fall logarithmisch sind."
Hengameh
1
Es gibt einige Dinge auf Wikipedia unter Dynamic Array / Vriants. Es ist jedoch nicht ganz das, was ich mir vorgestellt habe ... Stellen Sie sich eine b + baumartige Struktur mit Seiten, aber ohne Schlüssel vor. Stattdessen merkt sich jede Zwischenseite, wie viele Elemente in jeder Unterseite vorhanden sind, während die Blattseiten nur die enthalten Elemente in einem kleinen Array. Wenn Sie ein Element in eine Blattseite einfügen, müssen Sie ~ die Hälfte der Seite verschieben, um Platz zu schaffen, und dann die Anzahl der Elemente auf allen Ahnen-Seiten aktualisieren. Wenn Sie ein Element #N nachschlagen, addieren Sie einfach die Anzahl der untergeordneten Seitenelemente, bis Sie N überqueren, und steigen Sie dann in diesen Teilbaum ab
DenNukem
3

In einem Array haben Sie das Recht, in O (1) -Zeit auf jedes Element zuzugreifen. Daher eignet es sich für Operationen wie die binäre Suche, die schnelle Sortierung usw. Die verknüpfte Liste eignet sich andererseits zum Löschen von Einfügungen, da sie in O (1) -Zeit angezeigt wird. Beides hat sowohl Vor- als auch Nachteile. Wenn Sie eines dem anderen vorziehen, kommt es darauf an, was Sie implementieren möchten.

- Die größere Frage ist, ob wir eine Mischung aus beiden haben können. So etwas wie das, was Python und Perl als Listen implementieren.

Pranjal
quelle
3

Verknüpfte Liste

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

1 -> 3 -> 4

Einfügen (2)

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

Schließlich

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, jeder kann sich den Unterschied vorstellen! Nur für 4 Index führen wir 3 Schritte aus

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 Element in der Objektklasse aufheben! Aber für das Array müssen wir shiftLeft () ausführen

Hoffentlich hilft das! :) :)

Farah Nazifa
quelle
3

Verknüpfte Listen sind eher ein zu pflegender Aufwand als ein Array. Außerdem ist zusätzlicher Speicher erforderlich. Alle diese Punkte sind vereinbart. Aber es gibt ein paar Dinge, die Array nicht kann. Angenommen, Sie möchten ein Array mit einer Länge von 10 ^ 9, können Sie es nicht erhalten, da ein kontinuierlicher 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 sie einfach in der verknüpften Liste erweitert werden.

STL-Container haben normalerweise eine Implementierung einer verknüpften Liste hinter den Kulissen.

iec2011007
quelle
3

1- Die verknüpfte Liste ist eine dynamische Datenstruktur, die zur Laufzeit durch Zuweisen und Freigeben von Speicher vergrößert und verkleinert werden kann. Es ist also nicht erforderlich, eine anfängliche Größe der verknüpften Liste anzugeben. Das Einfügen und Löschen von Knoten ist wirklich einfacher.

2 Die Größe der verknüpften Liste kann zur Laufzeit zunehmen oder abnehmen, sodass keine Speicherverschwendung auftritt. Im Fall des Arrays entsteht viel Speicherplatz. Wenn wir beispielsweise ein Array der Größe 10 deklarieren und nur 6 Elemente darin speichern, wird Platz für 4 Elemente verschwendet. In der verknüpften Liste gibt es kein solches Problem, da der Speicher nur bei Bedarf zugewiesen wird.

3- Datenstrukturen wie Stapel und Warteschlangen können mithilfe einer verknüpften Liste einfach implementiert werden.

Ayman Amjad
quelle
2

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

Ein Nachteil könnte sein, dass Zeiger viel Platz beanspruchen.

Und darüber ist die Codierung schwieriger: Normalerweise benötigen Sie keine Code-verknüpfte Liste (oder nur einmal), sie sind in STL enthalten, und es ist nicht so kompliziert, wenn Sie dies noch tun müssen.

user15453
quelle
2
Zeiger nehmen viel Platz ein? Nicht wirklich. Wenn Sie eine verknüpfte Liste von Booleschen Werten speichern, nehmen die Zeiger prozentual viel Platz ein. Wenn Sie jedoch komplexe Objekte speichern (was im Allgemeinen der Fall ist), sind die Zeiger wahrscheinlich vernachlässigbar.
Herms
vergessenes Lächeln :) Aber sagte 'könnte' nicht 'ist'.
user15453
1

Ich denke auch, dass die Linkliste besser ist als Arrays. weil wir in der Linkliste, aber nicht in Arrays durchlaufen

iram Arshad
quelle
1

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

C Programmiersprache : Bei Verwendung einer verknüpften Liste (normalerweise über Strukturzeiger) muss besonders berücksichtigt werden, dass kein Speicher verloren geht. Wie bereits erwähnt, lassen sich verknüpfte Listen leicht mischen, da nur Zeiger geändert werden. Werden wir uns jedoch daran erinnern, alles freizugeben?

Java : Java verfügt über eine automatische Speicherbereinigung, sodass Speicherverluste kein Problem darstellen. Dem Programmierer auf hoher Ebene sind jedoch die Implementierungsdetails einer verknüpften Liste verborgen. Methoden wie das Entfernen eines Knotens aus der Mitte der Liste sind komplizierter als es einige Benutzer der Sprache erwarten würden.

SetSlapShot
quelle
1

Warum eine verknüpfte Liste über ein Array? Wie einige bereits gesagt haben, höhere Geschwindigkeit beim Einfügen und Löschen.

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 Byte "Gelöscht" verwenden, um die Tatsache darzustellen, dass eine Zeile gelöscht wurde. Daher ist eine Neuordnung des Arrays 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 die 20, 50, 100 zuletzt verwendeten Elemente enthält. Wenn sich das benötigte nicht in der kürzeren verknüpften Liste oder im kürzeren Array befindet, wechseln Sie zum großen Array. Wenn es dort gefunden wird, können Sie es dann zu der kleineren verknüpften Liste / dem kleineren Array hinzufügen, unter der Annahme, dass "zuletzt verwendete Elemente am wahrscheinlichsten wiederverwendet werden können" (und ja, möglicherweise das zuletzt verwendete Element aus der Liste stößt). Was in vielen Fällen zutrifft und ein Problem gelöst hat, das ich in einem .ASP-Modul zur Überprüfung von Sicherheitsberechtigungen mit Leichtigkeit, Eleganz und beeindruckender Geschwindigkeit angehen musste.

Juan Carlos
quelle
1

Während viele von Ihnen wichtige Adv./dis der verknüpften Liste gegen Array angesprochen haben, sind die meisten Vergleiche, wie einer besser / schlechter als der andere ist. Sie können im Array wahlfrei zugreifen, in verknüpften Listen und anderen jedoch nicht. 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 Suchalarme ermöglichen. Aber lassen Sie uns überlegen, wie die Linkliste besser sein kann. Sagen Sie, Sie möchten "Blob" im Wörterbuch suchen. Wäre es sinnvoll, eine Linkliste von A-> B-> C-> D ----> zu haben?

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

Ist der obige Ansatz nun besser oder eine flache Anordnung von [Adam, Apfel, Banane, Klecks, Katze, Höhle]? Wäre es mit Array überhaupt möglich? Ein Hauptvorteil der Linkliste besteht also darin, dass ein Element nicht nur auf das nächste Element verweist, sondern auch auf eine andere Linkliste / ein Array / einen Heap / oder einen anderen Speicherort. Array ist ein flacher zusammenhängender Speicher, der in die Blockgröße des Elements unterteilt ist, das gespeichert werden soll. Die Linkliste besteht dagegen aus nicht zusammenhängenden Speichereinheiten (kann beliebig groß sein und alles speichern) und zeigt auf jedes Element andere wie du willst. Angenommen, Sie erstellen ein USB-Laufwerk. Möchten Sie nun, dass Dateien als Array oder als Linkliste gespeichert werden? Ich denke du bekommst die Idee worauf ich zeige :)

Vikalp Veer
quelle