Wann würde ich eine verknüpfte Liste im Vergleich zu einem Stack in C++ verwenden

Question

Ich weiß, dass Sie in einer verknüpften Liste nicht vorab zugeordneten Speicher benötigen und die Einfüge- und Löschmethode ist wirklich einfach zu tun und das einzige, was ich wirklich über Stack weiß, ist der Push und Pop-Methode.

Answer 1

Verknüpfte Listen eignen sich zum Einfügen und Entfernen von Elementen an zufälligen Positionen. In einem Stapel werden wir nur am Ende angehängt oder entfernt.

Answer 2

verlinkte Liste vs Array (Stack)

Beide Arrays und verkettete Liste können lineare Daten von ähnlichen Typen zu speichern, verwendet werden, aber sie haben beide einige Vorteile und Nachteile übereinander.

Im Folgenden sind die Punkte zugunsten von Linked Lists.

(1) Die Größe der Arrays ist festgelegt: So müssen wir die obere Grenze für die Anzahl der Elemente im Voraus wissen. Im Allgemeinen ist der zugewiesene Speicher unabhängig von der Verwendung gleich der oberen Grenze, und bei praktischen Anwendungen wird die obere Grenze selten erreicht.

(2) Das Einfügen eines neuen Elements in ein Array von Elementen ist teuer, da Raum für die neuen Elemente erstellt werden muss und um Raum zu schaffen, müssen vorhandene Elemente verschoben werden.

Angenommen, wir haben eine sortierte Liste von IDs in einer Array-ID [].

ID [] = [1000, 1010, 1050, 2000, 2040, ... ..].

Und wenn wir eine neue ID 1005 einfügen möchten, müssen wir alle Elemente nach 1000 (außer 1000) verschieben, um die sortierte Reihenfolge beizubehalten.

Das Löschen ist auch bei Arrays teuer, solange keine speziellen Techniken verwendet werden. Um zum Beispiel 1010 in id [] zu löschen, muss alles nach 1010 verschoben werden.

So verlinkte Liste gibt folgende zwei Vorteile gegenüber Anordnungen 1) Dynamische Größe 2) Einfachheit Einfügen/Löschen

verlinkte Listen haben folgende Nachteile: 1) mit wahlfreiem Zugriff ist nicht gestattet. Wir müssen sequentiell auf die Elemente zugreifen, beginnend mit dem ersten Knoten. Daher können wir keine binäre Suche mit verknüpften Listen durchführen. 2) Zusätzlicher Speicherplatz für einen Zeiger ist für jedes Element der Liste erforderlich. 3) Arrays haben eine bessere Cache-Lokalität, die einen ziemlich großen Unterschied in der Leistung machen kann.