arrays - verkettete - vorteile stack




Warum sind verknüpfte Listen schneller als Arrays? (4)

Dieser Fragetitel ist irreführend.

Es behauptet, dass verkettete Listen schneller als Arrays sind, ohne den Bereich gut zu begrenzen. Es gibt mehrere Fälle, in denen Arrays wesentlich schneller sein können und es mehrere Male gibt, wenn eine verkettete Liste wesentlich schneller sein kann: Der spezielle Fall von verketteten Listen "wird schneller" scheint nicht unterstützt zu werden.

Es gibt zwei Dinge zu beachten:

  1. Die theoretischen Grenzen von verknüpften Listen im Vergleich zu Arrays in einer bestimmten Operation ; und
  2. das reale Implementierungs- und Nutzungsmuster einschließlich Cache-Lokalität und Zuordnungen.

Soweit der Zugriff eines indizierten Elements: Die Operation ist O(1) in einem Array und wie bereits erwähnt, ist sehr schnell (nur ein Offset). Die Operation ist O(k) in einer verketteten Liste (wobei k der Index ist und immer << n , abhängig sein kann), aber wenn die verkettete Liste bereits durchlaufen wird, ist dies O(1) pro Schritt, der "derselbe ist "als ein Array. Ob ein Array- Traversal ( for(i=0;i<len;i++ ) schneller (oder langsamer) ist, hängt von der jeweiligen Implementierung / Sprache / Laufzeit ab.

Wenn es jedoch einen speziellen Fall gibt, in dem das Array für eine der obigen Operationen (Suchen oder Traversieren) nicht schneller ist, wäre es interessant, etwas detaillierter zu sezieren . (Ich bin sicher, dass es möglich ist, eine Sprache mit einer sehr entarteten Implementierung von Arrays über Listen zu finden, husten Haskell Husten )

Glückliche Kodierung.

Meine Zusammenfassung der einfachen Verwendung: Arrays eignen sich gut für indizierten Zugriff und Operationen, bei denen Elemente ausgetauscht werden. Der nicht-amortisierte Betrieb der Größe und der zusätzliche Spielraum (falls erforderlich) können jedoch ziemlich teuer sein. Verkettete Listen amortisieren die Größenanpassung (und die Handelslücke für einen "Zeiger" pro Zelle) und können oft bei Operationen wie "Ausschneiden oder Einfügen einer Menge von Elementen" ausgezeichnet sein. Am Ende sind sie unterschiedliche Datenstrukturen und sollten als solche behandelt werden.

Ich bin sehr verwirrt darüber. Überall gibt es geschrieben "verknüpfte Listen sind schneller als Arrays", aber niemand macht sich die Mühe, WARUM zu sagen. Mit einfacher Logik kann ich nicht verstehen, wie eine verkettete Liste schneller sein kann. In einem Array sind alle Zellen nebeneinander, so lange man die Größe jeder Zelle kennt, ist es leicht, eine Zelle sofort zu erreichen. Zum Beispiel, wenn es eine Liste von 10 ganzen Zahlen gibt und ich den Wert in der vierten Zelle bekommen möchte, gehe ich direkt zum Anfang des Arrays + 24 Bytes und lese 8 Bytes von dort.

Wenn Sie andererseits eine verknüpfte Liste haben und das Element an die vierte Stelle bringen möchten, müssen Sie am Anfang oder am Ende der Liste beginnen (abhängig davon, ob es sich um eine einzelne oder doppelte Liste handelt) und von einem Knoten aus gehen zum anderen bis du findest wonach du suchst.

Wie kann der Teufel Schritt für Schritt schneller sein als direkt zu einem Element?


Hängt davon ab, auf welche Operation Sie sich beziehen. Das Hinzufügen oder Entfernen von Elementen ist in einer verknüpften Liste viel schneller als in einem Array.

Iterieren sequenziell über die Liste nacheinander ist mehr oder weniger die gleiche Geschwindigkeit in einer verknüpften Liste und einem Array.

Ein bestimmtes Element in der Mitte zu bekommen, ist in einem Array viel schneller.

Und das Array könnte Platz verschwenden, da beim Erweitern des Arrays sehr oft mehr Elemente zugewiesen werden, als zu diesem Zeitpunkt benötigt werden (denke ArrayList in Java).

Sie müssen also Ihre Datenstruktur auswählen, je nachdem, was Sie tun möchten:

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

Direktzugriff und idealerweise eine vordefinierte Größe -> benutze ein Array


Da kein Speicher verschoben wird, wenn in der Mitte des Arrays eingefügt wird. Für den Fall, den Sie vorgestellt haben, sind die wahren Arrays schneller, Sie brauchen nur Arithmetik, um von einem Element zum anderen zu gelangen. Verknüpfte Liste erfordert Indirektion und Fragmente Speicher. Der Schlüssel ist zu wissen, welche Struktur wann verwendet werden soll.


Verknüpfte Listen sind gegenüber Arrays vorzuziehen, wenn

a) Sie benötigen Konstant-Zeit-Einträge / Löschungen aus der Liste (wie in Echtzeit-Computing, wo Zeit Vorhersagbarkeit ist absolut kritisch)

b) Sie wissen nicht, wie viele Artikel in der Liste sein werden. Bei Arrays müssen Sie möglicherweise Speicher neu deklarieren und kopieren, wenn das Array zu groß wird

c) Sie benötigen keinen zufälligen Zugriff auf irgendwelche Elemente

d) Sie können Elemente in der Mitte der Liste einfügen (z. B. eine Prioritätswarteschlange)

Arrays sind vorzuziehen, wenn:

a) Sie benötigen indexierten / zufälligen Zugriff auf Elemente

b) Sie kennen die Anzahl der Elemente im Array im Voraus, so dass Sie die richtige Menge an Speicher für das Array zuweisen können

c) Sie brauchen Geschwindigkeit, wenn Sie alle Elemente der Reihe nach durchlaufen. Sie können mit Zeigermathematik auf das Array zugreifen, um auf jedes Element zuzugreifen, während Sie den Knoten basierend auf dem Zeiger für jedes Element in der verknüpften Liste suchen müssen, was zu Seitenfehlern führen kann, die zu Leistungseinbußen führen können.

d) Erinnerung ist ein Problem. Gefüllte Arrays belegen weniger Speicherplatz als verknüpfte Listen. Jedes Element im Array ist nur die Daten. Jeder verknüpfte Listenknoten benötigt sowohl die Daten als auch einen (oder mehrere) Zeiger auf die anderen Elemente in der verknüpften Liste.

Array-Listen (wie die in .Net) bieten Ihnen die Vorteile von Arrays, ordnen Ihnen jedoch dynamisch Ressourcen zu, so dass Sie sich nicht allzu viele Gedanken über die Listengröße machen müssen und Sie Elemente auf jedem Index ohne Aufwand löschen können. Elemente mischen. Leistungsmäßig sind Arraylisten langsamer als rohe Arrays.

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







linked-list