Liste doublement chainée

Liste doublement chainée - Java - Programmation

Marsh Posté le 09-08-2002 à 11:19:24    

...j'trouve pas dans le JDK, y a une liste doublement chainée ?
Genre, une liste dans laquelle on peut, à partir d'un élément, avoir l'élément précédent ou l'élément suivant.
ça dit qqch à qqn ?

Reply

Marsh Posté le 09-08-2002 à 11:19:24   

Reply

Marsh Posté le 09-08-2002 à 11:22:14    

je pense pas que ça existe mais ça doit pas etre mortel à implementer.
bete question (sans remettre en doute ton choix): c'est pour faire quoi?

Reply

Marsh Posté le 09-08-2002 à 11:29:42    

si si ca existe : java.util.LinkedList
 

Citation :

In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).

Reply

Marsh Posté le 09-08-2002 à 11:32:02    

autant pour moi :)

Reply

Marsh Posté le 09-08-2002 à 11:35:32    

--greg-- a écrit a écrit :

autant pour moi :)




 
je suis tombé dessus hier ! ;)

Reply

Marsh Posté le 09-08-2002 à 11:38:15    

benou a écrit a écrit :

 
 
je suis tombé dessus hier ! ;)



lol
euh
je vois pas bien à quoi ça peut servir par contre. concretement.
(enfin ptet que si j'y pensais 20 secondes, je trouverais :??:)

Reply

Marsh Posté le 09-08-2002 à 11:39:30    

pour certains algos ... ou pour de l'optimsation ou pour éviter de coder une liste chainée à la main ...
 
c'est clair que mio je m'en suis jamais servi ! ;)

Reply

Marsh Posté le 09-08-2002 à 11:47:16    

benou a écrit a écrit :

pour certains algos ... ou pour de l'optimsation ou pour éviter de coder une liste chainée à la main ...
 
c'est clair que mio je m'en suis jamais servi ! ;)



euh oui d'accord mais ce que je voulais demander c à quoi pouvait servir une liste doublement chainée
(pas de diplome powa:D)

Reply

Marsh Posté le 09-08-2002 à 11:48:06    

--greg-- a écrit a écrit :

lol
euh
je vois pas bien à quoi ça peut servir par contre. concretement.
(enfin ptet que si j'y pensais 20 secondes, je trouverais :??:)



A circuler dans les deux sens dans ta liste. Par contre dans le JDK, il n'existe pas de liste simplement chainée. :o


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 11:49:28    

Cherrytree a écrit a écrit :

A circuler dans les deux sens dans ta liste. Par contre dans le JDK, il n'existe pas de liste simplement chainée. :o  




 
Ouais, normalement, c ça, ms apparement LinkedList ne permet pas ça !  :(

Reply

Marsh Posté le 09-08-2002 à 11:49:28   

Reply

Marsh Posté le 09-08-2002 à 11:50:10    

Oups, g rien dit ! :D
ListIterator !
Génial.
Merci  :hello:

Reply

Marsh Posté le 09-08-2002 à 11:51:15    

--greg-- a écrit a écrit :

euh oui d'accord mais ce que je voulais demander c à quoi pouvait servir une liste doublement chainée
(pas de diplome powa:D)




 
c plus pratique quand t'as besoin de pouvoir parcourir les éléments dans les 2 sens.

Reply

Marsh Posté le 09-08-2002 à 11:56:57    

El_Gringo a écrit a écrit :

 
 
Ouais, normalement, c ça, ms apparement LinkedList ne permet pas ça !  :(  




si avec les iterator !

Reply

Marsh Posté le 09-08-2002 à 11:57:03    

Cherrytree a écrit a écrit :

A circuler dans les deux sens dans ta liste. Par contre dans le JDK, il n'existe pas de liste simplement chainée. :o  



:o j'ai dit "concrètement"

Reply

Marsh Posté le 09-08-2002 à 11:57:14    

El_Gringo a écrit a écrit :

Oups, g rien dit ! :D
ListIterator !
Génial.
Merci  :hello:  




oups maxi-grilled !

Reply

Marsh Posté le 09-08-2002 à 12:07:52    

--greg-- a écrit a écrit :

:o j'ai dit "concrètement"




 
Et bah, imagine, t'as 15 éléments ds ta liste.
Tu possèdes l'élément 11, et tu veux le 10, et bah la c utile ! :D
y a pas plus concret ! :D
Plus sérieusement, je sais pas vraiment, je "traduit" un truc écrit en C++ vers mon appli Java, alors en voyant une liste doublement chainée ds le truc C++, j'utilise tout simplement moi aussi une liste doublement chainée.

Reply

Marsh Posté le 09-08-2002 à 12:08:10    

J'pourrais t'en dire plus une fois que j'aurais avancé ds mon truc.

Reply

Marsh Posté le 09-08-2002 à 12:09:23    

El_Gringo a écrit a écrit :

 
 
Et bah, imagine, t'as 15 éléments ds ta liste.
Tu possèdes l'élément 11, et tu veux le 10, et bah la c utile ! :D
y a pas plus concret ! :D
Plus sérieusement, je sais pas vraiment, je "traduit" un truc écrit en C++ vers mon appli Java, alors en voyant une liste doublement chainée ds le truc C++, j'utilise tout simplement moi aussi une liste doublement chainée.
 




euh ouais
ça j'avais compris hein . c pas SUPER concret. je voulais dire "concretement", pas au niveau "code", mais au niveau "fonctionnalité". dans quel cas ça peut servir quoi. rah.

Reply

Marsh Posté le 09-08-2002 à 12:34:54    

--greg-- a écrit a écrit :

 
euh ouais
ça j'avais compris hein . c pas SUPER concret. je voulais dire "concretement", pas au niveau "code", mais au niveau "fonctionnalité". dans quel cas ça peut servir quoi. rah.



Parcours des noeuds d'un graphe ?


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 12:35:25    

si ta structure de données est propre tu dois pouvoir te débrouiller sans.


---------------
Just because you feel good does not make you right
Reply

Marsh Posté le 09-08-2002 à 12:43:05    

Cherrytree a écrit a écrit :

Parcours des noeuds d'un graphe ?



hmmoué ok.
enfin. ds un cas comme ça, il te faudrait qd meme une implementation spécialisée me semble. bref...

Reply

Marsh Posté le 09-08-2002 à 12:49:11    

--greg-- a écrit a écrit :

hmmoué ok.
enfin. ds un cas comme ça, il te faudrait qd meme une implementation spécialisée me semble. bref...



C'est sur. ça doit aussi pouvoir servir pour réaliser les chainages avant et arrière dans les systèmes experts. De m'en demandez pas plus, là, j'étale ma confiture.


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 13:57:07    

Dark : pas forcément....Genre, pour une fonctionnalité bête, du type affichage d'une liste de machins DANS LES DEUX SANS, et cyclique...ben...c'est 'achtement pratique..

Reply

Marsh Posté le 09-08-2002 à 13:59:16    

Cherrytree a écrit a écrit :

A circuler dans les deux sens dans ta liste. Par contre dans le JDK, il n'existe pas de liste simplement chainée. :o  




 
Pas de liste simplement chaînée???? BAh...tout ce qui implémente List, tu peux récupérer un Iterator dessus....
Alors Vector, ArrayList, etc...ben c'en est, non??

Reply

Marsh Posté le 09-08-2002 à 14:05:42    

gfive a écrit a écrit :

 
 
Pas de liste simplement chaînée???? BAh...tout ce qui implémente List, tu peux récupérer un Iterator dessus....
Alors Vector, ArrayList, etc...ben c'en est, non??



Ben non, c'est pas des Listes chaînées. Au sens fonctionnalités, ça marche pareil, mais pas au sens de l'implémentation. Voilà.
 
Vector et ArrayList, ce sont des tableaux qui ont la faculté de se copier dans un tableau de plus grande capacité automatiquement, que le tableau précédent est trop petit.


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 14:09:54    

ouais...bon.....mais je te merde, d'abord, voilà, c'est tout, et toc! :D

Reply

Marsh Posté le 09-08-2002 à 14:14:19    

Cherrytree a écrit a écrit :

A circuler dans les deux sens dans ta liste. Par contre dans le JDK, il n'existe pas de liste simplement chainée. :o  




 
...Qui peut le plus peut le moins ! Rien ne te force à utiliser le double chainage, et niveau perfs, j'pense pas qu'une référence en plus par noeud soit perceptible.

Reply

Marsh Posté le 09-08-2002 à 14:37:01    

El_Gringo a écrit a écrit :

 
 
...Qui peut le plus peut le moins ! Rien ne te force à utiliser le double chainage, et niveau perfs, j'pense pas qu'une référence en plus par noeud soit perceptible.



Ben si ta structure est plus lourde et doit faire des références supplémentaires en cas d'ajout, suppression.


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 14:37:33    

gfive a écrit a écrit :

ouais...bon.....mais je te merde, d'abord, voilà, c'est tout, et toc! :D



:lol: Mauvais joueur ! :D


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 14:42:00    

voui, et alors! :p

Reply

Marsh Posté le 09-08-2002 à 14:44:10    

gfive a écrit a écrit :

voui, et alors! :p




 
Ho, viens on y pète sa gueule !? :D

Reply

Marsh Posté le 09-08-2002 à 14:45:09    

El_Gringo a écrit a écrit :

 
 
Ho, viens on y pète sa gueule !? :D



Bien par là petit. [:cherrytree2] maîtrise la Force.


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 16:10:58    

Cherrytree a écrit a écrit :

Ben si ta structure est plus lourde et doit faire des références supplémentaires en cas d'ajout, suppression.



Oui mais ;) Si t'as par exemple un pointeur qui se baladent de gauche à droite (et de droite à gauche) pour je ne sais quelle raison (j'ai déjà vu ca dans un buddy system -> gestion de mémoire je crois... y a longtemps :pt1cable:)... et que tu dois éliminer l'élèment référencé par le pointeur -> tu fais en sorte que le prédecesseur référence l'élèment suivant le pointeur et vice versa (le suivant référence le prédecesseur). Donc l'élèment en question ne sera plus dans la liste et pourra être garbage collecté. Avec une LinkedList normale tu devras faire une iteration supplémentaire pour  trouver le prédecesseur (et mettre les références à jour).
Enfin... y a que quand tu fais des iterations dans les 2 senses que le DoublyLinkedList a de l'intèrêt (-> au sinon tu pourrais utiliser un pointeur supplémentaire qui garde le prédecesseur).


---------------
Belgian Connection
Reply

Marsh Posté le 09-08-2002 à 16:26:42    

:heink: Si j'ai bien compris, t'es en train d'essayer de m'expliquer ce qu'est une liste doublement chaînée ?! ?! ?! [:zebra33]


---------------
Le site de ma maman
Reply

Marsh Posté le 09-08-2002 à 16:27:59    

MelloW a écrit a écrit :

Oui mais ;) Si t'as par exemple un pointeur qui se baladent de gauche à droite (et de droite à gauche) pour je ne sais quelle raison (j'ai déjà vu ca dans un buddy system -> gestion de mémoire je crois... y a longtemps :pt1cable:)... et que tu dois éliminer l'élèment référencé par le pointeur -> tu fais en sorte que le prédecesseur référence l'élèment suivant le pointeur et vice versa (le suivant référence le prédecesseur). Donc l'élèment en question ne sera plus dans la liste et pourra être garbage collecté. Avec une LinkedList normale tu devras faire une iteration supplémentaire pour  trouver le prédecesseur (et mettre les références à jour).
Enfin... y a que quand tu fais des iterations dans les 2 senses que le DoublyLinkedList a de l'intèrêt (-> au sinon tu pourrais utiliser un pointeur supplémentaire qui garde le prédecesseur).




 
Surement très juste, ms t à coté ! :D
Justement, DoublyLinkedList n'existe pas. C'est LinkedList qui est une liste doublement chainée. CherryTree se plaignait de la non existance de liste simplement chainée dans le JDK.
Parce qu'en fait il sait pas programmer une liste chainée ! (Rooh l'autre, hé ! :D)


Message édité par El_gringo le 09-08-2002 à 16:28:17
Reply

Marsh Posté le 09-08-2002 à 16:36:34    

:pt1cable: comprend plus rien là :D
un linkedlist -> chaque élèment a un pointeur vers le prochain
une doublylinkedlist -> vers le prédecesseur et vers le prochain
enfin c'est comme ca dans les cours d'algo et de "data structures"
:pt1cable: comprends mieux maintenant ;)
Sorry :D


---------------
Belgian Connection
Reply

Marsh Posté le 09-08-2002 à 16:44:59    

El_Gringo a écrit a écrit :

 
 
Surement très juste, ms t à coté ! :D
Justement, DoublyLinkedList n'existe pas. C'est LinkedList qui est une liste doublement chainée. CherryTree se plaignait de la non existance de liste simplement chainée dans le JDK.
Parce qu'en fait il sait pas programmer une liste chainée ! (Rooh l'autre, hé ! :D)



Heureusement que tu blagues, petit père. :D


---------------
Le site de ma maman
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed