Discussion :

[abc.xyz]

Bonjour,

je souhaiterais écrire la fonction de concaténation de deux listes simplement chaînées.

Quelques recherches (les bonnes?) sur Google m'ont appris que apparemment on ne pouvait pas faire de liste simplement chaînée en PHP (ce que j'ai du mail à croire) et qu'il fallait plutôt passer par les tableaux pour cette problématique. Mes recherches m'ont aussi appris que la SPL fournissait une classe mais pour les listes doublement chaînées et non les simples, c'est de la POO et moi je veux écrire cette concaténation de listes simplement chaînées en PHP non POO.

En fait je ne vous demande pas le code de concaténation de ces deux listes simplement chaînées car je veux l'écrire moi même, je vous demande plutôt de m'indiquer s'il est possible (ce que je crois sans en être sur) d'implémenter des listes simplement chaînées en PHP sans passer par les tableaux ni par la POO, pour ensuite les concaténer.

merci

[Celira]

Euh... Question bête : c'est quoi une liste simplement chainée déjà ? Est-ce que tu as un exemple de données de départ et de ce que tu veux obtenir en sortie.

[abc.xyz]

une liste simplement chaînée est ce qu'on appelle une structure de données, les structures de données jouent un rôle non négligeable en algorithmique.
Les listes doublement chaînées, les piles, les files, les arbres etc..sont d'autres structures de données.

[Celira]

Je me doute bien que c'est pas le nom du prochain StarWars Ce qui je voulais savoir c'est si tu avais un exemple concret, parce les concepts d'algorithmique en dev Web ce n'est pas exactement ce qu'on manie le plus.
En général, on manipule les tableaux, éventuellement les listes, mais la liste simplement chainée n'est pas franchement au menu.

Si j'ai bien compris le concept, chaque élément contient deux informations : sa valeur et quelque chose qui indique l'élément suivant. Si tu ne veux utiliser ni les tableaux, ni les objets, je ne vois pas bien comment tu vas stocker deux choses dans une seule variable à part peut-être une chaine contenant les deux infos concaténées avec un séparateur... mais tu vas passer ton temps à concaténer/déconcaténer tes chaines ou devoir utiliser des regex tous azimuts.

[CosmoKnacki]

C'est une chaîne dont chaque maillon contient une valeur et un pointeur vers le maillon suivant (ou un pointeur null pour la fin de chaîne). La seule différence entre une liste simplement et doublement chaînée est que les éléments (maillons) de la liste doublement chaînée contiennent également un pointeur vers l'élément précédent, ce qui permet de la parcourir dans les deux sens.

Ce sont des structures de données très utiles pour le langage C (et sûrement d'autres langages bas niveau) car on peut facilement (tout est relatif) les modifier (et allouer ou libérer de la mémoire pour les éléments) en changeant les pointeurs et parce que leur parcours est très rapide.

Bien évidemment en PHP, ça ne sert pas à grand chose vu qu'il n'y a pas de gestion de mémoire, et qu'un tableau indexé est modifiable à volonté et permet de faire la même chose.

Rien n'empêche de créer un équivalent en PHP en utilisant les références:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
$a=[]; $b=[]; $c=[]; $d=[]; $e=[];
$a=['k', &$b]; $b=['o', &$c]; $c=['a', &$d]; $d=['l', &$e]; $e=['a', null];
 
$current = &$a;
 
do {
    echo $current[0];
    $current = &$current[1];
} while ($current);

[Tsilefy]

PHP ne propose pas de liste chaînée, mais rien ne t'empêche d'utiliser une des classes qu'on trouve en ligne. Et je ne vois pas le problème avec SplDoublyLinkedList. Oui, c'est une classe, mais quelle différence ça fait dans ton code? Tu n'es pas obligé de faire de la POO pour l'utiliser, comme tu peux utiliser PDO sans faire de l'OOP.

Et surtout, peux-tu présenter ta problématique? Est-ce qu'il y a une raison particulière pour préférer une linked list par rapport au tableau de PHP (qui n'est pas vraiment un tableau)?

[Tsilefy]

C

Bien évidemment en PHP, ça ne sert pas à grand chose vu qu'il n'y a pas de gestion de mémoire, et qu'un tableau indexé est modifiable à volonté et permet de faire la même chose.

Oui. next(), current(), prev(), end() et reset() sont largement suffisants pour PHP.

[CosmoKnacki]

À noter qu'en PHP3, l'instruction foreach n'existait pas et que la seule manière de parcourir un tableau était d'utiliser ces instructions ainsi que each. Bien après la sortie de PHP4, il n'était pas rare de trouver encore des publications avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
reset($array);
while(list($key, $val) = each($array)) {
...
}

(voire la même mais entièrement écrite en majuscule.)

[abc.xyz]

Oui, en effet.
En fait la différence entre le C et PHP pour les listes simplement chaînées est que en C on utilise une structure (struct est un élément de langage du C) qui contient la valeur de la cellule et un pointeur vers la cellule suivante alors qu'en PHP on peut utiliser non pas une structure mais la solution par les tableaux que tu me présentes, chaque cellule de la liste étant représentée par un tableau contenant la valeur et une référence (au lieu du pointeur C) vers la cellule suivante.
Je ne comprends pas pourquoi la SPL a une classe pour les listes doublement chaînées et non pour les listes simplement chaînées sans doute car ceux qui ont codé ces classes de SPL pensent que la simple découle de la double ou sans doute car ils pensent que si on a besoin d'une simple il est facile d'utiliser la solution par les tableaux que vous m'avez présenté ici.

[Tsilefy]

Oui, en effet.
En fait la différence entre le C et PHP pour les listes simplement chaînées est que en C on utilise une structure (struct est un élément de langage du C) qui contient la valeur de la cellule et un pointeur vers la cellule suivante alors qu'en PHP on peut utiliser non pas une structure mais la solution par les tableaux que tu me présentes, chaque cellule de la liste étant représentée par un tableau contenant la valeur et une référence (au lieu du pointeur C) vers la cellule suivante.

Oui. Le terme "tableau" est très trompeur pour PHP. En réalité, c'est un dictionnaire/hashtable qui peut remplacer un tableau, un vector, une list, une pile etc...

Je ne comprends pas pourquoi la SPL a une classe pour les listes doublement chaînées et non pour les listes simplement chaînées sans doute car ceux qui ont codé ces classes de SPL pensent que la simple découle de la double ou sans doute car ils pensent que si on a besoin d'une simple il est facile d'utiliser la solution par les tableaux que vous m'avez présenté ici.

Oui, tu peux faire du double avec du simple. Si vraiment tu as absolument besoin uniquement des fonctionnalités d'une simple liste, tu peux encapsuler SplDoublyLinkedList avec un classe qui n'expose pas les méthodes de la double liste.