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