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