Ruby Linked Lists

Für diese Übung werden wir eine einfache Version einer einfach verknüpften Liste implementieren. Aber lassen Sie uns zuerst lernen, was eine verknüpfte Liste ist und warum Sie sich darum kümmern sollten.

Eine verknüpfte Liste eine Datenstruktur, die für schnelle und speichereffiziente Einfügungen und Löschungen verwendet wird. Im Gegensatz zu Arrays, bei denen es sich um einzelne Objekte handelt, enthalten verknüpfte Listen mehrere Knotenobjekte, die über Referenzen miteinander verknüpft sind.

Verknüpfte Listen können entweder einfach oder doppelt verknüpft werden. Wir werden uns vorerst auf einzeln verknüpfte Listen konzentrieren.

Einfach verknüpfte Liste

Wenn verknüpfte Listen mehrere miteinander verknüpfte Objekte sind, benötigen wir im Idealfall ein paar verschiedene Objekte.

  1. Ein LinkedList-Objekt, das alle Objekte in der Liste enthält

  2. Ein Knotenobjekt, das die Daten für das Element sowie einen Verweis auf den nächsten Knoten in der Liste enthält.

Warten Sie, warum nicht stattdessen Arrays verwenden?

In untergeordneten Sprachen werden Arrays in Blöcken zugewiesen. Daher sind Arrays statisch groß und können nur einen bestimmten Datentyp enthalten. Verknüpfte Listen speichern Daten im Heap, was bedeutet, dass die Daten unorganisiert gespeichert werden können. Da jeder Knoten auf den nächsten verweist, ist es weiterhin möglich, die Listenstruktur beizubehalten.

Erste Schritte

Der beste Weg, um zu verstehen, wie verknüpfte Listen funktionieren, besteht darin, eine zu erstellen! Machen wir das in Ruby. Hier ist der Prozess.

  1. Erstellen Sie zunächst eine Node -Klasse. Wir werden Attribute haben, um die Daten darzustellen (nennen wir das @data ) und den Verweis auf den nächsten Knoten (nennen wir das @next).

  2. Erstellen Sie eine LinkedList -Klasse. Diese Klasse hat zwei Werte, @head und @tail. Diese stellen den Anfang und das Ende der Liste dar. Initialisieren Sie beide vorerst auf nil. Wir haben eine leere Liste!

  3. Nun zur Einbeziehung der beiden Klassen zusammen. Erstellen Sie eine Methode für die Klasse LinkedList mit dem Namen insert_front. Die Herausforderung besteht darin, ein Element am Anfang der Liste hinzuzufügen. Dies kann durch Erstellen eines neuen Node und anschließendem Ausführen der folgenden Schritte erfolgen:

  4. Speichern Sie den Wert von @head in einer temporären Variablen

  5. Setzen Sie @head auf das neu erstellte Node. Beachten Sie, dass die Referenz next derzeit nil .

  6. Überlegen Sie, was wir tun müssten, wenn wir am Anfang einer verknüpften Liste ein neues Element hinzufügen. Konsultieren Sie das Diagramm (Hinweis: Wir müssen etwas mit der Referenz next des neuen Knotens tun)

  7. Schließlich behandeln Sie den Sonderfall des @tail . @tail sollte immer das letzte Node in der verknüpften Liste sein.

  8. Erstellen Sie eine andere Methode auf LinkedList oder Node mit dem Namen to_s, um die Liste auf der Konsole zu drucken.

Iterieren über verknüpfte Listen

Verwenden Sie while-Schleifen, um über verknüpfte Listen zu iterieren. While-Schleifen sind hier besser als for-Schleifen, da verknüpfte Listen keine length-Eigenschaft haben. Anstatt for eine bestimmte Anzahl von Malen zu iterieren, iterieren wir einfach while unser current Zeiger ist nicht nil .

Erstellen Sie eine lokale Variable namens current, die auf den Stammknoten der Liste zeigt. Innerhalb der Schleife können Sie zwei Dinge tun:

  1. zugriff auf den Wert des aktuellen Knotens unter current.data

  2. zeigen Sie die aktuelle Variable auf das nächste Element mit current = current.next

BONUS: Erstellen Sie eine insert_end -Methode, um Knoten am Ende der Liste hinzuzufügen.

SUPERBONUS: Erstellen Sie eine vielseitigere insert -Methode, um einen Knoten an einer beliebigen Stelle in der verknüpften Liste hinzuzufügen und einen Index für das neue Element bereitzustellen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.