Introduction aux listes chaînées en PHP : guide du débutant

Une liste chaînée est une structure de données de base en informatique, dont les éléments (appelés nœuds) sont connectés en séquence via des pointeurs. Contrairement aux tableaux, les listes chaînées sont dynamiques, ce qui signifie qu’elles peuvent augmenter ou diminuer en taille sans opérations de redimensionnement. Ce tutoriel couvrira les bases de l'implémentation de listes chaînées en PHP.

Structure des nœuds de liste chaînée

Chaque nœud de la liste chaînée est composé de deux parties :

1. Données : la valeur stockée dans le nœud.
2. Suivant : une référence (pointeur) vers le nœud suivant.

Voici un exemple d'implémentation d'un nœud basique en PHP :

<code class="language-php">class Node {
    public $data;
    public $next;

    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}</code>

Mise en œuvre d'une simple liste chaînée

Pour gérer les nœuds, nous créons une classe LinkedList qui maintient la tête de liste et fournit des méthodes pour la manipuler.

Opérations de base

1. Ajouter un nœud à la fin

Nous ajoutons des nœuds à la fin de la liste en parcourant les nœuds jusqu'à atteindre le dernier nœud.

<code class="language-php">class LinkedList {
    private $head;

    public function __construct() {
        $this->head = null;
    }

    public function append($data) {
        $newNode = new Node($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }
}</code>

2. Afficher la liste

Nous pouvons parcourir la liste pour imprimer tous les éléments.

<code class="language-php">public function display() {
    $current = $this->head;
    while ($current !== null) {
        echo $current->data . " -> ";
        $current = $current->next;
    }
    echo "NULL\n";
}</code>

3. Supprimer le nœud

Supprimer un nœud implique de trouver le nœud et de mettre à jour le pointeur du nœud précédent.

<code class="language-php">public function delete($data) {
    if ($this->head === null) {
        return;
    }

    if ($this->head->data === $data) {
        $this->head = $this->head->next;
        return;
    }

    $current = $this->head;
    while ($current->next !== null && $current->next->data !== $data) {
        $current = $current->next;
    }

    if ($current->next !== null) {
        $current->next = $current->next->next;
    }
}</code>

Exemple d'utilisation

Voici comment l'implémenter à l'aide d'une liste chaînée :

<code class="language-php">$linkedList = new LinkedList();
$linkedList->append(10);
$linkedList->append(20);
$linkedList->append(30);

echo "初始列表：\n";
$linkedList->display();

$linkedList->delete(20);
echo "删除 20 后：\n";
$linkedList->display();</code>

Sortie :

<code>初始列表：
10 -> 20 -> 30 -> NULL
删除 20 后：
10 -> 30 -> NULL</code>

Conclusion

Les listes chaînées sont des outils puissants pour la manipulation dynamique des données. Bien que PHP dispose de fonctions de tableau intégrées qui servent souvent un objectif similaire, la compréhension des listes chaînées est essentielle pour maîtriser les structures de données sous-jacentes et améliorer la pensée algorithmique. Cette implémentation fournit un point de départ pour des structures plus avancées telles que les listes doublement chaînées et les listes chaînées circulaires.

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!