Implémenter la liste chaînée en PHP

1. Utiliser la classe SplDoublyLinkedList pour implémenter une liste chaînée en PHP
2. Utilisez la méthode push() pour insérer des valeurs dans la liste liée
3. Utilisez la méthode add() pour insérer des valeurs dans la liste liée
4. Utilisez la méthode pop() pour supprimer l’élément dans la liste liée
5. Trouver la valeur supérieure et inférieure à partir d’une liste liée

Cet article présentera l’implémentation d’une liste chaînée en PHP.

Utiliser la classe SplDoublyLinkedList pour implémenter une liste chaînée en PHP

Une liste chaînée est une structure de données commune implémentée dans de nombreux langages de programmation. Il est linéaire et contient des nœuds liés les uns aux autres.

Chaque nœud contient les données et le lien vers le nœud adjacent. Ainsi, une liste chaînée forme une chaîne de nœuds. Il existe différentes variantes de listes liées.

1. Liste chaînée simple : elle est unidirectionnelle. Il ne traverse que dans le sens avant.
2. Liste doublement liée : elle est bidirectionnelle. Il traverse à la fois dans les directions avant et arrière.
3. Liste liée circulaire : Elle est unidirectionnelle et circulaire.
4. Liste circulaire doublement liée : elle est bidirectionnelle et circulaire.

Nous pouvons effectuer diverses opérations dans la liste chaînée. Les opérations de base sont :

• traversée
• insertion
• suppression
• mettre à jour
• recherche

PHP fournit une classe SplDoublyLinkedList pour implémenter une liste chaînée. C’est une liste doublement liée.

Utilisez la méthode push() pour insérer des valeurs dans la liste liée

La méthode push() accepte un paramètre à pousser et permet d’ajouter les valeurs dans la liste. L’élément sera poussé à la fin de la liste liée.

Par exemple, créez une instance de la classe SplDoublyLinkedList et affectez-la à une variable $list. Invoquez la méthode push() et insérez les éléments.

Exemple de code :

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

Dans l’exemple ci-dessous, nous avons ajouté les éléments 10, 20, 30, 40 et 40 dans une liste chaînée vide. Notez que l’élément 40 est ajouté deux fois.

Nous pouvons utiliser la fonction suivante pour afficher les éléments de la liste.

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

La méthode rewind() rembobine l’itérateur depuis le début de la liste chaînée. Par exemple, l’itérateur se déplacera vers le premier élément de la liste.

La méthode valid() vérifie si la liste chaînée contient plus de nœuds, et la méthode next() passe à l’élément suivant de la liste chaînée. Ainsi, nous pouvons utiliser ces méthodes comme dans l’exemple ci-dessus dans la boucle for pour parcourir les éléments de la liste chaînée.

A l’intérieur de la boucle, la méthode current() désigne l’élément courant. Ainsi, l’élément courant sera imprimé.

Nous pouvons appeler cette fonction displayList() chaque fois que nous avons besoin d’imprimer les éléments de la liste. Nous utiliserons cette fonction plusieurs fois dans l’article.

Voici la sortie lorsque nous appelons la fonction displayList() avec $list comme argument.

Production:

10
20
30
40
40

Utilisez la méthode add() pour insérer des valeurs dans la liste liée

Nous pouvons utiliser la méthode add() pour insérer des éléments dans une liste chaînée en spécifiant la position. La méthode prend deux paramètres.

Le premier paramètre est l’index où l’élément doit être inséré, et le deuxième paramètre est l’élément à insérer. Par exemple, invoquez la méthode add() avec 4 et 50 comme paramètres et appelez la méthode displayList().

Exemple de code :

$list->add(4,50);
displayList($list);

Le code ci-dessus ajoute l’élément 50 dans le quatrième index de la liste chaînée que nous avons créée.

Production:

10
20
30
40
50
40

En conséquence, l’élément 50 apparaît dans le quatrième indice. L’élément 40, auparavant dans le quatrième index, est décalé à la fin de la liste chaînée.

Utilisez la méthode pop() pour supprimer l’élément dans la liste liée

On peut utiliser la méthode pop() pour supprimer le dernier élément d’une liste chaînée. La méthode ne prend aucun paramètre.

Depuis la dernière sortie ci-dessus, la liste contient les éléments suivants.

10
20
30
40
50
40

La méthode pop() supprimera le dernier élément (40) de la liste chaînée.

Exemple de code :

$list->pop();
displayList($list);

Production:

10
20
30
40
50

Trouver la valeur supérieure et inférieure à partir d’une liste liée

Nous pouvons trouver la valeur supérieure de la liste chaînée en utilisant la méthode top(), et pour la valeur inférieure, nous pouvons utiliser la méthode bottom(). L’exemple ci-dessous est également la suite de l’exemple ci-dessus.

La liste contient les éléments suivants.

10
20
30
40
50

Nous pouvons invoquer les fonctions top() et bottom() avec l’objet $list et les afficher à l’aide de la fonction echo.

Exemple de code :

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

Par conséquent, l’élément le plus haut est affiché comme 50 et l’élément le plus bas est affiché comme 10.

Production:

10
20
30
40
50
the top value: 50
the bottom value: 10