Discussion :

[gl]

Juste une petite remarque en passant, ça me "choque" toujours de voir une liste (ou pile, queue, etc.) connue par son premier noeud (et par conséquence d'avoir une classe node en guise de pile).

De mon point de vue, une liste contient des éléments (et à la limite que ce soit des noeuds chaînés par un pointeur, un tableau ou que sais-je, c'est un détail d'implémentation qui devrait rester interne) et fournie des APIs pour manipuler la liste. Mais une liste n'est pas et ne peut pas se résumer à un noeud.

[koala01]

Salut,

Juste une petite remarque en passant, ça me "choque" toujours de voir une liste (ou pile, queue, etc.) connue par son premier noeud (et par conséquence d'avoir une classe node en guise de pile).

De mon point de vue, une liste contient des éléments (et à la limite que ce soit des noeuds chaînés par un pointeur, un tableau ou que sais-je, c'est un détail d'implémentation qui devrait rester interne) et fournie des APIs pour manipuler la liste. Mais une liste n'est pas et ne peut pas se résumer à un noeud.

+1...

J'y vois au moins deux raisons:
La première est que cela nous permet de passer au choix un pointeur ou une référence sur la liste à nos fonctions, au lieu de devoir passer... un pointeur de pointeur

La seconde est que cela permet à la liste de disposer (éventuellement) d'informations supplémentaires comme un pointeur sur le dernier élément, qui permette d'assurer une insertion en fin de file en "temps constant".

Enfin, suis-je le seul à trouver un peu choquant d'avoir une liste dont le nom (lors du passage de paramètre) est... lapile (je fais référence au premier message de la discussion)

Une pile, une file et une liste sont trois structures qui, bien que très proches les unes des autres, ont des comportements totalement différents, et il me semble donc dommage et dangereux d'introduire un terme pouvant induire le lecteur du code sur l'objectif poursuivi par la structure lorsque l'on décide de donner un nom à une variable ou un argument

[TropMDR]

Juste une petite remarque en passant, ça me "choque" toujours de voir une liste (ou pile, queue, etc.) connue par son premier noeud (et par conséquence d'avoir une classe node en guise de pile).

De mon point de vue, une liste contient des éléments (et à la limite que ce soit des noeuds chaînés par un pointeur, un tableau ou que sais-je, c'est un détail d'implémentation qui devrait rester interne) et fournie des APIs pour manipuler la liste. Mais une liste n'est pas et ne peut pas se résumer à un noeud.

Pour une pile je suis d'accord, ça devrait être sagement encapsulé. En revanche, pour une liste, il peut y avoir un intérêt à vraiment voir ça comme "une liste chaînée" : le partage et la persistance.
Comme ça, quand tu as la liste [2;3;4], rien ne t'empêche de rajouter 1 en tête, et d'avoir *à la fois* la liste [1;2;3;4] et la liste [2;3;4]. Ce qui risque d'être nettement plus pénible si c'est encapsulé.

[Médinoc]

Personnellement, je suis prêt à accepter cela tant qu'il n'y a pas de typedef node* liste;, qui m'horripile.

[koala01]

Pour une pile je suis d'accord, ça devrait être sagement encapsulé. En revanche, pour une liste, il peut y avoir un intérêt à vraiment voir ça comme "une liste chaînée" : le partage et la persistance.
Comme ça, quand tu as la liste [2;3;4], rien ne t'empêche de rajouter 1 en tête, et d'avoir *à la fois* la liste [1;2;3;4] et la liste [2;3;4]. Ce qui risque d'être nettement plus pénible si c'est encapsulé.

Absolument pas, du moins dans le contexte où nous sommes ici, qui est une programmation procédurale pure (et, à bien y réfléchir, cela ne poserait pas de problème particulier si nous étions dans un contexte OO )...

Si, d'une manière générale, tu souhaite garder un pointeur sur un élément particulier de la liste, il n'y a strictement rien qui t'empêche de maintenir un tel pointeur, sachant qu'il sera alors connu (et utilisé) sous la forme d'un noeud et non sous la forme d'une liste.

Au contraire, si tel est effectivement ton souhait, le fait de séparer clairement la structure liste de la structure noeud t'évitera bien des déboires:

Imagine si tu n'encapsule pas ton noeud dans une structure particulière, et que tu veut, effectivement garder un pointeur sur le deuxième élément:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main
{
    Node * liste=NULL;
    push(&liste,4);
    push(&liste,3);
    push(&liste,2);
    /*nous avons nos trois premiers éléments, et tout va bien */
    Node *l2=liste /* on garde cette première version de la liste grace à l2*/
    push(&liste,1);
    /* à priori, tout va bien, tant que nous continuerons à invoquer push
     * en passant &liste, mais...
     */
    push(&l2,-10); // CRACK: on perd tous les éléments qui précèdent 2
                   // et on a une fuite mémoire
    return 0;
}

Par contre, si tu sépare correctement les deux concepts que sont liste et noeud, sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
struct Noeud
{
    int val;
    Noeud * next;
};
struct Liste
{
    Noeud * first;
    /* j'apprécie particulièrement d'avoir */
    Noeud * last;
};

le prototype de tes fonctions push et pull devient

Code :

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

1
2
3
4
5
void push(Liste & l, int val);
void pull(Liste & l, int val);
/* voir, si tu veux travailler avec des pointeurs */
void push(List * l, int val);
void pull(List * l, int val);

Et, du coup, tu va travailler sous une forme proche de

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    Liste liste;
    /* il serait pas mal d'avoir un système d'initialisation complet, mais 
     * on peut se contenter de
     */
    liste.first = NULL;
    /* et au besoin */
    liste.last = NULL;
    /* créons notre liste de départ */
    push(liste, 4);
    push(liste, 3);
    push(liste, 2);
    /* et gardons un pointeur sur l'élément "2" */
   Node * n = liste.first;
   /* rajoutons des éléments avant "2" */
   push(liste, 1);
   push(liste, 0);
   /* la ligne suivante sera refusée à la compilation, car n n'est pas
    * une liste
    */
   push(n, -10);
}

Tu n'a au final que des avantages pour un cout, finalement, des plus réduits (on a quoi deux pointeurs présents en mémoire en plus, ou à peine plus )

[TropMDR]

Je pense qu'on a surtout une différence de vocabulaire. Pour moi :
Sur une pile, push est de type void, parce qu'on modifie la pile
Sur une liste, push retourne une "nouvelle" liste (bien sûr, ça introduit du partage et fait qu'une gestion "naïve" de la mémoire n'est plus possible. A défaut de GC, il va falloir faire chauffer les smarts pointers).

Sinon, j'ai du mal à voir la distinction entre une pile et une liste.

[Médinoc]

Déjà, c'est rare qu'une pile ait une fonction pull(), qui ressemble plus au enqueue() d'une file.
Une pile chaînée, ça fait du push() et du pop()...

[koala01]

Je pense qu'on a surtout une différence de vocabulaire. Pour moi :
Sur une pile, push est de type void, parce qu'on modifie la pile
Sur une liste, push retourne une "nouvelle" liste (bien sûr, ça introduit du partage et fait qu'une gestion "naïve" de la mémoire n'est plus possible. A défaut de GC, il va falloir faire chauffer les smarts pointers).

Sinon, j'ai du mal à voir la distinction entre une pile et une liste.

C'est une simple question de sémantique...

Une pile fonctionne selon le principe LIFO (Last In, First Out), car, à l'instar d'une pile de caisse, tu ne peux accéder qu'au dernier élément ajouté (ou à celui ajouté juste avant si le dernier a déjà été retiré) sous peine de... te prendre les caisses sur la tête.

Le principe de gestion inverse est le FIFO (First In, First Out), qui est, par exemple, conseillé pour la gestion des denrées périssables, sous peine de trouver au fond du réfrigérateur un morceau de viande datant de la première guerre).

On observe ce principe lorsqu'il s'agit de passer à la caisse d'un magasin: le premier arrivé à la caisse sera le premier à la quitter, et l'insertion se fait "en bout de file".

Enfin, la liste ne donne pas vraiment de priorité et permet l'ajout d'élément au début, à la fin et même "au beau milieu" de la liste, voire, la possibilité de trier les éléments

Le parcours peut (éventuellement) se faire dans les deux sens (si la liste est doublement chainée), voire, reprendre "au beau milieu" (pour autant que l'on dispose d'un élément servant de point de départ différent que le premier ou le dernier élément de la liste)

On a donc trois concepts (pour ceux dont j'ai parlé) qui, bien que très proches par les informations qu'ils contiennent présentent trois principes tout à fait différents

[TropMDR]

C'est une simple question de sémantique...

C'est bien le problème :-D

Une pile fonctionne selon le principe LIFO (Last In, First Out), car, à l'instar d'une pile de caisse, tu ne peux accéder qu'au dernier élément ajouté (ou à celui ajouté juste avant si le dernier a déjà été retiré) sous peine de... te prendre les caisses sur la tête.

Effectivement, la vision de base d'une pile, c'est push, pop, rien d'autre ! Mais c'est quand même assez réducteur. Pas mal de langage à pile par exemple (dont le bytecode Java est un représentant des plus connus) permettent d'accéder au n-ième élément de la pile, en lecture comme en écriture. C'est une vision un peu plus laxiste de ce qu'est une pile. (non, parler de Java n'est pas complètement hors sujet, on peut très bien implémenter une VM java en C++ )

Enfin, la liste ne donne pas vraiment de priorité et permet l'ajout d'élément au début, à la fin et même "au beau milieu" de la liste, voire, la possibilité de trier les éléments

Là tu prends l'approche inverse Tu donnes tout de suite une vision "relâché" de ce que peut être une liste. Dans sa version "élémentaire", une liste, tu peux accéder à sa tête et à sa queue, et construire une nouvelle liste en rajoutant un élément. C'est la structure "récursive" par excellence, qui permet partage et persistance. (c'est d'ailleurs la structure "de base" de nombreux langages fonctionnels).
Bien sûr, on peut, comme tu le fais, en avoir une vision plus souple, où l'on accède au dernier élément, où l'on modifie la liste au milieu, etc. Mais on y perd la possibilité de profiter (sans risque) du partage et de la persistance. C'est un choix à faire en toute technique d'arrosage :p

Bref, pour résumer, pour moi (et je suis parfaitement conscient d'avoir une vision biaisée par ma pratique du monde fonctionnel), une pile ne devrait pas se "scinder" ou se partager, et gagne donc tout à être encapsulée (par exemple en cachant en fait une liste chaînée comme vu ci après), avec des méthodes de type void (sauf pour l'accès au premier élément hein... Je veux juste dire qu'on ne retourne pas une nouvelle pile) alors qu'une liste simple (pas d'accès au dernier élément, pas d'insertion au milieu) devrait pouvoir avoir différent "futurs" et donc ne pas être encapsulé (ce qui ne veux pas dire qu'il faut que l'utilisateur aille mettre les mains dans le cambouis hein !)

Mais on tourne en rond

[koala01]

Là tu prends l'approche inverse Tu donnes tout de suite une vision "relâché" de ce que peut être une liste. Dans sa version "élémentaire", une liste, tu peux accéder à sa tête et à sa queue, et construire une nouvelle liste en rajoutant un élément. C'est la structure "récursive" par excellence, qui permet partage et persistance. (c'est d'ailleurs la structure "de base" de nombreux langages fonctionnels).
Bien sûr, on peut, comme tu le fais, en avoir une vision plus souple, où l'on accède au dernier élément, où l'on modifie la liste au milieu, etc. Mais on y perd la possibilité de profiter (sans risque) du partage et de la persistance. C'est un choix à faire en toute technique d'arrosage :p

Pas vraiment...

Conceptuellement parlant, la file est, simplement, une structure dynamique qui ne se démarque d'un tableau que par son accès exclusivement séquentiel, point-barre.

A partir de là, une différence peut être faite selon la direction dans laquelle l'accès peut être effectué (du premier au dernier uniquement pour la liste "simplement chainée" ou dans les deux sens pour la liste "doublement chainée"), mais, au delà, il est possible (car pas forcément utile / nécessaire / intéressant, je te l'accorde) d'y appliquer des algorithmes de tri, de décider d'ajouter quelque chose "en plein milieu" ou de décider... n'importe quoi, y compris de la rendre circulaire.

Par contre, de telles décisions sont purement et simplement sans fondement pour les autres structures dont j'ai parlé (la pile et la file) car elles présentent, conceptuellement parlant, des restrictions qui leur sont propres, du seul fait du modèle de gestion envisagé (FIFO ou LIFO) pour l'une et pour l'autre.

[gl]

En revanche, pour une liste, il peut y avoir un intérêt à vraiment voir ça comme "une liste chaînée" : le partage et la persistance.
Comme ça, quand tu as la liste [2;3;4], rien ne t'empêche de rajouter 1 en tête, et d'avoir *à la fois* la liste [1;2;3;4] et la liste [2;3;4]. Ce qui risque d'être nettement plus pénible si c'est encapsulé.

Oui, mais justement tu n'as pas à la fois la liste [1;2;3;4] et la liste [2;3;4] dans le sens où ce ne sont pas deux listes distinctes et que la modification d'une des deux va modifier l'autre (voire l'invalidé complétement).

Grosso-modo, je vois trois cas qui peuvent plus ou moins correspondre à ce que tu cherches ici :

• Avoir deux listes distinctes, et donc dupliquer la liste initiale ou mettre en place des mécanismes assez complexes de chaînages multiples.
• Avoir des index/itérateurs/curseurs/... différents sur une même liste.
• Avoir plusieurs "vues" différentes d'une même liste (au passage, je n'ai jamais eu ce besoin, si c'est ce que tu entendais ici, aurais-tu un exemple concret ?).

Dans les trois cas, je ne vois pas d'impossibilité à fournir ce servir malgré l'encapsulation ni de difficulté particulière à le faire, je dirais même au contraire dans certains cas.

Après j'admets volontiers que dans certains cas particuliers un besoin spécifique ou une contrainte précise puisse amener le besoin d'implémenter de la sorte.
Mais dans le cas général, je ne vois pas de réelle plus-value à implémenter une liste comme étant un noeud, par contre j'y vois des inconvénients.