Discussion :

[Mornor]

Bonjour à tous !

Je me lance tout doucement dans les LinkedList, et je dois dire que j'ai un peu de mal à implémenter la méthode remove ...
J'ai fait le bout de code suivant, mais j'ai une erreur sur la ligne en commentaire, et je ne comprend pas d'ou elle vient. (NullPointerException).

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
 
public class MyLinkedList<E> extends AbstractList<E> implements List<E> 
{
        public E remove(int index) 
	{	// TODO
		E tmp = get(index); // On récupère l'objet à remplacer, via son index. 
		E nextInd = get(index + 1); // Idem avec l'objet suivant
		Node<E> nodeToRemove = new Node<E>(tmp); // On l'assigne à un Noeud
		Node<E> nextNode = new Node<E>(nextInd); 
		//nodeToRemove.getPrev().setNext(nextNode); 
		nodeToRemove.setElement(null); 			
 
		curSize--; 
 
		return tmp;		
	}
 
}

Les commentaires dans le code sont, je pense, assez explicite.

Les implémentations des méthodes getPrev(), getNext(), etc ... Sont correctes.

Quelqu'un pourrait-il m'expliquer d'ou viens cette faute ?

Un grand merci d'avance à ceux qui prendront le temps de me lire !

[joel.drigo]

Salut,

c'est dû à une confusion totale :

ceci

Code :

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

Node<E> nodeToRemove = new Node<E>(tmp); // On l'assigne à un Noeud

créé une nouvelle instance de Node, qui n'a aucun raison d'avoir un élément précédent.

d'ailleurs :

Code :

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

nodeToRemove.setElement(null);

ne manipulant qu'une nouvelle instance de Node qui n'a rien à voir avec celles que tu stockes dans ta liste chainée, ça n'effacera rien dans cette liste

ce qu'il faut que tu fasses, c'est récupérer l'instance de Node mémorisée dans ta liste chainée

[jdevbe]

Je suppose qu'il s'agit d'un exercice sinon la class java.util.LinkedList existe déjà !
Selon java doc, la class AbstractList est adaptée pour une implémentation basée "random access" (pe un array). Pour une implémentation type LinkedList, la class java.util.AbstractSequentialList est plus adaptée.
Mais sans doute l'exercice impose AbstractList ...

pour AbstractList , une piste (peu performante) est peut être quelque chose comme:

Code :

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

1
2
3
4
5
6
7
8
 
public E remove(int index) {
  E tmp = get(index);
  if (remove(tmp) {
    return tmp
  }
  return null;
}

[Mornor]

Merci de la réponse !

En fait, je pensais récupérer l'instance stockée dans la liste en faisant cela.
Même si j'avoue avoir été complètement perdu en me posant la question de la présence du new ....

J'ai essayer de trouver une autre méthode, mais je n'arrive pas à passer outre du fait que pour récupérer cette instance, je dois utiliser un Node, afin d'utiliser la méthode getElement().

Comment lier un Element à un Node ?

J'avoue ne pas bien comprendre la notion de Node, je me renseigne dans la littérature

Voici ce que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public E remove(int index) 
	{	// TODO
		E tmp = get(index); // On récupère l'objet à remplacer, via son index. 	
 
		Node<E> nodeToRem = null; 
		nodeToRem.getElement();	
 
 
		curSize--; 
 
		return tmp;		
	}

[jdevbe]

Comment lier un Element à un Node ?

J'avoue ne pas bien comprendre la notion de Node, je me renseigne dans la littérature

La class Node est une class que l'on ta fournie ?

Je suppose qu'elle est utilisée pour implémenter ta LinkedList et qu'elle contient un référence à un élément E et une référence vers le noeud Node suivant.
Dans ce cas, tu obtenir la référence du noeud précédent le noeud avec la référence à supprimer.

[joel.drigo]

Oublie les AbstractList ou AbstractSequentialList si tu dois implémenter une liste chainée dans le cadre d'un exercice, en particulier à partir de Node.

Ce que tu appelles Node est une classe qui permet de stocker une valeur (l'élément dont tu parles) et un lien vers l'élément suivant pour une liste chainée vers l'avant, ou chaque node est lié à son suivant, ou à rien pour le dernier (on pourrait avoir une liste chainée vers l'arrière, ou une liste doublement chaînée vers l'avant et vers l'arrière)

Les méthodes d'ajout (add), suppression(remove) et lecture (get) manipulent des nodes, se déplacent entre eux par leur(s) lien(s)

[Mornor]

Bonsoir,

Oui, la classe Node m'a été fournie.
Et elle contient effectivement toute les méthodes citées.

Néanmoins, je ne comprend pas le lien entre un node et un élément.
C'est pour cela que j'ai du mal à comprendre comment lié les deux ensemble afin de pouvoir récupérer l'instance effectivement contenue dans la LinkedList, via son index

[joel.drigo]

Tu peux peut être poster les sources de ces 2 classes, pour qu'on puisse mieux te guider...

[Mornor]

Pas de soucis !

Pour ce qui est de la classe Node :

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
24
25
26
27
28
29
 
public class Node<E> 
{
	private E element;
	private Node<E> prev;
	private Node<E> next;
 
	public Node(E item){
		this.element = item;
	}
	public E getElement() {
		return element;
	}
	public void setElement(E element) {
		this.element = element;
	}
	public Node<E> getPrev() {
		return prev;
	}
	public void setPrev(Node<E> prev) {
		this.prev = prev;
	}
	public Node<E> getNext() {
		return next;
	}
	public void setNext(Node<E> next) {
		this.next = next;
	}
}

Et pour la classe MyLinkedList :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
import java.util.AbstractList;
import java.util.Iterator;
import java.util.List;
 
public class MyLinkedList<E> extends AbstractList<E> implements List<E> {
	private Node<E> start;
	private Node<E> end;
	private int curSize;//Number of non-null element of the list
 
	public MyLinkedList(){
		start = new Node<E> (null);
		end=new Node<E>(null);
		start.setNext(end);
		end.setPrev(start);
		curSize=0;
	}
 
	public E get(int index) {
		if(index<0 || index>=size()){
			throw new IndexOutOfBoundsException();
		}
		Node<E> tmp = start.getNext();
		for(int i=0; i<index; i++){
			tmp=tmp.getNext();
		}
		return tmp.getElement();
	}
 
	public int size() {
		return this.curSize; 
	}
 
	public void add(int index, E item) {
		if(index<0 || index>size()){
			throw new IndexOutOfBoundsException();
		}
		Node<E> tmp = start;
		for(int i=0; i<index; i++){
			tmp=tmp.getNext(); //Tmp est le noeud avant index
		}
		//Création du nouveau noeud
		Node<E> newNode = new Node<E>(item);
		newNode.setElement(item);
		newNode.setPrev(tmp);
		newNode.setNext(tmp.getNext());
		newNode.getNext().setPrev(newNode);
		tmp.setNext(newNode);
		curSize++;
	}
 
	// Pourquoi le bug ? 
	public void print() 
	{
		for (Node n = start; n != null; n = n.getNext()) 
			System.out.print(n.getElement().toString());
		System.out.println("");
	}
 
	public E remove(int index) 
	{	
		return null; 
 
	}
}

[joel.drigo]

Il n'y a pas de classe Element alors... c'est bien ce que je disais l'élément c'est la valeur stockée (une liste, chainée ou pas, c'est une liste de valeurs)

Tu peux complètement t'inspirer de get() pour implémenter remove() :

1) chercher le node à supprimer en parcourant les nodes comme pour get
2) récuper le node précédent et le node suivant du node à supprimer trouvé, et refaire les liens suivant de node précédent et précédent de node suivant pour qu'ils pointent entre eux...

Une autre solution serait de faire un méthode intermédiaire, private, qui te permettent d'obtenir un node d'après son index (extraire donc cette partie de la méthode get() pour pouvoir l'appeler depuis la méthode get(), add(), ou remove(), et une méthode intermediaire pour lier 2 nodes entre eux (l'un est suivant de l'autre qui précède le premier...) : ça te fera des primitives qu'il suffit d'appeler pour implémenter get(), add() ou remove()

[Mornor]

Merci,

C'est ce que j'ai fais, mais j'ai toujours un problème. 2 en fait.
1. Dans la méthode add:

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
 
public void add(int index, E item) {
		if(index<0 || index>size()){
			throw new IndexOutOfBoundsException();
		}
		Node<E> tmp = start;
		for(int i=0; i<index; i++){
			tmp=tmp.getNext(); //Tmp est le noeud avant index
		}
		//Création du nouveau noeud
		Node<E> newNode = new Node<E>(item);
		newNode.setElement(item);
		newNode.setPrev(tmp);
		newNode.setNext(tmp.getNext());
		newNode.getNext().setPrev(newNode);
		tmp.setNext(newNode);
		curSize++;
	}

Dans la boucle, il est dit que tmp est le noeud *avant* index. Soit.
Disons que l'index est 3, et donc tmp est le node 2.

Code :

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

newNode.setPrev(tmp);

On setPrev sur le newMode en utilsant tmp. DONC newMode est *forcément* le node 3 (car son précédent est tmp, qui est 2)
Jusque là, tout va bien.
Mais après :

Code :

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

newNode.setNext(tmp.getNext());

On setNext le node après newNode en utlisant tmp.getNext().
Mais tmp est 2, donc getNext() renvoie 3 ce qui est ... le newNode lui même ?
Hell !
Ou est l'erreur dans mon raisonnement ?

2. Pour ce qui est de remove(), voici le code que j'ai fait, mais j'ai quand même un problème :

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
 
public E remove(int index) {	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException();
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
		tmp = tmp.getNext(); // tmp est le noeur *sur* l'index
 
		/*On relie le node suivant et précédent de tmp entre eux*/
		tmp.getNext().setPrev(tmp.getPrev()); 
		tmp.getPrev().setNext(tmp.getNext()); 
 
		return null; 		
	}

A la ligne

Code :

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

tmp = tmp.getNext(); // tmp est le noeur *sur* l'index

Pourriez-vous m'expliquer l'erreur de compréhension que je fait sur le premier problème ?

Tout grand merci pour l'aide déjà apportée.

[jdevbe]

Code :

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

1
2
3
4
 
newNode.setNext(tmp.getNext());
On setNext le node après newNode en utlisant tmp.getNext().
Mais tmp est 2, donc getNext() renvoie 3 ce qui est ... le newNode lui même ?

Ton raisonnement n'est pas exacte.
lorsque tu fait "newNode.setNext(tmp.getNext());", tmp.getNext désigne l'encien suivant de tmp qui sera le suivant newNode.

Pour plus de clarté on peux écrire:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
    Node<E> prevNode = tmp;
    Node<E> nextNode = tmp.getNext();
    //Création du nouveau noeud
    Node<E> newNode = new Node<E>(item);
    newNode.setElement(item);
    newNode.setPrev(prevNode);
    newNode.setNext(nextNode);
    //màj de prevNode
    prevNode.setNext(newNode);
    //màj de nextNode
    nextNode.setPrev(newNode);

Les états des noeud lors de l'insertion du premier noeud sont:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
    Liste vide:
    chainage next: [START(null)]->[END(null)]
    chainage prev: [END(null)]->[START(null)]
    Après recheche noeud avant index 0:
    tmp->[START(null)]    
    Après création du nouveau noeud:
    chainage next: [newNode(item)]->[END(null)]
                   [START(null)]->[END(null)]
    chainage prev: [newNode(item)]->[START(null)]
                   [END(null)]->[START(null)]
    après màj de prevNode et nextNode
    chainage next: [START(null)]->[newNode(item)]->[END(null)]
    chainage prev: [END(null)]->[newNode(item)]->[START(null)]

Pour la suppression il faut passer par les l'états des noeuds suivants:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
    Liste à avant suppression:
    chainage next: [START(null)]->[newNode(item)]->[END(null)]
    chainage prev: [END(null)]->[newNode(item)]->[START(null)]
    Après recheche du noeud index 0 et des noeuds suivant et précédent de ce noeud 0:
    tmp->[newNode(item)]
    prevNode->[START(null)]
    nextNode->[END(null)]  
    màj de prevNode et nextNode:
    chainage next: [START(null)]->[END(null)]
    chainage prev: [END(null)]->[START(null)]

Je te laisse coder cela...

[joel.drigo]

Salut,

dans le premier cas, l'erreur de raisonnement provient du fait que tu appliques un raisonnement par index à quelque chose qui n'est pas géré par index, mais par référence.

Tu as trouvé un tmp qui a un next

Code :

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

1
2
3
4
Node<E> newNode = new Node<E>(item);
newNode.setElement(item); // cette ligne ne sert à rien
newNode.setPrev(tmp); // tu modifies newNode
newNode.setNext(tmp.getNext()); // tu modifies newNode

tu n'as pas modifié tmp jusqu'ici
newNode.getNext().setPrev(newNode); // tu modifies le next de newNode qui est aussi le next de tmp, mais pas tmp

Code :

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

tmp.setNext(newNode);

tmp doit bien avoir pour suivant le nouveau

Ton problème 2 est le même problème de raisonnement.
Il faut juste que tu n'oublies pas de décrémenter cursize


Notes, qu'en plus tu as un nœud "bidon" qui est utilisé juste pour avoir un pointeur, et qui ne contient jamais d'élément. (start n'est pas le premier node de ta liste donc)

[Mornor]

Bonsoir,

J'ai donc fait cela.

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
24
25
26
 
public E remove(int index) 
	{	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException();
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
 
		E item = get(index); 
 
		Node<E> newNode = new Node<E>(item); 
		Node<E> prevNode = tmp; 
		Node<E> nextNode = tmp.getNext(); 
 
		prevNode.setNext(newNode.getNext()); 
		nextNode.setPrev(newNode.getPrev()); 
 
		curSize--; 
 
		return item; 
 
	}

Mais je sens qu'il y'a encore un problème ...
J'ai du mal avec le fait qu'il fasse créer un nouveau Node ... Pourquoi ? Pour récupérer l'élément ?

[joel.drigo]

Bonsoir,

J'ai donc fait cela.

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
24
25
26
 
public E remove(int index) 
	{	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException();
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
 
		E item = get(index); 
 
		Node<E> newNode = new Node<E>(item); 
		Node<E> prevNode = tmp; 
		Node<E> nextNode = tmp.getNext(); 
 
		prevNode.setNext(newNode.getNext()); 
		nextNode.setPrev(newNode.getPrev()); 
 
		curSize--; 
 
		return item; 
 
	}

Mais je sens qu'il y'a encore un problème ...
J'ai du mal avec le fait qu'il fasse créer un nouveau Node ... Pourquoi ?

Parce que pour supprimer, il ne faut pas créer de nouveau Node !

il suffit de chercher celui qu'on veut supprimer et de faire que son prec.next deviennent son next actuel et que son next.prec deviennent son prec actuel

[Mornor]

il suffit de chercher celui qu'on veut supprimer et de faire que son prec.next deviennent son next actuel et que son next.prec deviennent son prec actuel

Ça, pas de soucis, mais j'ai du mal à piger (comme vous vous en doutez surement) la position par référence et tout le bazar.

Pour moi, les étapes sont simples :
- On trouve le noeud à supprimer.
- L'élement précédent ce noeud, on le fait pointer vers l'élément suivant de ce noeud --> noeud.getPrev().setNext(noeud.getNext());
- L'élément suivant de ce noeud, on le fait pointer vers le noeud précédent --> noeud.getNext().setPrev(noeud.getPrev());

d'ou :

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
 
public E remove(int index) {	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException();
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
 
		Node<E> temporaire = tmp; 
		Node<E> prevNode = tmp.getPrev();
		Node<E> nextNode = tmp.getNext(); 
 
		temporaire.getPrev().setNext(temporaire.getNext()); 
		temporaire.getNext().setPrev(temporaire.getPrev());
 
		curSize--; 
 
		return (E) temporaire; 
 
}

Ou est l'étape que je saute ... ?

[Mornor]

Pour information,

Après toute les explications qui m'ont été données, et après 17 ans de recherches, j'ai trouvé

Grand merci à tous !!

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
24
25
26
27
28
 
public E remove(int index) {	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException("Erreur lors de la suppression");
 
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
 
		Node<E> temporaire = tmp.getNext(); // Le noeud se trouve *sur* l'index 
		Node<E> prevNode = temporaire.getPrev(); 
		Node<E> nextNode = temporaire.getNext();
 
		nextNode.setPrev(prevNode); 
		prevNode.setNext(nextNode); 
 
		temporaire.setElement(null); 
 
		// System.out.println(temporaire.getElement());
 
		curSize--; 
 
		return temporaire.getElement(); 
 
	}

[joel.drigo]

Pour information,

Après toute les explications qui m'ont été données, et après 17 ans de recherches, j'ai trouvé

Grand merci à tous !!

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
24
25
26
27
28
 
public E remove(int index) {	
		/*Test vérifiant la conformité de l'index*/
		if(index < 0 || index > size())
			throw new IndexOutOfBoundsException("Erreur lors de la suppression");
 
 
		/*Recupération du Node à supprimer*/
		Node<E> tmp = start; 
		for(int i = 0 ; i < index ; i++)
			tmp = tmp.getNext(); 
 
		Node<E> temporaire = tmp.getNext(); // Le noeud se trouve *sur* l'index 
		Node<E> prevNode = temporaire.getPrev(); 
		Node<E> nextNode = temporaire.getNext();
 
		nextNode.setPrev(prevNode); 
		prevNode.setNext(nextNode); 
 
		temporaire.setElement(null); 
 
		// System.out.println(temporaire.getElement());
 
		curSize--; 
 
		return temporaire.getElement(); 
 
	}

Cool

Enfin presque trouvée parce que tu ne devrais pas faire :

Code :

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

temporaire.setElement(null);

sinon ta méthode va toujours retourner null et pas l'élément supprimé.

Le node temporaire n'ayant normalement plus de lien dessus, il n'est pas absolument utile de le mettre à null (l'élément sera garbageable si la seule instance à avoir une référence dessus est cet instance de node)...

[Mornor]

Ok !

Encore merci de ton aide

Toute dernière question, je dois bien renvoyer :

Code :

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

return temporaire.getElement();

?

[joel.drigo]

Ok !

Encore merci de ton aide

Toute dernière question, je dois bien renvoyer :

Code :

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

return temporaire.getElement();

?

Oui ! Oui ! C'est justement pour ça que je t'ai dit qu'il ne fallait pas faire temporaire.setElement(null) (en tout cas pas avant d'avoir lu getElement()) : regardes ta classe Node : getElement() retourne element et setElement(null) met null dans cette variable. or la méthode remove(int) doit retourner l'élément effacé : si tu met null dans la variable qui contient l'élément effacé, avant de le lire, tu retournes pas l'élément effacé, mais null...