Verknüpfte Liste in PHP implementieren

1. Verwenden Sie die Klasse SplDoublyLinkedList zur Implementierung einer verketteten Liste in PHP
2. Verwenden Sie die push()-Methode, um Werte in eine verknüpfte Liste einzufügen
3. Verwenden Sie die add()-Methode, um Werte in eine verknüpfte Liste einzufügen
4. Verwendung der Methode pop() zum Löschen eines Elements in einer verknüpften Liste
5. Finden Sie den oberen und unteren Wert aus einer verknüpften Liste

Dieser Artikel stellt die Implementierung einer verketteten Liste in PHP vor.

Verwenden Sie die Klasse SplDoublyLinkedList zur Implementierung einer verketteten Liste in PHP

Eine verkettete Liste ist eine gemeinsame Datenstruktur, die in vielen Programmiersprachen implementiert ist. Es ist linear und enthält Knoten, die miteinander verbunden sind.

Jeder Knoten enthält die Daten und die Verbindung zum benachbarten Knoten. Somit bildet eine verkettete Liste eine Kette von Knoten. Es gibt verschiedene Variationen von verknüpften Listen.

1. Einfach verkettete Liste: Sie ist unidirektional. Es wird nur in Vorwärtsrichtung gefahren.
2. Doppelt verkettete Liste: Sie ist bidirektional. Es wird sowohl in Vorwärts- als auch in Rückwärtsrichtung gefahren.
3. Circular Linked List: Sie ist unidirektional und kreisförmig.
4. Circular Double Linked List: Sie ist bidirektional und zirkulär.

Wir können eine Vielzahl von Operationen in der verknüpften Liste ausführen. Die Grundoperationen sind:

• Durchquerung
• Einfügen
• Löschung
• aktualisieren
• Suchen

PHP stellt eine Klasse SplDoublyLinkedList zur Verfügung, um eine verkettete Liste zu implementieren. Es ist eine doppelt verknüpfte Liste.

Verwenden Sie die push()-Methode, um Werte in eine verknüpfte Liste einzufügen

Die Methode push() akzeptiert einen zu pushenden Parameter und ermöglicht das Anhängen der Werte in der Liste. Das Element wird an das Ende der verknüpften Liste verschoben.

Erstellen Sie beispielsweise eine Instanz der Klasse SplDoublyLinkedList und weisen Sie diese einer $list-Variablen zu. Rufen Sie die Methode push() auf und fügen Sie die Elemente ein.

Beispielcode:

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

Im folgenden Beispiel haben wir die Elemente 10, 20, 30, 40 und 40 in einer leeren verknüpften Liste angehängt. Beachten Sie, dass das Element 40 zweimal angehängt wird.

Wir können die folgende Funktion verwenden, um die Elemente der Liste anzuzeigen.

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

Die Methode rewind() spult den Iterator vom Anfang der verknüpften Liste zurück. Beispielsweise springt der Iterator zum ersten Element der Liste.

Die Methode valid() prüft, ob die verkettete Liste weitere Knoten enthält, und die Methode next() springt zum nächsten Element der verketteten Liste. Daher können wir diese Methoden wie im obigen Beispiel in der for-Schleife verwenden, um durch die Elemente der verknüpften Liste zu iterieren.

Innerhalb der Schleife bezeichnet die Methode current() das aktuelle Element. Das aktuelle Element wird also gedruckt.

Wir können diese Funktion displayList() aufrufen, wann immer wir die Listenelemente drucken müssen. Wir werden diese Funktion im Artikel mehrfach verwenden.

Das Folgende ist die Ausgabe, wenn wir die Funktion displayList() mit $list als Argument aufrufen.

Ausgabe:

10
20
30
40
40

Verwenden Sie die add()-Methode, um Werte in eine verknüpfte Liste einzufügen

Mit der Methode add() können wir Elemente in eine verkettete Liste einfügen, indem wir die Position angeben. Die Methode benötigt zwei Parameter.

Der erste Parameter ist der Index, wo das Element eingefügt werden soll, und der zweite Parameter ist das Element, das eingefügt werden soll. Rufen Sie beispielsweise die Methode add() mit 4 und 50 als Parameter auf und rufen Sie die Methode displayList() auf.

Beispielcode:

$list->add(4,50);
displayList($list);

Der obige Code fügt das Element 50 im vierten Index der von uns erstellten verknüpften Liste hinzu.

Ausgabe:

10
20
30
40
50
40

Als Ergebnis ist im vierten Index das Element 50 zu sehen. Das Element 40, bisher im vierten Index, wird an das Ende der verknüpften Liste verschoben.

Verwendung der Methode pop() zum Löschen eines Elements in einer verknüpften Liste

Wir können die Methode pop() verwenden, um das letzte Element aus einer verknüpften Liste zu entfernen. Die Methode akzeptiert keine Parameter.

Ab der letzten Ausgabe oben enthält die Liste die folgenden Elemente.

10
20
30
40
50
40

Die Methode pop() entfernt das letzte Element (40) aus der verknüpften Liste.

Beispielcode:

$list->pop();
displayList($list);

Ausgabe:

10
20
30
40
50

Finden Sie den oberen und unteren Wert aus einer verknüpften Liste

Wir können den oberen Wert der verknüpften Liste mit der Methode top() finden, und für den unteren Wert können wir die Methode bottom() verwenden. Das folgende Beispiel ist auch die Fortsetzung des obigen Beispiels.

Die Liste enthält die folgenden Elemente.

10
20
30
40
50

Wir können die Funktionen top() und bottom() mit dem Objekt $list aufrufen und sie mit der Funktion echo ausgeben.

Beispielcode:

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

Als Ergebnis wird das oberste Element als 50 und das unterste Element als 10 angezeigt.

Ausgabe:

10
20
30
40
50
the top value: 50
the bottom value: 10