1 /*
2 * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 /**
29 * Linked list implementation of the {@code List} interface.
30 * Implements all optional list operations, and permits all elements
31 * (including {@code null}). In addition to implementing the {@code
32 * List} interface, the {@code LinkedList} class provides uniformly
33 * named methods to {@code get}, {@code remove} and {@code add} an
34 * element at the beginning (<i>operation</i>{@code First}) and end
35 * (<i>operation</i>{@code Last}) of the list. These operations allow
36 * linked lists to be used as a stack, {@linkplain Queue queue}, or
37 * {@linkplain Deque double-ended queue}.
38 *
39 * <p>The class implements the {@code Deque} interface, providing
40 * first-in-first-out queue operations for {@code add},
41 * {@code poll}, along with other stack and deque operations.
42 *
43 * <p>All of the operations perform as could be expected for a doubly-linked
44 * list. Operations that index into the list will traverse the list from
45 * the beginning or the end, whichever is closer to the specified index.
46 *
47 * <p><strong>Note that this implementation is not synchronized.</strong>
48 * If multiple threads access a linked list concurrently, and at least
49 * one of the threads modifies the list structurally, it <i>must</i> be
50 * synchronized externally. (A structural modification is any operation
51 * that adds or deletes one or more elements; merely setting the value of
52 * an element is not a structural modification.) This is typically
53 * accomplished by synchronizing on some object that naturally
54 * encapsulates the list.
55 *
56 * If no such object exists, the list should be "wrapped" using the
57 * {@link Collections#synchronizedList Collections.synchronizedList}
58 * method. This is best done at creation time, to prevent accidental
59 * unsynchronized access to the list:<pre>
60 * List list = Collections.synchronizedList(new LinkedList(...));</pre>
61 *
62 * <p>The iterators returned by this class's {@code iterator} and
63 * {@code listIterator} methods are <i>fail-fast</i>: if the list is
64 * structurally modified at any time after the iterator is created, in
65 * any way except through the Iterator's own {@code remove} or
66 * {@code add} methods, the iterator will throw a {@link
67 * ConcurrentModificationException}. Thus, in the face of concurrent
68 * modification, the iterator fails quickly and cleanly, rather than
69 * risking arbitrary, non-deterministic behavior at an undetermined
70 * time in the future.
71 *
72 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
73 * as it is, generally speaking, impossible to make any hard guarantees in the
74 * presence of unsynchronized concurrent modification. Fail-fast iterators
75 * throw {@code ConcurrentModificationException} on a best-effort basis.
76 * Therefore, it would be wrong to write a program that depended on this
77 * exception for its correctness: <i>the fail-fast behavior of iterators
78 * should be used only to detect bugs.</i>
79 *
80 * <p>This class is a member of the
81 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
82 * Java Collections Framework</a>.
83 *
84 * @author Josh Bloch
85 * @see List
86 * @see ArrayList
87 * @since 1.2
88 * @param <E> the type of elements held in this collection
89 */
90
91 public class LinkedList<E>
92 extends AbstractSequentialList<E>
93 implements List<E>, Deque<E>, Cloneable, java.io.Serializable
94 {
95 transient int size = 0;
96
97 /**
98 * Pointer to first node.
99 * Invariant: (first == null && last == null) ||
100 * (first.prev == null && first.item != null)
101 */
102 transient Node<E> first;
103
104 /**
105 * Pointer to last node.
106 * Invariant: (first == null && last == null) ||
107 * (last.next == null && last.item != null)
108 */
109 transient Node<E> last;
110
111 /**
112 * Constructs an empty list.
113 */
114 public LinkedList() {
115 }
116
117 /**
118 * Constructs a list containing the elements of the specified
119 * collection, in the order they are returned by the collection's
120 * iterator.
121 *
122 * @param c the collection whose elements are to be placed into this list
123 * @throws NullPointerException if the specified collection is null
124 */
125 public LinkedList(Collection<? extends E> c) {
126 this();
127 addAll(c);
128 }
129
130 /**
131 * Links e as first element.
132 */
133 private void linkFirst(E e) {
134 final Node<E> f = first;
135 final Node<E> newNode = new Node<E>(null, e, f);
136 first = newNode;
137 if (f == null)
138 last = newNode;
139 else
140 f.prev = newNode;
141 size++;
142 modCount++;
143 }
144
145 /**
146 * Links e as last element.
147 */
148 void linkLast(E e) {
149 final Node<E> l = last;
150 final Node<E> newNode = new Node<E>(l, e, null);
151 last = newNode;
152 if (l == null)
153 first = newNode;
154 else
155 l.next = newNode;
156 size++;
157 modCount++;
158 }
159
160 /**
161 * Inserts element e before non-null Node succ.
162 */
163 void linkBefore(E e, Node<E> succ) {
164 // assert succ != null;
165 final Node<E> pred = succ.prev;
166 final Node<E> newNode = new Node<E>(pred, e, succ);
167 succ.prev = newNode;
168 if (pred == null)
169 first = newNode;
170 else
171 pred.next = newNode;
172 size++;
173 modCount++;
174 }
175
176 /**
177 * Unlinks non-null first node f.
178 */
179 private E unlinkFirst(Node<E> f) {
180 // assert f == first && f != null;
181 final E element = f.item;
182 final Node<E> next = f.next;
183 f.item = null;
184 f.next = null; // help GC
185 first = next;
186 if (next == null)
187 last = null;
188 else
189 next.prev = null;
190 size--;
191 modCount++;
192 return element;
193 }
194
195 /**
196 * Unlinks non-null last node l.
197 */
198 private E unlinkLast(Node<E> l) {
199 // assert l == last && l != null;
200 final E element = l.item;
201 final Node<E> prev = l.prev;
202 l.item = null;
203 l.prev = null; // help GC
204 last = prev;
205 if (prev == null)
206 first = null;
207 else
208 prev.next = null;
209 size--;
210 modCount++;
211 return element;
212 }
213
214 /**
215 * Unlinks non-null node x.
216 */
217 E unlink(Node<E> x) {
218 // assert x != null;
219 final E element = x.item;
220 final Node<E> next = x.next;
221 final Node<E> prev = x.prev;
222
223 if (prev == null) {
224 first = next;
225 } else {
226 prev.next = next;
227 x.prev = null;
228 }
229
230 if (next == null) {
231 last = prev;
232 } else {
233 next.prev = prev;
234 x.next = null;
235 }
236
237 x.item = null;
238 size--;
239 modCount++;
240 return element;
241 }
242
243 /**
244 * Returns the first element in this list.
245 *
246 * @return the first element in this list
247 * @throws NoSuchElementException if this list is empty
248 */
249 public E getFirst() {
250 final Node<E> f = first;
251 if (f == null)
252 throw new NoSuchElementException();
253 return f.item;
254 }
255
256 /**
257 * Returns the last element in this list.
258 *
259 * @return the last element in this list
260 * @throws NoSuchElementException if this list is empty
261 */
262 public E getLast() {
263 final Node<E> l = last;
264 if (l == null)
265 throw new NoSuchElementException();
266 return l.item;
267 }
268
269 /**
270 * Removes and returns the first element from this list.
271 *
272 * @return the first element from this list
273 * @throws NoSuchElementException if this list is empty
274 */
275 public E removeFirst() {
276 final Node<E> f = first;
277 if (f == null)
278 throw new NoSuchElementException();
279 return unlinkFirst(f);
280 }
281
282 /**
283 * Removes and returns the last element from this list.
284 *
285 * @return the last element from this list
286 * @throws NoSuchElementException if this list is empty
287 */
288 public E removeLast() {
289 final Node<E> l = last;
290 if (l == null)
291 throw new NoSuchElementException();
292 return unlinkLast(l);
293 }
294
295 /**
296 * Inserts the specified element at the beginning of this list.
297 *
298 * @param e the element to add
299 */
300 public void addFirst(E e) {
301 linkFirst(e);
302 }
303
304 /**
305 * Appends the specified element to the end of this list.
306 *
307 * <p>This method is equivalent to {@link #add}.
308 *
309 * @param e the element to add
310 */
311 public void addLast(E e) {
312 linkLast(e);
313 }
314
315 /**
316 * Returns {@code true} if this list contains the specified element.
317 * More formally, returns {@code true} if and only if this list contains
318 * at least one element {@code e} such that
319 * <tt>(o==null ? e==null : o.equals(e))</tt>.
320 *
321 * @param o element whose presence in this list is to be tested
322 * @return {@code true} if this list contains the specified element
323 */
324 public boolean contains(Object o) {
325 return indexOf(o) != -1;
326 }
327
328 /**
329 * Returns the number of elements in this list.
330 *
331 * @return the number of elements in this list
332 */
333 public int size() {
334 return size;
335 }
336
337 /**
338 * Appends the specified element to the end of this list.
339 *
340 * <p>This method is equivalent to {@link #addLast}.
341 *
342 * @param e element to be appended to this list
343 * @return {@code true} (as specified by {@link Collection#add})
344 */
345 public boolean add(E e) {
346 linkLast(e);
347 return true;
348 }
349
350 /**
351 * Removes the first occurrence of the specified element from this list,
352 * if it is present. If this list does not contain the element, it is
353 * unchanged. More formally, removes the element with the lowest index
354 * {@code i} such that
355 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
356 * (if such an element exists). Returns {@code true} if this list
357 * contained the specified element (or equivalently, if this list
358 * changed as a result of the call).
359 *
360 * @param o element to be removed from this list, if present
361 * @return {@code true} if this list contained the specified element
362 */
363 public boolean remove(Object o) {
364 if (o == null) {
365 for (Node<E> x = first; x != null; x = x.next) {
366 if (x.item == null) {
367 unlink(x);
368 return true;
369 }
370 }
371 } else {
372 for (Node<E> x = first; x != null; x = x.next) {
373 if (o.equals(x.item)) {
374 unlink(x);
375 return true;
376 }
377 }
378 }
379 return false;
380 }
381
382 /**
383 * Appends all of the elements in the specified collection to the end of
384 * this list, in the order that they are returned by the specified
385 * collection's iterator. The behavior of this operation is undefined if
386 * the specified collection is modified while the operation is in
387 * progress. (Note that this will occur if the specified collection is
388 * this list, and it's nonempty.)
389 *
390 * @param c collection containing elements to be added to this list
391 * @return {@code true} if this list changed as a result of the call
392 * @throws NullPointerException if the specified collection is null
393 */
394 public boolean addAll(Collection<? extends E> c) {
395 return addAll(size, c);
396 }
397
398 /**
399 * Inserts all of the elements in the specified collection into this
400 * list, starting at the specified position. Shifts the element
401 * currently at that position (if any) and any subsequent elements to
402 * the right (increases their indices). The new elements will appear
403 * in the list in the order that they are returned by the
404 * specified collection's iterator.
405 *
406 * @param index index at which to insert the first element
407 * from the specified collection
408 * @param c collection containing elements to be added to this list
409 * @return {@code true} if this list changed as a result of the call
410 * @throws IndexOutOfBoundsException {@inheritDoc}
411 * @throws NullPointerException if the specified collection is null
412 */
413 public boolean addAll(int index, Collection<? extends E> c) {
414 checkPositionIndex(index);
415
416 Object[] a = c.toArray();
417 int numNew = a.length;
418 if (numNew == 0)
419 return false;
420
421 Node<E> pred, succ;
422 if (index == size) {
423 succ = null;
424 pred = last;
425 } else {
426 succ = node(index);
427 pred = succ.prev;
428 }
429
430 for (Object o : a) {
431 @SuppressWarnings("unchecked") E e = (E) o;
432 Node<E> newNode = new Node<E>(pred, e, null);
433 if (pred == null)
434 first = newNode;
435 else
436 pred.next = newNode;
437 pred = newNode;
438 }
439
440 if (succ == null) {
441 last = pred;
442 } else {
443 pred.next = succ;
444 succ.prev = pred;
445 }
446
447 size += numNew;
448 modCount++;
449 return true;
450 }
451
452 /**
453 * Removes all of the elements from this list.
454 * The list will be empty after this call returns.
455 */
456 public void clear() {
457 // Clearing all of the links between nodes is "unnecessary", but:
458 // - helps a generational GC if the discarded nodes inhabit
459 // more than one generation
460 // - is sure to free memory even if there is a reachable Iterator
461 for (Node<E> x = first; x != null; ) {
462 Node<E> next = x.next;
463 x.item = null;
464 x.next = null;
465 x.prev = null;
466 x = next;
467 }
468 first = last = null;
469 size = 0;
470 modCount++;
471 }
472
473
474 // Positional Access Operations
475
476 /**
477 * Returns the element at the specified position in this list.
478 *
479 * @param index index of the element to return
480 * @return the element at the specified position in this list
481 * @throws IndexOutOfBoundsException {@inheritDoc}
482 */
483 public E get(int index) {
484 checkElementIndex(index);
485 return node(index).item;
486 }
487
488 /**
489 * Replaces the element at the specified position in this list with the
490 * specified element.
491 *
492 * @param index index of the element to replace
493 * @param element element to be stored at the specified position
494 * @return the element previously at the specified position
495 * @throws IndexOutOfBoundsException {@inheritDoc}
496 */
497 public E set(int index, E element) {
498 checkElementIndex(index);
499 Node<E> x = node(index);
500 E oldVal = x.item;
501 x.item = element;
502 return oldVal;
503 }
504
505 /**
506 * Inserts the specified element at the specified position in this list.
507 * Shifts the element currently at that position (if any) and any
508 * subsequent elements to the right (adds one to their indices).
509 *
510 * @param index index at which the specified element is to be inserted
511 * @param element element to be inserted
512 * @throws IndexOutOfBoundsException {@inheritDoc}
513 */
514 public void add(int index, E element) {
515 checkPositionIndex(index);
516
517 if (index == size)
518 linkLast(element);
519 else
520 linkBefore(element, node(index));
521 }
522
523 /**
524 * Removes the element at the specified position in this list. Shifts any
525 * subsequent elements to the left (subtracts one from their indices).
526 * Returns the element that was removed from the list.
527 *
528 * @param index the index of the element to be removed
529 * @return the element previously at the specified position
530 * @throws IndexOutOfBoundsException {@inheritDoc}
531 */
532 public E remove(int index) {
533 checkElementIndex(index);
534 return unlink(node(index));
535 }
536
537 /**
538 * Tells if the argument is the index of an existing element.
539 */
540 private boolean isElementIndex(int index) {
541 return index >= 0 && index < size;
542 }
543
544 /**
545 * Tells if the argument is the index of a valid position for an
546 * iterator or an add operation.
547 */
548 private boolean isPositionIndex(int index) {
549 return index >= 0 && index <= size;
550 }
551
552 /**
553 * Constructs an IndexOutOfBoundsException detail message.
554 * Of the many possible refactorings of the error handling code,
555 * this "outlining" performs best with both server and client VMs.
556 */
557 private String outOfBoundsMsg(int index) {
558 return "Index: "+index+", Size: "+size;
559 }
560
561 private void checkElementIndex(int index) {
562 if (!isElementIndex(index))
563 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
564 }
565
566 private void checkPositionIndex(int index) {
567 if (!isPositionIndex(index))
568 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
569 }
570
571 /**
572 * Returns the (non-null) Node at the specified element index.
573 */
574 Node<E> node(int index) {
575 // assert isElementIndex(index);
576
577 if (index < (size >> 1)) {
578 Node<E> x = first;
579 for (int i = 0; i < index; i++)
580 x = x.next;
581 return x;
582 } else {
583 Node<E> x = last;
584 for (int i = size - 1; i > index; i--)
585 x = x.prev;
586 return x;
587 }
588 }
589
590 // Search Operations
591
592 /**
593 * Returns the index of the first occurrence of the specified element
594 * in this list, or -1 if this list does not contain the element.
595 * More formally, returns the lowest index {@code i} such that
596 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
597 * or -1 if there is no such index.
598 *
599 * @param o element to search for
600 * @return the index of the first occurrence of the specified element in
601 * this list, or -1 if this list does not contain the element
602 */
603 public int indexOf(Object o) {
604 int index = 0;
605 if (o == null) {
606 for (Node<E> x = first; x != null; x = x.next) {
607 if (x.item == null)
608 return index;
609 index++;
610 }
611 } else {
612 for (Node<E> x = first; x != null; x = x.next) {
613 if (o.equals(x.item))
614 return index;
615 index++;
616 }
617 }
618 return -1;
619 }
620
621 /**
622 * Returns the index of the last occurrence of the specified element
623 * in this list, or -1 if this list does not contain the element.
624 * More formally, returns the highest index {@code i} such that
625 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
626 * or -1 if there is no such index.
627 *
628 * @param o element to search for
629 * @return the index of the last occurrence of the specified element in
630 * this list, or -1 if this list does not contain the element
631 */
632 public int lastIndexOf(Object o) {
633 int index = size;
634 if (o == null) {
635 for (Node<E> x = last; x != null; x = x.prev) {
636 index--;
637 if (x.item == null)
638 return index;
639 }
640 } else {
641 for (Node<E> x = last; x != null; x = x.prev) {
642 index--;
643 if (o.equals(x.item))
644 return index;
645 }
646 }
647 return -1;
648 }
649
650 // Queue operations.
651
652 /**
653 * Retrieves, but does not remove, the head (first element) of this list.
654 *
655 * @return the head of this list, or {@code null} if this list is empty
656 * @since 1.5
657 */
658 public E peek() {
659 final Node<E> f = first;
660 return (f == null) ? null : f.item;
661 }
662
663 /**
664 * Retrieves, but does not remove, the head (first element) of this list.
665 *
666 * @return the head of this list
667 * @throws NoSuchElementException if this list is empty
668 * @since 1.5
669 */
670 public E element() {
671 return getFirst();
672 }
673
674 /**
675 * Retrieves and removes the head (first element) of this list.
676 *
677 * @return the head of this list, or {@code null} if this list is empty
678 * @since 1.5
679 */
680 public E poll() {
681 final Node<E> f = first;
682 return (f == null) ? null : unlinkFirst(f);
683 }
684
685 /**
686 * Retrieves and removes the head (first element) of this list.
687 *
688 * @return the head of this list
689 * @throws NoSuchElementException if this list is empty
690 * @since 1.5
691 */
692 public E remove() {
693 return removeFirst();
694 }
695
696 /**
697 * Adds the specified element as the tail (last element) of this list.
698 *
699 * @param e the element to add
700 * @return {@code true} (as specified by {@link Queue#offer})
701 * @since 1.5
702 */
703 public boolean offer(E e) {
704 return add(e);
705 }
706
707 // Deque operations
708 /**
709 * Inserts the specified element at the front of this list.
710 *
711 * @param e the element to insert
712 * @return {@code true} (as specified by {@link Deque#offerFirst})
713 * @since 1.6
714 */
715 public boolean offerFirst(E e) {
716 addFirst(e);
717 return true;
718 }
719
720 /**
721 * Inserts the specified element at the end of this list.
722 *
723 * @param e the element to insert
724 * @return {@code true} (as specified by {@link Deque#offerLast})
725 * @since 1.6
726 */
727 public boolean offerLast(E e) {
728 addLast(e);
729 return true;
730 }
731
732 /**
733 * Retrieves, but does not remove, the first element of this list,
734 * or returns {@code null} if this list is empty.
735 *
736 * @return the first element of this list, or {@code null}
737 * if this list is empty
738 * @since 1.6
739 */
740 public E peekFirst() {
741 final Node<E> f = first;
742 return (f == null) ? null : f.item;
743 }
744
745 /**
746 * Retrieves, but does not remove, the last element of this list,
747 * or returns {@code null} if this list is empty.
748 *
749 * @return the last element of this list, or {@code null}
750 * if this list is empty
751 * @since 1.6
752 */
753 public E peekLast() {
754 final Node<E> l = last;
755 return (l == null) ? null : l.item;
756 }
757
758 /**
759 * Retrieves and removes the first element of this list,
760 * or returns {@code null} if this list is empty.
761 *
762 * @return the first element of this list, or {@code null} if
763 * this list is empty
764 * @since 1.6
765 */
766 public E pollFirst() {
767 final Node<E> f = first;
768 return (f == null) ? null : unlinkFirst(f);
769 }
770
771 /**
772 * Retrieves and removes the last element of this list,
773 * or returns {@code null} if this list is empty.
774 *
775 * @return the last element of this list, or {@code null} if
776 * this list is empty
777 * @since 1.6
778 */
779 public E pollLast() {
780 final Node<E> l = last;
781 return (l == null) ? null : unlinkLast(l);
782 }
783
784 /**
785 * Pushes an element onto the stack represented by this list. In other
786 * words, inserts the element at the front of this list.
787 *
788 * <p>This method is equivalent to {@link #addFirst}.
789 *
790 * @param e the element to push
791 * @since 1.6
792 */
793 public void push(E e) {
794 addFirst(e);
795 }
796
797 /**
798 * Pops an element from the stack represented by this list. In other
799 * words, removes and returns the first element of this list.
800 *
801 * <p>This method is equivalent to {@link #removeFirst()}.
802 *
803 * @return the element at the front of this list (which is the top
804 * of the stack represented by this list)
805 * @throws NoSuchElementException if this list is empty
806 * @since 1.6
807 */
808 public E pop() {
809 return removeFirst();
810 }
811
812 /**
813 * Removes the first occurrence of the specified element in this
814 * list (when traversing the list from head to tail). If the list
815 * does not contain the element, it is unchanged.
816 *
817 * @param o element to be removed from this list, if present
818 * @return {@code true} if the list contained the specified element
819 * @since 1.6
820 */
821 public boolean removeFirstOccurrence(Object o) {
822 return remove(o);
823 }
824
825 /**
826 * Removes the last occurrence of the specified element in this
827 * list (when traversing the list from head to tail). If the list
828 * does not contain the element, it is unchanged.
829 *
830 * @param o element to be removed from this list, if present
831 * @return {@code true} if the list contained the specified element
832 * @since 1.6
833 */
834 public boolean removeLastOccurrence(Object o) {
835 if (o == null) {
836 for (Node<E> x = last; x != null; x = x.prev) {
837 if (x.item == null) {
838 unlink(x);
839 return true;
840 }
841 }
842 } else {
843 for (Node<E> x = last; x != null; x = x.prev) {
844 if (o.equals(x.item)) {
845 unlink(x);
846 return true;
847 }
848 }
849 }
850 return false;
851 }
852
853 /**
854 * Returns a list-iterator of the elements in this list (in proper
855 * sequence), starting at the specified position in the list.
856 * Obeys the general contract of {@code List.listIterator(int)}.<p>
857 *
858 * The list-iterator is <i>fail-fast</i>: if the list is structurally
859 * modified at any time after the Iterator is created, in any way except
860 * through the list-iterator's own {@code remove} or {@code add}
861 * methods, the list-iterator will throw a
862 * {@code ConcurrentModificationException}. Thus, in the face of
863 * concurrent modification, the iterator fails quickly and cleanly, rather
864 * than risking arbitrary, non-deterministic behavior at an undetermined
865 * time in the future.
866 *
867 * @param index index of the first element to be returned from the
868 * list-iterator (by a call to {@code next})
869 * @return a ListIterator of the elements in this list (in proper
870 * sequence), starting at the specified position in the list
871 * @throws IndexOutOfBoundsException {@inheritDoc}
872 * @see List#listIterator(int)
873 */
874 public ListIterator<E> listIterator(int index) {
875 checkPositionIndex(index);
876 return new ListItr(index);
877 }
878
879 private class ListItr implements ListIterator<E> {
880 private Node<E> lastReturned = null;
881 private Node<E> next;
882 private int nextIndex;
883 private int expectedModCount = modCount;
884
885 ListItr(int index) {
886 // assert isPositionIndex(index);
887 next = (index == size) ? null : node(index);
888 nextIndex = index;
889 }
890
891 public boolean hasNext() {
892 return nextIndex < size;
893 }
894
895 public E next() {
896 checkForComodification();
897 if (!hasNext())
898 throw new NoSuchElementException();
899
900 lastReturned = next;
901 next = next.next;
902 nextIndex++;
903 return lastReturned.item;
904 }
905
906 public boolean hasPrevious() {
907 return nextIndex > 0;
908 }
909
910 public E previous() {
911 checkForComodification();
912 if (!hasPrevious())
913 throw new NoSuchElementException();
914
915 lastReturned = next = (next == null) ? last : next.prev;
916 nextIndex--;
917 return lastReturned.item;
918 }
919
920 public int nextIndex() {
921 return nextIndex;
922 }
923
924 public int previousIndex() {
925 return nextIndex - 1;
926 }
927
928 public void remove() {
929 checkForComodification();
930 if (lastReturned == null)
931 throw new IllegalStateException();
932
933 Node<E> lastNext = lastReturned.next;
934 unlink(lastReturned);
935 if (next == lastReturned)
936 next = lastNext;
937 else
938 nextIndex--;
939 lastReturned = null;
940 expectedModCount++;
941 }
942
943 public void set(E e) {
944 if (lastReturned == null)
945 throw new IllegalStateException();
946 checkForComodification();
947 lastReturned.item = e;
948 }
949
950 public void add(E e) {
951 checkForComodification();
952 lastReturned = null;
953 if (next == null)
954 linkLast(e);
955 else
956 linkBefore(e, next);
957 nextIndex++;
958 expectedModCount++;
959 }
960
961 final void checkForComodification() {
962 if (modCount != expectedModCount)
963 throw new ConcurrentModificationException();
964 }
965 }
966
967 private static class Node<E> {
968 E item;
969 Node<E> next;
970 Node<E> prev;
971
972 Node(Node<E> prev, E element, Node<E> next) {
973 this.item = element;
974 this.next = next;
975 this.prev = prev;
976 }
977 }
978
979 /**
980 * @since 1.6
981 */
982 public Iterator<E> descendingIterator() {
983 return new DescendingIterator();
984 }
985
986 /**
987 * Adapter to provide descending iterators via ListItr.previous
988 */
989 private class DescendingIterator implements Iterator<E> {
990 private final ListItr itr = new ListItr(size());
991 public boolean hasNext() {
992 return itr.hasPrevious();
993 }
994 public E next() {
995 return itr.previous();
996 }
997 public void remove() {
998 itr.remove();
999 }
1000 }
1001
1002 @SuppressWarnings("unchecked")
1003 private LinkedList<E> superClone() {
1004 try {
1005 return (LinkedList<E>) super.clone();
1006 } catch (CloneNotSupportedException e) {
1007 throw new InternalError();
1008 }
1009 }
1010
1011 /**
1012 * Returns a shallow copy of this {@code LinkedList}. (The elements
1013 * themselves are not cloned.)
1014 *
1015 * @return a shallow copy of this {@code LinkedList} instance
1016 */
1017 public Object clone() {
1018 LinkedList<E> clone = superClone();
1019
1020 // Put clone into "virgin" state
1021 clone.first = clone.last = null;
1022 clone.size = 0;
1023 clone.modCount = 0;
1024
1025 // Initialize clone with our elements
1026 for (Node<E> x = first; x != null; x = x.next)
1027 clone.add(x.item);
1028
1029 return clone;
1030 }
1031
1032 /**
1033 * Returns an array containing all of the elements in this list
1034 * in proper sequence (from first to last element).
1035 *
1036 * <p>The returned array will be "safe" in that no references to it are
1037 * maintained by this list. (In other words, this method must allocate
1038 * a new array). The caller is thus free to modify the returned array.
1039 *
1040 * <p>This method acts as bridge between array-based and collection-based
1041 * APIs.
1042 *
1043 * @return an array containing all of the elements in this list
1044 * in proper sequence
1045 */
1046 public Object[] toArray() {
1047 Object[] result = new Object[size];
1048 int i = 0;
1049 for (Node<E> x = first; x != null; x = x.next)
1050 result[i++] = x.item;
1051 return result;
1052 }
1053
1054 /**
1055 * Returns an array containing all of the elements in this list in
1056 * proper sequence (from first to last element); the runtime type of
1057 * the returned array is that of the specified array. If the list fits
1058 * in the specified array, it is returned therein. Otherwise, a new
1059 * array is allocated with the runtime type of the specified array and
1060 * the size of this list.
1061 *
1062 * <p>If the list fits in the specified array with room to spare (i.e.,
1063 * the array has more elements than the list), the element in the array
1064 * immediately following the end of the list is set to {@code null}.
1065 * (This is useful in determining the length of the list <i>only</i> if
1066 * the caller knows that the list does not contain any null elements.)
1067 *
1068 * <p>Like the {@link #toArray()} method, this method acts as bridge between
1069 * array-based and collection-based APIs. Further, this method allows
1070 * precise control over the runtime type of the output array, and may,
1071 * under certain circumstances, be used to save allocation costs.
1072 *
1073 * <p>Suppose {@code x} is a list known to contain only strings.
1074 * The following code can be used to dump the list into a newly
1075 * allocated array of {@code String}:
1076 *
1077 * <pre>
1078 * String[] y = x.toArray(new String[0]);</pre>
1079 *
1080 * Note that {@code toArray(new Object[0])} is identical in function to
1081 * {@code toArray()}.
1082 *
1083 * @param a the array into which the elements of the list are to
1084 * be stored, if it is big enough; otherwise, a new array of the
1085 * same runtime type is allocated for this purpose.
1086 * @return an array containing the elements of the list
1087 * @throws ArrayStoreException if the runtime type of the specified array
1088 * is not a supertype of the runtime type of every element in
1089 * this list
1090 * @throws NullPointerException if the specified array is null
1091 */
1092 @SuppressWarnings("unchecked")
1093 public <T> T[] toArray(T[] a) {
1094 if (a.length < size)
1095 a = (T[])java.lang.reflect.Array.newInstance(
1096 a.getClass().getComponentType(), size);
1097 int i = 0;
1098 Object[] result = a;
1099 for (Node<E> x = first; x != null; x = x.next)
1100 result[i++] = x.item;
1101
1102 if (a.length > size)
1103 a[size] = null;
1104
1105 return a;
1106 }
1107
1108 private static final long serialVersionUID = 876323262645176354L;
1109
1110 /**
1111 * Saves the state of this {@code LinkedList} instance to a stream
1112 * (that is, serializes it).
1113 *
1114 * @serialData The size of the list (the number of elements it
1115 * contains) is emitted (int), followed by all of its
1116 * elements (each an Object) in the proper order.
1117 */
1118 private void writeObject(java.io.ObjectOutputStream s)
1119 throws java.io.IOException {
1120 // Write out any hidden serialization magic
1121 s.defaultWriteObject();
1122
1123 // Write out size
1124 s.writeInt(size);
1125
1126 // Write out all elements in the proper order.
1127 for (Node<E> x = first; x != null; x = x.next)
1128 s.writeObject(x.item);
1129 }
1130
1131 /**
1132 * Reconstitutes this {@code LinkedList} instance from a stream
1133 * (that is, deserializes it).
1134 */
1135 @SuppressWarnings("unchecked")
1136 private void readObject(java.io.ObjectInputStream s)
1137 throws java.io.IOException, ClassNotFoundException {
1138 // Read in any hidden serialization magic
1139 s.defaultReadObject();
1140
1141 // Read in size
1142 int size = s.readInt();
1143
1144 // Read in all elements in the proper order.
1145 for (int i = 0; i < size; i++)
1146 linkLast((E)s.readObject());
1147 }
1148 }