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

不言
Libérer: 2023-04-02 18:30:02
original
1623 Les gens l'ont consulté

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;
    }
}
Copier après la connexion

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;
}
Copier après la connexion

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

}
Copier après la connexion

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;
}
Copier après la connexion

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;
        }
    }
}
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal