So implementieren Sie eine PHP-verknüpfte Liste

So implementieren Sie eine PHP-verknüpfte Liste: Erstellen Sie zuerst eine PHP-Beispieldatei. Initialisieren Sie dann die Daten eines Knotens an einer bestimmten Position und löschen Sie schließlich den Knoten an einer bestimmten Position bestimmte Position.

Empfohlen: „PHP-Video-Tutorial“

Verknüpfte Liste

Verknüpfte Liste ist eine allgemeine Grunddatenstruktur, eine lineare Tabelle, aber sie speichert Daten nicht in linearer Reihenfolge, sondern speichert den Zeiger ( Zeiger) auf den nächsten Knoten in jedem Knoten.

Die Verwendung der verknüpften Listenstruktur kann den Nachteil verknüpfter Array-Listen überwinden, dass die Datengröße im Voraus bekannt sein muss. Die verknüpfte Listenstruktur kann den Speicherplatz des Computers vollständig nutzen und eine flexible dynamische Speicherverwaltung erreichen. Allerdings verliert die verknüpfte Liste den Vorteil des zufälligen Lesens des Arrays. Gleichzeitig weist die verknüpfte Liste aufgrund der Vergrößerung des Zeigerfelds des Knotens einen relativ großen Speicherplatzaufwand auf.

Es gibt viele verschiedene Arten von verknüpften Listen: einfach verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen.

Einseitig verknüpfte Liste

Der einfachste Typ einer verknüpften Liste ist die einseitig verknüpfte Liste, die zwei Felder enthält, ein Informationsfeld und ein Zeigerfeld. Dieser Link zeigt auf den nächsten Knoten in der Liste und der letzte Knoten zeigt auf einen Nullwert.

PHP implementiert eine einfache einseitig verknüpfte Liste

<?php

class Node
{
    private $Data;//节点数据
    private $Next;//存储下个点对象

    public function __construct($data, $next)
    {        $this->Data = $data;        $this->Next = $next;
    }

    public function __set($name, $value)
    {        if (isset($this->$name))            $this->$name = $value;
    }

    public function __get($name)
    {        if (isset($this->$name))            return $this->$name;        else
            return NULL;
    }
}

class LinkList
{
    private $head;//头节点
    private $len;

    /**
     * 初始化头节点
     */
    public function __construct()
    {        $this->init();
    }

    public function setHead(Node $val)
    {        $this->head = $val;
    }

    public function getHead()
    {        return $this->head;
    }

    public function getLen()
    {        return $this->len;
    }

    public function init()
    {        $this->setHead(new Node(NULL, NULL));        $this->len = 0;
    }

    /**
     * 设置某位置节点的数据
     * @param int $index
     * @param $data
     * @return bool
     */
    public function set(int $index, $data)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        $node->Data = $data;        return TRUE;
    }

    /**
     * 获取某位置节点的数据
     * @param int $index
     * @return mixed
     */
    public function get(int $index)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i <= $index) {            $node = $node->Next;            $i++;
        }        return $node->Data;
    }

    /**
     * 在某位置处插入节点
     * @param $data
     * @param int $index
     * @return bool
     */
    public function insert($data, int $index = 0)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = new Node($data, $node->Next);        $this->len++;        return TRUE;
    }

    /**
     * 删除某位置的节点
     * @param int $index
     * @return bool
     */
    public function delete(int $index)
    {        if ($index <= 0 || $index > $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = $node->Next->Next;        $this->len--;        return TRUE;
    }
}

Zweiseitig verknüpfte ListeEine komplexere verknüpfte Liste ist eine „doppelseitig verknüpfte Liste“ oder „doppelseitig verknüpfte Liste“. . Jeder Knoten hat zwei Verbindungen: eine zeigt auf den vorherigen Knoten (wenn diese „Verbindung“ die erste „Verbindung“ ist, zeigt sie auf einen Nullwert oder eine leere Liste), und die andere zeigt auf den nächsten Knoten (wenn diese „Verbindung“ ist). " ist die erste „Verbindung“, sie zeigt auf einen Nullwert oder eine leere Liste); „Wenn es die letzte „Verbindung“ ist, zeigt sie auf einen Nullwert oder eine leere Liste)

Rundschreiben Verknüpfte ListeIn einer zirkulär verknüpften Liste sind der erste Knoten und der letzte Knoten miteinander verbunden. Diese Methode kann sowohl in einseitig als auch in zweifach verknüpften Listen implementiert werden. Um eine zirkulär verknüpfte Liste zu konvertieren, beginnen Sie an einem beliebigen Knoten und folgen der Liste in beide Richtungen, bis Sie zum Startknoten zurückkehren. Betrachtet man eine andere Methode, kann eine zirkulär verknüpfte Liste als „kopflos und schwanzlos“ betrachtet werden. Solche Listen sind nützlich, um Datenspeicher-Caches zu schonen, vorausgesetzt, Sie haben ein Objekt in einer Liste und möchten, dass alle anderen Objekte in einer nicht spezifischen Anordnung durchlaufen werden. Der Zeiger auf die gesamte Liste kann als Zugriffszeiger bezeichnet werden.

Die Grundideen sind fast an der Zeit, mit der Aktualisierung fortzufahren

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine PHP-verknüpfte Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!