Suppression dans LinkedList

Version imprimable

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:

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 !

16/11/2013, 18h59
joel.drigo

Salut,

c'est dû à une confusion totale :

ceci

Code:

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:

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
16/11/2013, 21h11
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:

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

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:

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; }

16/11/2013, 21h32
jdevbe

Citation:

Envoyé par Mornor

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.
16/11/2013, 21h35
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)
16/11/2013, 21h37
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 ;)
16/11/2013, 21h48
joel.drigo

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

Pas de soucis !

Pour ce qui est de la classe Node :

Code:

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:

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; 
 
	}
}

16/11/2013, 22h04
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()

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:

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:

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:

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 ! :calim2:
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:

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:

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.

Code:

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:

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:

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:

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...

17/11/2013, 12h23
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:

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:

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)

Bonsoir,

J'ai donc fait cela.

Code:

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 ?

Citation:
Envoyé par Mornor
Bonsoir,

J'ai donc fait cela.
Code:

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

Citation:

Envoyé par joel.drigo

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:

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 ... ? :(

Pour information,

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

Grand merci à tous !!

Code:

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(); 
 
	}

Citation:
Envoyé par Mornor
Pour information,

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

Grand merci à tous !!
Code:

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 :D

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

Code:

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)...

18/11/2013, 19h09
Mornor

Ok !

Encore merci de ton aide :)

Toute dernière question, je dois bien renvoyer :

Code:

return temporaire.getElement();

?
18/11/2013, 19h15
joel.drigo

Citation:

Envoyé par Mornor

Ok !

Encore merci de ton aide :)

Toute dernière question, je dois bien renvoyer :

Code:

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...
19/11/2013, 14h34
Mornor

D'office ...

Merci à tous d'avoir pris le temps de répondre à mes (nombreuses) questions !
J'ai quand même fini par comprendre ce concept ... :D

Ciaooo les amis !