1 import java.util.NoSuchElementException;
2
3 /**
4 An implementation of a doubly linked list.
5 */
6 public class LinkedList
7 {
8 private Node first;
9 private Node last;
10
11 /**
12 Constructs an empty linked list.
13 */
14 public LinkedList()
15 {
16 first = null;
17 last = null;
18 }
19
20 /**
21 Returns the first element in the linked list.
22 @return the first element in the linked list
23 */
24 public Object getFirst()
25 {
26 if (first == null) { throw new NoSuchElementException(); }
27 return first.data;
28 }
29
30 /**
31 Removes the first element in the linked list.
32 @return the removed element
33 */
34 public Object removeFirst()
35 {
36 if (first == null) { throw new NoSuchElementException(); }
37 Object element = first.data;
38 first = first.next;
39 if (first == null) { last = null; } // List is now empty
40 else { first.previous = null; }
41 return element;
42 }
43
44 /**
45 Adds an element to the front of the linked list.
46 @param element the element to add
47 */
48 public void addFirst(Object element)
49 {
50 Node newNode = new Node();
51 newNode.data = element;
52 newNode.next = first;
53 newNode.previous = null;
54 if (first == null) { last = newNode; }
55 else { first.previous = newNode; }
56 first = newNode;
57 }
58
59 /**
60 Returns the last element in the linked list.
61 @return the last element in the linked list
62 */
63 public Object getLast()
64 {
65 if (last == null) { throw new NoSuchElementException(); }
66 return last.data;
67 }
68
69 /**
70 Removes the last element in the linked list.
71 @return the removed element
72 */
73 public Object removeLast()
74 {
75 if (last == null) { throw new NoSuchElementException(); }
76 Object element = last.data;
77 last = last.previous;
78 if (last == null) { first = null; } // List is now empty
79 else { last.next = null; }
80 return element;
81 }
82
83 /**
84 Adds an element to the back of the linked list.
85 @param element the element to add
86 */
87 public void addLast(Object element)
88 {
89 Node newNode = new Node();
90 newNode.data = element;
91 newNode.next = null;
92 newNode.previous = last;
93 if (last == null) { first = newNode; }
94 else { last.next = newNode; }
95 last = newNode;
96 }
97
98 /**
99 Returns an iterator for iterating through this list.
100 @return an iterator for iterating through this list
101 */
102 public ListIterator listIterator()
103 {
104 return new LinkedListIterator();
105 }
106
107 class Node
108 {
109 public Object data;
110 public Node next;
111 public Node previous;
112 }
113
114 class LinkedListIterator implements ListIterator
115 {
116 private Node position;
117 private boolean isAfterNext;
118 private boolean isAfterPrevious;
119
120 /**
121 Constructs an iterator that points to the front
122 of the linked list.
123 */
124 public LinkedListIterator()
125 {
126 position = null;
127 isAfterNext = false;
128 isAfterPrevious = false;
129 }
130
131 /**
132 Moves the iterator past the next element.
133 @return the traversed element
134 */
135 public Object next()
136 {
137 if (!hasNext()) { throw new NoSuchElementException(); }
138 isAfterNext = true;
139 isAfterPrevious = false;
140
141 if (position == null)
142 {
143 position = first;
144 }
145 else
146 {
147 position = position.next;
148 }
149
150 return position.data;
151 }
152
153 /**
154 Tests if there is an element after the iterator position.
155 @return true if there is an element after the iterator position
156 */
157 public boolean hasNext()
158 {
159 if (position == null)
160 {
161 return first != null;
162 }
163 else
164 {
165 return position.next != null;
166 }
167 }
168
169 /**
170 Moves the iterator before the previous element.
171 @return the traversed element
172 */
173 public Object previous()
174 {
175 if (!hasPrevious()) { throw new NoSuchElementException(); }
176 isAfterNext = false;
177 isAfterPrevious = true;
178
179 Object result = position.data;
180 position = position.previous;
181 return result;
182 }
183
184 /**
185 Tests if there is an element before the iterator position.
186 @return true if there is an element before the iterator position
187 */
188 public boolean hasPrevious()
189 {
190 return position != null;
191 }
192
193 /**
194 Adds an element before the iterator position
195 and moves the iterator past the inserted element.
196 @param element the element to add
197 */
198 public void add(Object element)
199 {
200 if (position == null)
201 {
202 addFirst(element);
203 position = first;
204 }
205 else if (position == last)
206 {
207 addLast(element);
208 position = last;
209 }
210 else
211 {
212 Node newNode = new Node();
213 newNode.data = element;
214 newNode.next = position.next;
215 newNode.next.previous = newNode;
216 position.next = newNode;
217 newNode.previous = position;
218 position = newNode;
219 }
220
221 isAfterNext = false;
222 isAfterPrevious = false;
223 }
224
225 /**
226 Removes the last traversed element. This method may
227 only be called after a call to the next() method.
228 */
229 public void remove()
230 {
231 Node positionToRemove = lastPosition();
232
233 if (positionToRemove == first)
234 {
235 removeFirst();
236 }
237 else if (positionToRemove == last)
238 {
239 removeLast();
240 }
241 else
242 {
243 positionToRemove.previous.next = positionToRemove.next;
244 positionToRemove.next.previous = positionToRemove.previous;
245 }
246
247 if (isAfterNext)
248 {
249 position = position.previous;
250 }
251
252 isAfterNext = false;
253 isAfterPrevious = false;
254 }
255
256 /**
257 Sets the last traversed element to a different value.
258 @param element the element to set
259 */
260 public void set(Object element)
261 {
262 Node positionToSet = lastPosition();
263 positionToSet.data = element;
264 }
265
266 /**
267 Returns the last node traversed by this iterator, or
268 throws an IllegalStateException if there wasn't an immediately
269 preceding call to next or previous.
270 @return the last traversed node
271 */
272 private Node lastPosition()
273 {
274 if (isAfterNext)
275 {
276 return position;
277 }
278 else if (isAfterPrevious)
279 {
280 if (position == null)
281 {
282 return first;
283 }
284 else
285 {
286 return position.next;
287 }
288 }
289 else { throw new IllegalStateException(); }
290 }
291 }
292 }