Warum sind die verlinkten Listen schneller als arrays?

Ich bin sehr verwirrt über diese. Überall wird geschrieben "verlinkte Listen sind schneller als arrays", aber niemand macht sich die Mühe, zu sagen, WARUM. Mit einfachen Logik kann ich nicht verstehen, wie eine verknüpfte Liste, kann schneller sein. In einem array sind alle Zellen neben einander, so lange, wie Sie wissen, die Größe der einzelnen Zellen ist es leicht zu erreichen eine Zelle sofort. Zum Beispiel, wenn es eine Liste mit 10 ganzen zahlen und ich will den Wert in der vierten Zelle, dann gehe ich halt direkt an den Anfang des Arrays+24 bytes und lies 8 bytes von dort.

In der anderen hand, wenn Sie eine verlinkte Liste, und Sie möchten, um das element in der vierten Ort, dann haben Sie von Anfang oder Ende der Liste(je nachdem, ob es ein Einzel-oder Doppel-Liste) und gehen von einem Knoten zum anderen, bis Sie finden, was Sie suchen.

Also wie zum Teufel kann gehen Schritt für Schritt schneller sein als die, die direkt auf ein element?

  • Es hängt davon ab, was Sie versuchen zu erreichen. Wenn Sie möchten, um die Suche oder den Zugriff auf ein bestimmtes element, arrays sind schneller, aber wenn Sie möchten, einfügen oder löschen eines Elements einer verknüpften Liste ist schneller.
  • Ich würde sehr gerne sehen, einen link zu irgendwo, macht diese Behauptung.
  • Einige antworteten schnell, ist relevant. So in einigen Orten ist es geschrieben, dass die arrays sind schneller als verknüpfte Listen und in manchen Orten ist es geschrieben, verknüpfte Listen sind schneller als arrays. Ich gegoogelt und fand keine Ergebnisse auf, die-und das ist der Grund, warum ich die Frage gepostet hier, da war ich verwirrt. Jetzt mit meiner Frage gekrönt jeden anderen, der wundert sich über das gleiche bekommen Ihren Kopf gerade.
  • Was ist mit en.wikipedia.org/wiki/... ?
  • als Anfänger habe ich lieber eine geradewegs Antwort als Lesen die ganze wikipedeia und gar nichts zu verstehen. Nicht jeder ist bequem mit format Sprache afterall.
  • Verknüpfte Listen sind ...soooo sloooooooow... bei Indizierung/durchqueren, aber Sie sind wahnsinnig schnell bei der insertion/deletion im Vergleich zu dynamischen arrays.

InformationsquelleAutor Pithikos | 2011-03-26
  1. 13

    Diese Frage Titel ist irreführend.

    Er behauptet, dass die verlinkten Listen sind schneller als arrays ohne Einschränkung des Anwendungsbereichs gut. Es gibt eine Anzahl von Zeiten, wenn arrays können deutlich schneller und es gibt eine Anzahl von Zeiten, wenn eine verknüpfte Liste, kann deutlich schneller: besonderen Fall von verknüpften Listen "schneller" scheint nicht unterstützt zu werden.

    Gibt es zwei Dinge zu beachten:

    1. Die theoretischen Grenzen der verknüpften Listen versus arrays in einem bestimmten Betrieb; und
    2. der realen Implementierung und Nutzung Muster einschließlich cache-Lokalität und Zuweisungen.

    Soweit der Zugriff auf eine indizierte element: Die Betrieb ist O(1) in ein array und wies darauf hin, ist sehr schnell (nur offset). Die Betrieb ist O(k) in einer verknüpften Liste (wo k ist der index und immer << n je) aber, wenn die verknüpfte Liste ist bereits Durchlaufen dann ist dies O(1) pro Schritt was ist "dasselbe" wie ein array. Wenn ein array traversal (for(i=0;i<len;i++) ist schneller (oder langsamer) hängt insbesondere Umsetzung/Sprache/run-time.

    Jedoch, wenn es eine bestimmten Fall, wo das array ist nicht schneller, für die oben genannten Operationen (suchen oder traversal), wäre es interessant, zu sehen, zu analysiert im detail. (Ich bin sicher, es ist möglich, eine Sprache zu finden, die mit einem sehr degenerierten Implementierung von arrays gegenüber Listen Husten Haskell Husten)

    Happy coding.

    Meine einfache Nutzung Zusammenfassung: Arrays eignen sich sehr gut für den indizierten Zugriff und Operationen, an denen swapping-Elemente. Die nicht-fortgeführten neu-Größe-Bedienung und extra Locker (wenn erforderlich), kann jedoch ziemlich kostspielig. Verknüpfte Listen amortisieren sich die re-Dimensionierung (und Handel Locker für ein "Zeiger" pro Zelle) und kann oft excel bei Operationen wie "hacken raus oder durch ein Bündel von Elementen". Am Ende werden Sie die verschiedenen Daten-Strukturen und sollten als solche behandelt werden.

    InformationsquelleAutor
  2. 7

    Wie die meisten Probleme in der Programmierung ist der Kontext alles. Sie müssen denken, über die zu erwartenden Zugriffsmustern Ihrer Daten, und dann gestalten Sie Ihre storage-system entsprechend. Wenn Sie etwas einmal, und dann darauf zugreifen 1.000.000 mal, dann wen kümmert es, was die insert-Kosten? Auf der anderen Seite, wenn Sie einfügen/löschen so oft, wie Sie Sie Lesen, dann werden diese Kosten treiben die Entscheidung.

    InformationsquelleAutor Peter Rowell
  3. 4

    Hängt davon ab, welche operation auf die Sie sich beziehen. Hinzufügen oder entfernen von Elementen ist sehr viel schneller in eine verknüpfte Liste als ein array.

    Durchlaufen sequenziell über die Liste ist mehr oder weniger die gleiche Geschwindigkeit in einer verknüpften Liste und einem array.

    Immer ein bestimmtes element in der Mitte ist viel schneller in ein array.

    Und das array kann die Speicherplatz vergeuden, denn sehr oft wird bei der Erweiterung des array, mehrere Elemente zugeordnet sind, als benötigt an diesem Punkt in der Zeit (glaube ArrayList in Java).

    So müssen Sie wählen Sie Ihre Daten-Struktur je nachdem, was Sie tun möchten:

    viele Einfügungen und Durchlaufen sequentiell --> verwenden Sie eine LinkedList

    random access und idealerweise eine vordefinierte Größe --> verwenden Sie ein array

    • In Bezug auf die Iteration sequentiell, kann es sein, dass eine verlinkte Liste etwas Rand über arrays. Ihre Behauptung, dass die Iteration sequentiell über die Liste ist mehr oder weniger die gleiche Geschwindigkeit ist wohl korrekt, aber schwierig zu Messen, die auf modernen Computern. Ich glaube, dass in der reinsten Kontext, verknüpfte Listen Kante aus arrays on iteration speed, da das bewegen auf den nächsten Knoten nicht erforderlich die Berechnung der Adresse des nächsten offset-Speicher, wie Sie mit arrays, da die verlinkte Liste enthält die Adresse des nächsten Knoten.
    InformationsquelleAutor a_horse_with_no_name
  4. 3

    Weil kein Speicher verschoben, wenn die Einfügemarke in der Mitte des Arrays.
    Für den Fall, dass Sie präsentiert, seine true - arrays sind schneller, brauchen Sie arithmetische, nur um dann von einem element zum anderen. Verkettete Liste erfordert indirektheit und-Fragmente in Erinnerung.
    Der Schlüssel ist, zu wissen, welche Struktur zu verwenden, und wenn.

    • Erwähnenswert ist, dass die Aufnahme schneller (wie löschen), aber nicht indizierten Zugriff, das war Pithikos' Quelle der Verwirrung.
    • Also du meinst in dem Fall, wo es eine ganze Reihe, und Sie möchten, um ein neues element hinzuzufügen? Dann sind Sie sicher, um die Größe des gesamten Arrays. Was aber, wenn das array leer ist?
    • für einfachen Zugang ist durch nichts arrays. Die Frage ist "Warum sind die verlinkten Listen schneller als arrays?" und die Antwort auf diese Frage einzugehen. In real-life-Anwendung, die Sie machen viele Operationen auf array (prüfen, Sortieren), und dies ist der Grund, warum die mehr verwendet werden, oft als arrays;
    • einfügen eines Elements in eine einfach verkettete Liste -> nur ein alocation . einfügen ein element in einen std:vector (array) kann realloc Speicher und alle Elemente verschieben.- > die Zeit ist nicht konstant. Vielleicht kleiner oder größer.
    InformationsquelleAutor cprogrammer
  5. 2

    Verknüpfte Listen sind vorzuziehen, über arrays, wenn:

    a) Sie benötigen Konstante Zeit Einfügungen/Streichungen aus der Liste (wie im real-time-computing, wo die Zeit Vorhersehbarkeit ist absolut kritisch)

    b) Sie nicht wissen, wie viele Elemente in der Liste. Mit arrays können Sie brauchen, um neu zu erklären, und kopieren Sie den Speicher, wenn das array wächst zu groß

    c) brauchen Sie nicht den wahlfreien Zugriff auf beliebige Elemente

    d) Sie wollen in der Lage sein, Elemente einfügen, die in der Mitte der Liste (wie eine priority queue)

    Arrays sind vorzuziehen, wenn:

    a) Sie müssen indiziert/wahlfreier Zugriff auf Elemente

    b) Sie wissen, die Anzahl der Elemente im array vor der Zeit, so dass Sie zuordnen kann, der die korrekte Menge an Speicher für das array

    c) müssen Sie die Geschwindigkeit bei der Iteration über alle Elemente in der Sequenz. Sie können Zeiger Mathematik auf das array zugreifen auf alle Elemente, während Sie brauchen, um lookup der Knoten, basierend auf den Zeiger, die für jedes element in der verknüpften Liste, das kann zu seitenfehlern führen, die kann dazu führen, dass Leistung trifft.

    d) - Speicher ist ein Anliegen. Gefüllt arrays weniger Speicher als verknüpfte Listen. Jedes element im array ist, nur die Daten. Jede verkettete Liste node benötigt die Daten, als auch eine (oder mehrere) Zeiger auf die anderen Elemente in der verknüpften Liste.

    Array-Listen (wie in .Net) geben Sie die Vorteile von arrays, aber dynamisch Ressourcen zuweisen, so dass Sie brauchen nicht zu viel sorgen über die Liste Größe und Sie können Sie löschen Elemente, die in einem index ohne jede Anstrengung oder re-mischen Elemente um Sie herum. Performance-Weise, arraylists sind langsamer als roh-arrays.

    Referenz:
    Lamar Antwort
    https://stackoverflow.com/a/393578/6249148

    InformationsquelleAutor Ahmed Abdelkarim
Schreibe einen Kommentar