001 /*
002 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package java.util;
027
028 /**
029 * Linked list implementation of the <tt>List</tt> interface. Implements all
030 * optional list operations, and permits all elements (including
031 * <tt>null</tt>). In addition to implementing the <tt>List</tt> interface,
032 * the <tt>LinkedList</tt> class provides uniformly named methods to
033 * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
034 * beginning and end of the list. These operations allow linked lists to be
035 * used as a stack, {@linkplain Queue queue}, or {@linkplain Deque
036 * double-ended queue}. <p>
037 *
038 * The class implements the <tt>Deque</tt> interface, providing
039 * first-in-first-out queue operations for <tt>add</tt>,
040 * <tt>poll</tt>, along with other stack and deque operations.<p>
041 *
042 * All of the operations perform as could be expected for a doubly-linked
043 * list. Operations that index into the list will traverse the list from
044 * the beginning or the end, whichever is closer to the specified index.<p>
045 *
046 * <p><strong>Note that this implementation is not synchronized.</strong>
047 * If multiple threads access a linked list concurrently, and at least
048 * one of the threads modifies the list structurally, it <i>must</i> be
049 * synchronized externally. (A structural modification is any operation
050 * that adds or deletes one or more elements; merely setting the value of
051 * an element is not a structural modification.) This is typically
052 * accomplished by synchronizing on some object that naturally
053 * encapsulates the list.
054 *
055 * If no such object exists, the list should be "wrapped" using the
056 * {@link Collections#synchronizedList Collections.synchronizedList}
057 * method. This is best done at creation time, to prevent accidental
058 * unsynchronized access to the list:<pre>
059 * List list = Collections.synchronizedList(new LinkedList(...));</pre>
060 *
061 * <p>The iterators returned by this class's <tt>iterator</tt> and
062 * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
063 * structurally modified at any time after the iterator is created, in
064 * any way except through the Iterator's own <tt>remove</tt> or
065 * <tt>add</tt> methods, the iterator will throw a {@link
066 * ConcurrentModificationException}. Thus, in the face of concurrent
067 * modification, the iterator fails quickly and cleanly, rather than
068 * risking arbitrary, non-deterministic behavior at an undetermined
069 * time in the future.
070 *
071 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
072 * as it is, generally speaking, impossible to make any hard guarantees in the
073 * presence of unsynchronized concurrent modification. Fail-fast iterators
074 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
075 * Therefore, it would be wrong to write a program that depended on this
076 * exception for its correctness: <i>the fail-fast behavior of iterators
077 * should be used only to detect bugs.</i>
078 *
079 * <p>This class is a member of the
080 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
081 * Java Collections Framework</a>.
082 *
083 * @author Josh Bloch
084 * @version 1.73, 05/05/07
085 * @see List
086 * @see ArrayList
087 * @see Vector
088 * @since 1.2
089 * @param <E> the type of elements held in this collection
090 */
091
092 public class LinkedList<E> extends AbstractSequentialList<E> implements
093 List<E>, Deque<E>, Cloneable, java.io.Serializable {
094 private transient Entry<E> header = new Entry<E>(null, null, null);
095 private transient int size = 0;
096
097 /**
098 * Constructs an empty list.
099 */
100 public LinkedList() {
101 header.next = header.previous = header;
102 }
103
104 /**
105 * Constructs a list containing the elements of the specified
106 * collection, in the order they are returned by the collection's
107 * iterator.
108 *
109 * @param c the collection whose elements are to be placed into this list
110 * @throws NullPointerException if the specified collection is null
111 */
112 public LinkedList(Collection<? extends E> c) {
113 this ();
114 addAll(c);
115 }
116
117 /**
118 * Returns the first element in this list.
119 *
120 * @return the first element in this list
121 * @throws NoSuchElementException if this list is empty
122 */
123 public E getFirst() {
124 if (size == 0)
125 throw new NoSuchElementException();
126
127 return header.next.element;
128 }
129
130 /**
131 * Returns the last element in this list.
132 *
133 * @return the last element in this list
134 * @throws NoSuchElementException if this list is empty
135 */
136 public E getLast() {
137 if (size == 0)
138 throw new NoSuchElementException();
139
140 return header.previous.element;
141 }
142
143 /**
144 * Removes and returns the first element from this list.
145 *
146 * @return the first element from this list
147 * @throws NoSuchElementException if this list is empty
148 */
149 public E removeFirst() {
150 return remove(header.next);
151 }
152
153 /**
154 * Removes and returns the last element from this list.
155 *
156 * @return the last element from this list
157 * @throws NoSuchElementException if this list is empty
158 */
159 public E removeLast() {
160 return remove(header.previous);
161 }
162
163 /**
164 * Inserts the specified element at the beginning of this list.
165 *
166 * @param e the element to add
167 */
168 public void addFirst(E e) {
169 addBefore(e, header.next);
170 }
171
172 /**
173 * Appends the specified element to the end of this list.
174 *
175 * <p>This method is equivalent to {@link #add}.
176 *
177 * @param e the element to add
178 */
179 public void addLast(E e) {
180 addBefore(e, header);
181 }
182
183 /**
184 * Returns <tt>true</tt> if this list contains the specified element.
185 * More formally, returns <tt>true</tt> if and only if this list contains
186 * at least one element <tt>e</tt> such that
187 * <tt>(o==null ? e==null : o.equals(e))</tt>.
188 *
189 * @param o element whose presence in this list is to be tested
190 * @return <tt>true</tt> if this list contains the specified element
191 */
192 public boolean contains(Object o) {
193 return indexOf(o) != -1;
194 }
195
196 /**
197 * Returns the number of elements in this list.
198 *
199 * @return the number of elements in this list
200 */
201 public int size() {
202 return size;
203 }
204
205 /**
206 * Appends the specified element to the end of this list.
207 *
208 * <p>This method is equivalent to {@link #addLast}.
209 *
210 * @param e element to be appended to this list
211 * @return <tt>true</tt> (as specified by {@link Collection#add})
212 */
213 public boolean add(E e) {
214 addBefore(e, header);
215 return true;
216 }
217
218 /**
219 * Removes the first occurrence of the specified element from this list,
220 * if it is present. If this list does not contain the element, it is
221 * unchanged. More formally, removes the element with the lowest index
222 * <tt>i</tt> such that
223 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
224 * (if such an element exists). Returns <tt>true</tt> if this list
225 * contained the specified element (or equivalently, if this list
226 * changed as a result of the call).
227 *
228 * @param o element to be removed from this list, if present
229 * @return <tt>true</tt> if this list contained the specified element
230 */
231 public boolean remove(Object o) {
232 if (o == null) {
233 for (Entry<E> e = header.next; e != header; e = e.next) {
234 if (e.element == null) {
235 remove(e);
236 return true;
237 }
238 }
239 } else {
240 for (Entry<E> e = header.next; e != header; e = e.next) {
241 if (o.equals(e.element)) {
242 remove(e);
243 return true;
244 }
245 }
246 }
247 return false;
248 }
249
250 /**
251 * Appends all of the elements in the specified collection to the end of
252 * this list, in the order that they are returned by the specified
253 * collection's iterator. The behavior of this operation is undefined if
254 * the specified collection is modified while the operation is in
255 * progress. (Note that this will occur if the specified collection is
256 * this list, and it's nonempty.)
257 *
258 * @param c collection containing elements to be added to this list
259 * @return <tt>true</tt> if this list changed as a result of the call
260 * @throws NullPointerException if the specified collection is null
261 */
262 public boolean addAll(Collection<? extends E> c) {
263 return addAll(size, c);
264 }
265
266 /**
267 * Inserts all of the elements in the specified collection into this
268 * list, starting at the specified position. Shifts the element
269 * currently at that position (if any) and any subsequent elements to
270 * the right (increases their indices). The new elements will appear
271 * in the list in the order that they are returned by the
272 * specified collection's iterator.
273 *
274 * @param index index at which to insert the first element
275 * from the specified collection
276 * @param c collection containing elements to be added to this list
277 * @return <tt>true</tt> if this list changed as a result of the call
278 * @throws IndexOutOfBoundsException {@inheritDoc}
279 * @throws NullPointerException if the specified collection is null
280 */
281 public boolean addAll(int index, Collection<? extends E> c) {
282 if (index < 0 || index > size)
283 throw new IndexOutOfBoundsException("Index: " + index
284 + ", Size: " + size);
285 Object[] a = c.toArray();
286 int numNew = a.length;
287 if (numNew == 0)
288 return false;
289 modCount++;
290
291 Entry<E> successor = (index == size ? header : entry(index));
292 Entry<E> predecessor = successor.previous;
293 for (int i = 0; i < numNew; i++) {
294 Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
295 predecessor.next = e;
296 predecessor = e;
297 }
298 successor.previous = predecessor;
299
300 size += numNew;
301 return true;
302 }
303
304 /**
305 * Removes all of the elements from this list.
306 */
307 public void clear() {
308 Entry<E> e = header.next;
309 while (e != header) {
310 Entry<E> next = e.next;
311 e.next = e.previous = null;
312 e.element = null;
313 e = next;
314 }
315 header.next = header.previous = header;
316 size = 0;
317 modCount++;
318 }
319
320 // Positional Access Operations
321
322 /**
323 * Returns the element at the specified position in this list.
324 *
325 * @param index index of the element to return
326 * @return the element at the specified position in this list
327 * @throws IndexOutOfBoundsException {@inheritDoc}
328 */
329 public E get(int index) {
330 return entry(index).element;
331 }
332
333 /**
334 * Replaces the element at the specified position in this list with the
335 * specified element.
336 *
337 * @param index index of the element to replace
338 * @param element element to be stored at the specified position
339 * @return the element previously at the specified position
340 * @throws IndexOutOfBoundsException {@inheritDoc}
341 */
342 public E set(int index, E element) {
343 Entry<E> e = entry(index);
344 E oldVal = e.element;
345 e.element = element;
346 return oldVal;
347 }
348
349 /**
350 * Inserts the specified element at the specified position in this list.
351 * Shifts the element currently at that position (if any) and any
352 * subsequent elements to the right (adds one to their indices).
353 *
354 * @param index index at which the specified element is to be inserted
355 * @param element element to be inserted
356 * @throws IndexOutOfBoundsException {@inheritDoc}
357 */
358 public void add(int index, E element) {
359 addBefore(element, (index == size ? header : entry(index)));
360 }
361
362 /**
363 * Removes the element at the specified position in this list. Shifts any
364 * subsequent elements to the left (subtracts one from their indices).
365 * Returns the element that was removed from the list.
366 *
367 * @param index the index of the element to be removed
368 * @return the element previously at the specified position
369 * @throws IndexOutOfBoundsException {@inheritDoc}
370 */
371 public E remove(int index) {
372 return remove(entry(index));
373 }
374
375 /**
376 * Returns the indexed entry.
377 */
378 private Entry<E> entry(int index) {
379 if (index < 0 || index >= size)
380 throw new IndexOutOfBoundsException("Index: " + index
381 + ", Size: " + size);
382 Entry<E> e = header;
383 if (index < (size >> 1)) {
384 for (int i = 0; i <= index; i++)
385 e = e.next;
386 } else {
387 for (int i = size; i > index; i--)
388 e = e.previous;
389 }
390 return e;
391 }
392
393 // Search Operations
394
395 /**
396 * Returns the index of the first occurrence of the specified element
397 * in this list, or -1 if this list does not contain the element.
398 * More formally, returns the lowest index <tt>i</tt> such that
399 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
400 * or -1 if there is no such index.
401 *
402 * @param o element to search for
403 * @return the index of the first occurrence of the specified element in
404 * this list, or -1 if this list does not contain the element
405 */
406 public int indexOf(Object o) {
407 int index = 0;
408 if (o == null) {
409 for (Entry e = header.next; e != header; e = e.next) {
410 if (e.element == null)
411 return index;
412 index++;
413 }
414 } else {
415 for (Entry e = header.next; e != header; e = e.next) {
416 if (o.equals(e.element))
417 return index;
418 index++;
419 }
420 }
421 return -1;
422 }
423
424 /**
425 * Returns the index of the last occurrence of the specified element
426 * in this list, or -1 if this list does not contain the element.
427 * More formally, returns the highest index <tt>i</tt> such that
428 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
429 * or -1 if there is no such index.
430 *
431 * @param o element to search for
432 * @return the index of the last occurrence of the specified element in
433 * this list, or -1 if this list does not contain the element
434 */
435 public int lastIndexOf(Object o) {
436 int index = size;
437 if (o == null) {
438 for (Entry e = header.previous; e != header; e = e.previous) {
439 index--;
440 if (e.element == null)
441 return index;
442 }
443 } else {
444 for (Entry e = header.previous; e != header; e = e.previous) {
445 index--;
446 if (o.equals(e.element))
447 return index;
448 }
449 }
450 return -1;
451 }
452
453 // Queue operations.
454
455 /**
456 * Retrieves, but does not remove, the head (first element) of this list.
457 * @return the head of this list, or <tt>null</tt> if this list is empty
458 * @since 1.5
459 */
460 public E peek() {
461 if (size == 0)
462 return null;
463 return getFirst();
464 }
465
466 /**
467 * Retrieves, but does not remove, the head (first element) of this list.
468 * @return the head of this list
469 * @throws NoSuchElementException if this list is empty
470 * @since 1.5
471 */
472 public E element() {
473 return getFirst();
474 }
475
476 /**
477 * Retrieves and removes the head (first element) of this list
478 * @return the head of this list, or <tt>null</tt> if this list is empty
479 * @since 1.5
480 */
481 public E poll() {
482 if (size == 0)
483 return null;
484 return removeFirst();
485 }
486
487 /**
488 * Retrieves and removes the head (first element) of this list.
489 *
490 * @return the head of this list
491 * @throws NoSuchElementException if this list is empty
492 * @since 1.5
493 */
494 public E remove() {
495 return removeFirst();
496 }
497
498 /**
499 * Adds the specified element as the tail (last element) of this list.
500 *
501 * @param e the element to add
502 * @return <tt>true</tt> (as specified by {@link Queue#offer})
503 * @since 1.5
504 */
505 public boolean offer(E e) {
506 return add(e);
507 }
508
509 // Deque operations
510 /**
511 * Inserts the specified element at the front of this list.
512 *
513 * @param e the element to insert
514 * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
515 * @since 1.6
516 */
517 public boolean offerFirst(E e) {
518 addFirst(e);
519 return true;
520 }
521
522 /**
523 * Inserts the specified element at the end of this list.
524 *
525 * @param e the element to insert
526 * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
527 * @since 1.6
528 */
529 public boolean offerLast(E e) {
530 addLast(e);
531 return true;
532 }
533
534 /**
535 * Retrieves, but does not remove, the first element of this list,
536 * or returns <tt>null</tt> if this list is empty.
537 *
538 * @return the first element of this list, or <tt>null</tt>
539 * if this list is empty
540 * @since 1.6
541 */
542 public E peekFirst() {
543 if (size == 0)
544 return null;
545 return getFirst();
546 }
547
548 /**
549 * Retrieves, but does not remove, the last element of this list,
550 * or returns <tt>null</tt> if this list is empty.
551 *
552 * @return the last element of this list, or <tt>null</tt>
553 * if this list is empty
554 * @since 1.6
555 */
556 public E peekLast() {
557 if (size == 0)
558 return null;
559 return getLast();
560 }
561
562 /**
563 * Retrieves and removes the first element of this list,
564 * or returns <tt>null</tt> if this list is empty.
565 *
566 * @return the first element of this list, or <tt>null</tt> if
567 * this list is empty
568 * @since 1.6
569 */
570 public E pollFirst() {
571 if (size == 0)
572 return null;
573 return removeFirst();
574 }
575
576 /**
577 * Retrieves and removes the last element of this list,
578 * or returns <tt>null</tt> if this list is empty.
579 *
580 * @return the last element of this list, or <tt>null</tt> if
581 * this list is empty
582 * @since 1.6
583 */
584 public E pollLast() {
585 if (size == 0)
586 return null;
587 return removeLast();
588 }
589
590 /**
591 * Pushes an element onto the stack represented by this list. In other
592 * words, inserts the element at the front of this list.
593 *
594 * <p>This method is equivalent to {@link #addFirst}.
595 *
596 * @param e the element to push
597 * @since 1.6
598 */
599 public void push(E e) {
600 addFirst(e);
601 }
602
603 /**
604 * Pops an element from the stack represented by this list. In other
605 * words, removes and returns the first element of this list.
606 *
607 * <p>This method is equivalent to {@link #removeFirst()}.
608 *
609 * @return the element at the front of this list (which is the top
610 * of the stack represented by this list)
611 * @throws NoSuchElementException if this list is empty
612 * @since 1.6
613 */
614 public E pop() {
615 return removeFirst();
616 }
617
618 /**
619 * Removes the first occurrence of the specified element in this
620 * list (when traversing the list from head to tail). If the list
621 * does not contain the element, it is unchanged.
622 *
623 * @param o element to be removed from this list, if present
624 * @return <tt>true</tt> if the list contained the specified element
625 * @since 1.6
626 */
627 public boolean removeFirstOccurrence(Object o) {
628 return remove(o);
629 }
630
631 /**
632 * Removes the last occurrence of the specified element in this
633 * list (when traversing the list from head to tail). If the list
634 * does not contain the element, it is unchanged.
635 *
636 * @param o element to be removed from this list, if present
637 * @return <tt>true</tt> if the list contained the specified element
638 * @since 1.6
639 */
640 public boolean removeLastOccurrence(Object o) {
641 if (o == null) {
642 for (Entry<E> e = header.previous; e != header; e = e.previous) {
643 if (e.element == null) {
644 remove(e);
645 return true;
646 }
647 }
648 } else {
649 for (Entry<E> e = header.previous; e != header; e = e.previous) {
650 if (o.equals(e.element)) {
651 remove(e);
652 return true;
653 }
654 }
655 }
656 return false;
657 }
658
659 /**
660 * Returns a list-iterator of the elements in this list (in proper
661 * sequence), starting at the specified position in the list.
662 * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
663 *
664 * The list-iterator is <i>fail-fast</i>: if the list is structurally
665 * modified at any time after the Iterator is created, in any way except
666 * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
667 * methods, the list-iterator will throw a
668 * <tt>ConcurrentModificationException</tt>. Thus, in the face of
669 * concurrent modification, the iterator fails quickly and cleanly, rather
670 * than risking arbitrary, non-deterministic behavior at an undetermined
671 * time in the future.
672 *
673 * @param index index of the first element to be returned from the
674 * list-iterator (by a call to <tt>next</tt>)
675 * @return a ListIterator of the elements in this list (in proper
676 * sequence), starting at the specified position in the list
677 * @throws IndexOutOfBoundsException {@inheritDoc}
678 * @see List#listIterator(int)
679 */
680 public ListIterator<E> listIterator(int index) {
681 return new ListItr(index);
682 }
683
684 private class ListItr implements ListIterator<E> {
685 private Entry<E> lastReturned = header;
686 private Entry<E> next;
687 private int nextIndex;
688 private int expectedModCount = modCount;
689
690 ListItr(int index) {
691 if (index < 0 || index > size)
692 throw new IndexOutOfBoundsException("Index: " + index
693 + ", Size: " + size);
694 if (index < (size >> 1)) {
695 next = header.next;
696 for (nextIndex = 0; nextIndex < index; nextIndex++)
697 next = next.next;
698 } else {
699 next = header;
700 for (nextIndex = size; nextIndex > index; nextIndex--)
701 next = next.previous;
702 }
703 }
704
705 public boolean hasNext() {
706 return nextIndex != size;
707 }
708
709 public E next() {
710 checkForComodification();
711 if (nextIndex == size)
712 throw new NoSuchElementException();
713
714 lastReturned = next;
715 next = next.next;
716 nextIndex++;
717 return lastReturned.element;
718 }
719
720 public boolean hasPrevious() {
721 return nextIndex != 0;
722 }
723
724 public E previous() {
725 if (nextIndex == 0)
726 throw new NoSuchElementException();
727
728 lastReturned = next = next.previous;
729 nextIndex--;
730 checkForComodification();
731 return lastReturned.element;
732 }
733
734 public int nextIndex() {
735 return nextIndex;
736 }
737
738 public int previousIndex() {
739 return nextIndex - 1;
740 }
741
742 public void remove() {
743 checkForComodification();
744 Entry<E> lastNext = lastReturned.next;
745 try {
746 LinkedList.this .remove(lastReturned);
747 } catch (NoSuchElementException e) {
748 throw new IllegalStateException();
749 }
750 if (next == lastReturned)
751 next = lastNext;
752 else
753 nextIndex--;
754 lastReturned = header;
755 expectedModCount++;
756 }
757
758 public void set(E e) {
759 if (lastReturned == header)
760 throw new IllegalStateException();
761 checkForComodification();
762 lastReturned.element = e;
763 }
764
765 public void add(E e) {
766 checkForComodification();
767 lastReturned = header;
768 addBefore(e, next);
769 nextIndex++;
770 expectedModCount++;
771 }
772
773 final void checkForComodification() {
774 if (modCount != expectedModCount)
775 throw new ConcurrentModificationException();
776 }
777 }
778
779 private static class Entry<E> {
780 E element;
781 Entry<E> next;
782 Entry<E> previous;
783
784 Entry(E element, Entry<E> next, Entry<E> previous) {
785 this .element = element;
786 this .next = next;
787 this .previous = previous;
788 }
789 }
790
791 private Entry<E> addBefore(E e, Entry<E> entry) {
792 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
793 newEntry.previous.next = newEntry;
794 newEntry.next.previous = newEntry;
795 size++;
796 modCount++;
797 return newEntry;
798 }
799
800 private E remove(Entry<E> e) {
801 if (e == header)
802 throw new NoSuchElementException();
803
804 E result = e.element;
805 e.previous.next = e.next;
806 e.next.previous = e.previous;
807 e.next = e.previous = null;
808 e.element = null;
809 size--;
810 modCount++;
811 return result;
812 }
813
814 /**
815 * @since 1.6
816 */
817 public Iterator<E> descendingIterator() {
818 return new DescendingIterator();
819 }
820
821 /** Adapter to provide descending iterators via ListItr.previous */
822 private class DescendingIterator implements Iterator {
823 final ListItr itr = new ListItr(size());
824
825 public boolean hasNext() {
826 return itr.hasPrevious();
827 }
828
829 public E next() {
830 return itr.previous();
831 }
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(a.getClass()
928 .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 }
|