Comment implémenter une liste chaînée php

Comment implémenter la liste chaînée PHP : créez d'abord un exemple de fichier PHP ; puis initialisez le nœud principal ; puis définissez les données d'un nœud à une certaine position et insérez un nœud à une certaine position ; nœud à une certaine position.

Recommandé : "Tutoriel vidéo PHP"

Liste chaînée

La liste chaînée est courante La structure de données de base est une table linéaire, mais elle ne stocke pas les données dans un ordre linéaire, mais stocke un pointeur vers le nœud suivant dans chaque nœud.

L'utilisation de la structure de liste chaînée peut surmonter l'inconvénient de la liste chaînée de tableau selon laquelle la taille des données doit être connue à l'avance. La structure de liste chaînée peut utiliser pleinement l'espace mémoire de l'ordinateur et réaliser une gestion dynamique flexible de la mémoire. Cependant, la liste chaînée perd l'avantage de la lecture aléatoire du tableau. Dans le même temps, la liste chaînée a une surcharge d'espace relativement importante en raison de l'augmentation du champ de pointeur du nœud.

Il existe de nombreux types différents de listes chaînées : les listes chaînées simples, les listes chaînées doublement et les listes chaînées circulaires.

Liste chaînée unidirectionnelle

Le type de liste chaînée le plus simple est la liste chaînée unidirectionnelle, qui contient deux champs, un champ d'information et un champ de pointeur. Ce lien pointe vers le nœud suivant de la liste et le dernier nœud pointe vers une valeur nulle.

PHP implémente une simple liste chaînée unidirectionnelle

<?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;
    }
}

Lié dans les deux sens listOne Une liste chaînée plus complexe est une « liste chaînée doublement » ou « liste chaînée double face ». Chaque nœud possède deux connexions : l'une pointe vers le nœud précédent (lorsque cette « connexion » est la première « connexion », elle pointe vers une valeur nulle ou une liste vide et l'autre pointe vers le nœud suivant (lorsque cette « connexion ») ; " est la première "connexion", elle pointe vers une valeur nulle ou une liste vide); "Quand c'est la dernière "connexion", elle pointe vers une valeur nulle ou une liste vide)

Liste chaînée circulaire dans une liste chaînée circulaire, Le premier nœud et le dernier nœud sont connectés ensemble. Cette méthode peut être implémentée dans des listes chaînées unidirectionnelles et bidirectionnelles. Pour convertir une liste chaînée circulaire, vous commencez à n’importe quel nœud et suivez la liste dans les deux sens jusqu’à ce que vous reveniez au nœud de départ. En regardant une autre méthode, une liste chaînée circulaire peut être considérée comme « sans tête et sans queue ». De telles listes sont utiles pour conserver les caches de stockage de données, en supposant que vous ayez un objet dans une liste et que vous souhaitiez que tous les autres objets soient itérés selon un arrangement non spécifique. Le pointeur vers la liste entière peut être appelé pointeur d’accès.

Les idées de base sont presque l'heure de continuer la mise à jour

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!