Liste chaînée double des bases de la structure de données PHP

Cet article présente principalement la liste doublement liée, la base de la structure de données PHP, qui a une certaine valeur de référence. Maintenant, je la partage avec vous. Les amis dans le besoin peuvent s'y référer

Qu'est-ce qu'une double liaison. liste?

L'article précédent sur les bases de la structure de données PHP pratique - liste à chaînage unique mentionné

Une liste à chaînage unique est composée d'objets qui sont des nœuds un par un. Chaque nœud a un pointeur vers le. nœud suivant. Le champ de pointeur du dernier nœud pointe vers null. Chaque nœud peut stocker n'importe quel type de données.

Chaque nœud de la liste à double chaînage possède deux champs de pointeur, pointant respectivement vers les nœuds prédécesseur et successeur. Une liste à chaînage unique est à sens unique, tandis qu'une liste à chaînage double est bidirectionnelle.

Opérations communes

Nos opérations courantes sur les listes doublement chaînées sont les suivantes :

• insérer

• insertBefore

• insertAfter

• insertAtFirst

• insertAtLast

• supprimerPremier

• supprimerLast

• supprimer

• inverser

• getNthNode

• ...

Implémentation du langage PHP

Nous implémentons d'abord une liste doublement chaînée ListNode selon au genre définition.

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

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

En regardant la classe de liste chaînée, nous avons d'abord besoin de 3 attributs privés, à savoir le nœud de tête, le nœud de queue et la longueur.

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

L'étape suivante consiste à s'en tenir aux anciennes règles et à regarder directement comment implémenter la première insertion couramment utilisée. Il s'agit d'une opération avec une complexité temporelle moyenne de 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;
    }

}

Voyons comment supprimer des nœuds.

/**
 * 删除一个节点
 * @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;
}

Inverser une liste doublement chaînée n'est pas non plus très compliqué.

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

Pour la mise en œuvre détaillée d'autres opérations sur les listes à double lien, veuillez vous référer ici.

La liste chaînée double est une partie spéciale de la structure de données d'accès à la liste chaînée par rapport à la liste chaînée unique. Appartiennent également à la structure de liste chaînée la liste chaînée unique, la liste chaînée circulaire et la liste chaînée multiple.

Série spéciale

Adresse du répertoire de la série spéciale sur la structure de données de base PHP : https://github.com/... Utilise principalement la syntaxe PHP pour résumer les structures de données et les algorithmes de base. Il existe également des connaissances de base qui sont facilement négligées dans notre développement PHP quotidien et quelques suggestions pratiques sur la standardisation, le déploiement et l'optimisation dans le développement PHP moderne. Il existe également une étude approfondie des caractéristiques du langage Javascript.

Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !

Recommandations associées :

Pile de base de la structure de données PHP

Notes sur la configuration des paramètres php-fpm pour php7+

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!