Grundlagen der PHP-Datenstruktur: doppelt verknüpfte Liste

Dieser Artikel stellt hauptsächlich die doppelt verknüpfte Liste vor, die die Grundlage der PHP-Datenstruktur darstellt und einen bestimmten Referenzwert hat. Jetzt können Freunde in Not darauf verweisen.

Was ist eine doppelt verknüpfte Liste? Liste?

Der vorherige Artikel über die Grundlagen der praktischen PHP-Datenstruktur – einfach verknüpfte Liste erwähnt

Eine einfach verknüpfte Liste besteht aus Objekten, die nacheinander Knoten sind. Jeder Knoten hat einen Zeiger auf Nächster Knoten. Das Zeigerfeld des letzten Knotens zeigt auf Null. Jeder Knoten kann jeden Datentyp speichern.

Jeder Knoten der doppelt verknüpften Liste verfügt über zwei Zeigerfelder, die auf den Vorgänger- bzw. Nachfolgerknoten zeigen. Eine einfach verknüpfte Liste ist unidirektional, während eine doppelt verknüpfte Liste bidirektional ist.

Allgemeine Operationen

Unsere allgemeinen Operationen für doppelt verknüpfte Listen sind wie folgt:

• Einfügen

• insertBefore

• insertAfter

• insertAtFirst

• insertAtLast

• deleteFirst

• deleteLast

• delete

• reverse

• getNthNode

• ...

PHP-Sprachimplementierung

Zuerst implementieren wir eine doppelt verknüpfte Liste ListNode entsprechend zur Definitionsart.

class ListNode
{
    public $data = null;
    public $next = null;
    public $prev = null;

    public function __construct(string $data)
    {
        $this->data = $data;
    }
}

Wenn wir uns die Klasse der verknüpften Liste ansehen, benötigen wir zunächst drei private Attribute, nämlich den Kopfknoten, den Endknoten und die Länge.

class DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;
}

Der nächste Schritt besteht darin, sich an die alten Regeln zu halten und direkt zu prüfen, wie die erste, häufig verwendete Einfügung implementiert wird. Dies ist eine Operation mit einer durchschnittlichen Zeitkomplexität von O(n).

/**
 * 插入一个节点
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);
    if ($this->head) {
        $currentNode = $this->head;
        while ($currentNode) {
            if ($currentNode->next === null) {
                $currentNode->next = $newNode;
                $newNode->prev = $currentNode;
                $this->last = $newNode;
                $this->length++;
                return true;
            }

            $currentNode = $currentNode->next;
        }
    } else {
        $this->head = &$newNode;
        $this->last = $newNode;
        $this->length++;
        return true;
    }

}

Schauen wir uns an, wie man Knoten löscht.

/**
 * 删除一个节点
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function delete(string $query = null)
{
if ($this->head) {
    $currentNode = $this->head;
    $prevNode = null;

    while ($currentNode) {
        if ($currentNode->data === $query) {
            if ($nextNode = $currentNode->next) {
                if ($prevNode) {
                    $prevNode->next = $nextNode;
                    $nextNode->prev = $prevNode;
                } else {
                    $this->head = $nextNode;
                    $nextNode->prev = null;
                }

                unset($currentNode);
            } else {
                if ($prevNode) {
                    $this->last = $prevNode;
                    $prevNode->next = null;
                    unset($currentNode);
                } else {
                    $this->head = null;
                    $this->last = null;
                }
            }

            $this->length--;
            return true;
        }

        $prevNode = $currentNode;
        $currentNode = $currentNode->next;
    }
}

    return false;
}

Das Umkehren einer doppelt verknüpften Liste ist auch nicht sehr kompliziert.

public function reverse()
{
    if ($this->head !== null) {

        if ($this->head->next !== null) {
            $reversedList = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reversedList;
                $currentNode->prev = $next;

                $reversedList = $currentNode;
                $currentNode = $next;

            }

            $this->last = $this->head;
            $this->head = $reversedList;
        }
    }
}

Eine detaillierte Implementierung anderer Operationen für doppelt verknüpfte Listen finden Sie hier.

Doppelt verknüpfte Listen sind im Vergleich zu einfach verknüpften Listen ein besonderer Teil der Zugriffsdatenstruktur für verknüpfte Listen. Zur verknüpften Listenstruktur gehören auch einfach verknüpfte Listen, zirkulär verknüpfte Listen und mehrfach verknüpfte Listen.

Sonderserie

PHP-Basisdatenstruktur-Sonderserien-Verzeichnisadresse: https://github.com/... Verwendet hauptsächlich PHP-Syntax, um grundlegende Datenstrukturen und Algorithmen zusammenzufassen. Es gibt auch grundlegende Kenntnisse, die in unserer täglichen PHP-Entwicklung leicht übersehen werden, und einige praktische Vorschläge zur Standardisierung, Bereitstellung und Optimierung in der modernen PHP-Entwicklung. Außerdem gibt es eine eingehende Untersuchung der Eigenschaften der Javascript-Sprache.

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass er für das Studium aller hilfreich ist. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

PHP-Datenstruktur-Grundstapel

Hinweise zur PHP-FPM-Parameterkonfiguration für PHP7+

Das obige ist der detaillierte Inhalt vonGrundlagen der PHP-Datenstruktur: doppelt verknüpfte Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!