Structure de données PHP : le charme des listes chaînées, exploration de l'organisation dynamique des données

Une liste chaînée est une structure de données qui utilise une série de nœuds avec des données et des pointeurs pour organiser les éléments. Elle est particulièrement adaptée au traitement de grands ensembles de données et aux opérations d'insertion/suppression fréquentes. Ses composants de base comprennent des nœuds (données et pointeurs vers le nœud suivant) et des nœuds principaux (pointant vers le premier nœud de la liste chaînée). Les opérations courantes de liste chaînée incluent : l’ajout (insertion de queue), la suppression (valeur spécifique) et le parcours.

Structure de données PHP : le charme des listes chaînées

Introduction

Une liste chaînée est une structure de données linéaire dont les éléments sont organisés comme une série de nœuds, chaque nœud contenant des données et un pointeur vers le nœud suivant . Contrairement à un tableau, les éléments d'une liste chaînée n'ont pas besoin d'être stockés de manière contiguë en mémoire, ce qui la rend idéale pour le traitement de grands ensembles de données et les opérations fréquentes d'insertion et de suppression.

Concept

Le composant de base d'une liste chaînée est un nœud. Chaque nœud est composé des parties suivantes :

• Données : stocke la valeur réelle
• Pointeur (suivant) : pointe vers le nœud suivant

Les listes liées interagissent les unes avec les autres via la connexion du nœud principal. Le nœud principal est un nœud spécial qui pointe vers le premier nœud de la liste chaînée.

Opérations

Voici quelques opérations courantes implémentées dans les listes chaînées :

class Node {
    public $data;
    public $next;
}

class LinkedList {
    private $head;

    // 添加新节点到尾部
    public function append($data) {
        $new_node = new Node();
        $new_node->data = $data;

        if ($this->head === null) {
            $this->head = $new_node;
        } else {
            $current_node = $this->head;
            while ($current_node->next !== null) {
                $current_node = $current_node->next;
            }
            $current_node->next = $new_node;
        }
    }

    // 从链表中删除特定值
    public function delete($data) {
        if ($this->head === null) {
            return;
        }

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

        $current_node = $this->head;
        while ($current_node->next !== null) {
            if ($current_node->next->data === $data) {
                $current_node->next = $current_node->next->next;
                return;
            }
            $current_node = $current_node->next;
        }
    }

    // 遍历链表并打印数据
    public function traverse() {
        $current_node = $this->head;
        while ($current_node !== null) {
            echo $current_node->data . " ";
            $current_node = $current_node->next;
        }
    }
}

Cas pratique

Créer une liste chaînée et effectuer certaines opérations :

$list = new LinkedList();

$list->append(10);
$list->append(20);
$list->append(30);

echo "链表：";
$list->traverse();
echo PHP_EOL;

$list->delete(20);

echo "删除 20 后：" ;
$list->traverse();
echo PHP_EOL;

Sortie :

链表：10 20 30
删除 20 后：10 30

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!