Discussion :

[nuriel2]

Salut,

J'ai vu sur un blog quelque part une implementation maison de LinkedList, et j'ai decide de faire pareil pour me tester. J'ai juste repris le nom des methodes dans le blog. Avez vous des critiques/remarques ou voyez vous des bugs ? J'ai egalement ecrit un version parametree (ci-dessous, la version non parametree etant tres similaire). Tous les commentaires me permettant d'ameliorer ce code sont bien venus.

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
/**
 * This class represents a single Node in the custom linked list.
 */
 
package sandrew.linkedlist;
 
public class NodeGeneric<E> {
	/*
	 * Pointer to the current element
	 */
	private E currentElement;
 
	/*
	 * Pointer to the next element
	 */
	private NodeGeneric<E> nextElement;
 
	/**
         * Builds a new node by providing the current element and a pointer to the next 
         * @param currentElement element contained in the node
         * @param nextElement pointer to the next element
         */
	public NodeGeneric(E currentElement, NodeGeneric<E> nextElement) {
		this.currentElement = currentElement;
		this.nextElement = nextElement;
	}
 
	/**
         * Returns the element in the node
         * @return the element in the node
         */
	public E getCurrentElement() {
		return currentElement;
	}
 
	/**
         * Returns a pointer toward the next node
         * @return A pointer toward the next node
         */
	public NodeGeneric<E> getNextElement() {
		return nextElement;
	}
 
	/**
         * Updates the pointer the current node is pointing to
         * @param nextElement Node the current node should be pointing to.
         */
	public void setNextElement(NodeGeneric<E> nextElement) {
		this.nextElement = nextElement;
	}
 
	/**
         * Updates the element contained in the node with currentElement
         * @param currentElement value the element contained in the node 
         * should be updated to.
         */
	public void setCurrentElement(E currentElement) {
		this.currentElement = currentElement;
	}
}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
/**
 * This class represents a simple linked list, supporting all basic operations
 */
 
package sandrew.linkedlist;
 
public class SimpleLinkedListGeneric<E> {
	/*
	 * Pointer to the first node
	 */
	private NodeGeneric<E> firstNode;
 
	/*
	 * Current size of the list
	 */
	private int size;
 
	/**
         * Initializing the first node to null and the size to 0
         */
	public SimpleLinkedListGeneric() {
		firstNode = null;
		size = 0;
	}
 
	public int getSize() {
		return size;
	}
 
	public boolean isEmpty() {
		return size <= 0;
	}
 
	/**
         * Returns the element at the given position (0 based).
         * If the position is negative or greater than the size of the list
         * an ArrayIndexOutOfBoundsException is raised.
         * 
         * @param position Position of the element searched
         * @return The element at the given position
         * @throws ArrayIndexOutOfBoundsException If the position is negative or
         * greater or equal to the size of the list
         */
	public NodeGeneric<E> getElementAt(int position) throws ArrayIndexOutOfBoundsException {
		if(position < 0 || position >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
 
		/*Starting off from the first node, and iterating until we reach the
		 * one searched
		 */
		NodeGeneric<E> tempNode = firstNode;
 
		for(int i = 0; i < position; i++) {
			tempNode = tempNode.getNextElement();
		}
 
		return tempNode;
	}
 
	/**
         * Returns the last element of the list (zero based)
         * 
         * @return The last element of the list
         * @throws ArrayIndexOutOfBoundsException If the list is empty
         */
	public NodeGeneric<E> getLastElement() throws ArrayIndexOutOfBoundsException {
		return getElementAt(size - 1);
	}
 
	/**
         * Returns the first node of the list, or null if the list is empty
         * 
         * @return The first node of the list, or null if the list is empty
         */
	public NodeGeneric<E> getFirstElement() {
		return firstNode;
	}
 
	/**
         * Insert an element at a given position
         * 
         * @param position POsition where the element should be inserted. Zero based
         * @param o Element to be inserted.
         * @throws ArrayIndexOutOfBoundsException. If the position is negative or
         * is greater than the list size.
         */
	public void insertAt(int position, E o) throws ArrayIndexOutOfBoundsException {
		NodeGeneric<E> currentElement = null;
 
		/*
		 * We can add an element at the position size.
		 */
 
		if(position > size || position < 0) {
			throw new ArrayIndexOutOfBoundsException();
		}
 
		/*
		 * Inserting at the first position if the list is empty
		 * or if this is actually the position requested.
		 */
		if(position == 0 || firstNode == null) {
			if(firstNode == null) {
				currentElement = new NodeGeneric<E>(o, null);
				firstNode = currentElement;
			} else {
				currentElement = new NodeGeneric<E>(o, firstNode);
				firstNode = currentElement;
			}
		} else if (position == size) { //Inserting at the last position
			currentElement = new NodeGeneric<E>(o, null);
			NodeGeneric<E> previousElement = getLastElement();
			previousElement.setNextElement(currentElement);
		} else {
			/*First going to the previous element, saving the next element,
			 * and inserting the current one inbetween.
			 */
			NodeGeneric<E> previousElement = getElementAt(position - 1);
			NodeGeneric<E> nextElement = previousElement.getNextElement();
			currentElement = new NodeGeneric<E>(o, nextElement);
			previousElement.setNextElement(currentElement);
		}
 
		size++;
	}
 
	/**
         * Adds a node at the last position of the list. The pointer to
         * the next element will be set to null. Note that this method
         * is equivalent to call insertAt with the size as the position parameter.
         * @param o Element to be added
         */
	public void insertAtLast(E o) throws ArrayIndexOutOfBoundsException {
		insertAt(size, o);
	}
 
	/**
         * Adds a node at the first position of the list. Zero based.
         * @param o Element to be added.
         */
	public void insertAtFirst(E o) {
		insertAt(0, o);
	}
 
	/**
         * Adds a node at the last position
         * @param o Element to be added
         */
	public void add(E o) {
		insertAtLast(o);
	}
 
	/**
         * Removes the node at the given position and returns it.
         * 
         * @param position Position of the element to be removed
         * @return The removed node or null if the list is empty.
         * @throws ArrayIndexOutOfBoundsException If the position is negative or
         * is greater or equal to the size of the list
         */
	public NodeGeneric<E> removeElementAt(int position) throws ArrayIndexOutOfBoundsException {
		NodeGeneric<E> currentElement = null;
 
		if(position < 0 || position >= size) {
			throw new ArrayIndexOutOfBoundsException();
		}
 
		if(isEmpty()) {
			return null;
		}
 
		if(position == 0) {
			/*
			 * Changing the firstNode pointer to the next element.
			 * Could also make the current element's next element point to null
			 * But this is not critical at the moment.
			 */
			currentElement = firstNode;
			firstNode = firstNode.getNextElement();
		} else if(position == (size - 1)) {
			/*
			 * Getting the element before the last, saving the pointer
			 * and making the previous element the last by setting
			 * its next to null.
			 */
			NodeGeneric<E> previousElement = getElementAt(position - 1);
			currentElement = previousElement.getNextElement();
			previousElement.setNextElement(null);
		} else {
			/*
			 * Getting the previous element, saving the next one
			 * and then removing the current element before
			 * connecting previous and next elements.
			 */
			NodeGeneric<E> previousElement = getElementAt(position - 1);
			currentElement = previousElement.getNextElement();
			NodeGeneric<E> nextElement = currentElement.getNextElement();
			previousElement.setNextElement(nextElement);
		}
 
		size--;
 
		return currentElement;
	}
 
	/**
         * Removes and returns the first element.
         * @return the first element.
         */
	public NodeGeneric<E> removeFirst() {
		return removeElementAt(0);
	}
 
	/**
         * Removes the last element. Note that this is equivalent to call
         * the method removeElementAt with size - 1 as the position paramater.
         * 
         * @return the last element
         */
	public NodeGeneric<E> removeLast() {
		return removeElementAt(size - 1);
	}
}

J'y ajoute mes sources et quelques tests.

Merci

Nuriel

[tchize_]

Il existe déjà une interface List dans java (et une implémentation LinkedList). Si vous désirez créer votre propres List, l est judicieux, pour l'interopérabilité avec le reste du code, d'implémenter cette interface

Aussi, comme NodeGeneric n'est utilisé que par la linkedlist en interne, a
autant en faire une classe interne privée

Code :

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

1
2
3
4
5
6
7
8
9
package sandrew.linkedlist;
 
public class SimpleLinkedListGeneric<E> {
    private static  class NodeGeneric<E> {
        //.......
    }
 
    //......
}

Sinon, pas de faute apparente dans le code, implémentation propre, rien de chocant autre que mentionné plus haut.