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 java.util.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 java.util.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 @SuppressWarnings("unchecked") 284 E tmp = (E) a[i]; 285 Entry<E> e = new Entry<E>(tmp, successor, predecessor); 286 predecessor.next = e; 287 predecessor = e; 288 } 289 successor.previous = predecessor; 290 291 size += numNew; 292 return true; 293 } 294 295 /** 296 * Removes all of the elements from this list. 297 */ 298 public void clear() { 299 Entry<E> e = header.next; 300 while (e != header) { 301 Entry<E> next = e.next; 302 e.next = e.previous = null; 303 e.element = null; 304 e = next; 305 } 306 header.next = header.previous = header; 307 size = 0; 308 modCount++; 309 } 310 311 312 // Positional Access Operations 313 314 /** 315 * Returns the element at the specified position in this list. 316 * 317 * @param index index of the element to return 318 * @return the element at the specified position in this list 319 * @throws IndexOutOfBoundsException {@inheritDoc} 320 */ 321 public E get(int index) { 322 return entry(index).element; 323 } 324 325 /** 326 * Replaces the element at the specified position in this list with the 327 * specified element. 328 * 329 * @param index index of the element to replace 330 * @param element element to be stored at the specified position 331 * @return the element previously at the specified position 332 * @throws IndexOutOfBoundsException {@inheritDoc} 333 */ 334 public E set(int index, E element) { 335 Entry<E> e = entry(index); 336 E oldVal = e.element; 337 e.element = element; 338 return oldVal; 339 } 340 341 /** 342 * Inserts the specified element at the specified position in this list. 343 * Shifts the element currently at that position (if any) and any 344 * subsequent elements to the right (adds one to their indices). 345 * 346 * @param index index at which the specified element is to be inserted 347 * @param element element to be inserted 348 * @throws IndexOutOfBoundsException {@inheritDoc} 349 */ 350 public void add(int index, E element) { 351 addBefore(element, (index==size ? header : entry(index))); 352 } 353 354 /** 355 * Removes the element at the specified position in this list. Shifts any 356 * subsequent elements to the left (subtracts one from their indices). 357 * Returns the element that was removed from the list. 358 * 359 * @param index the index of the element to be removed 360 * @return the element previously at the specified position 361 * @throws IndexOutOfBoundsException {@inheritDoc} 362 */ 363 public E remove(int index) { 364 return remove(entry(index)); 365 } 366 367 /** 368 * Returns the indexed entry. 369 */ 370 private Entry<E> entry(int index) { 371 if (index < 0 || index >= size) 372 throw new IndexOutOfBoundsException("Index: "+index+ 373 ", Size: "+size); 374 Entry<E> e = header; 375 if (index < (size >> 1)) { 376 for (int i = 0; i <= index; i++) 377 e = e.next; 378 } else { 379 for (int i = size; i > index; i--) 380 e = e.previous; 381 } 382 return e; 383 } 384 385 386 // Search Operations 387 388 /** 389 * Returns the index of the first occurrence of the specified element 390 * in this list, or -1 if this list does not contain the element. 391 * More formally, returns the lowest index <tt>i</tt> such that 392 * <tt>get(i)==o</tt>, 393 * or -1 if there is no such index. 394 * 395 * @param o element to search for 396 * @return the index of the first occurrence of the specified element in 397 * this list, or -1 if this list does not contain the element 398 */ 399 public int indexOf(Object o) { 400 int index = 0; 401 for (Entry<E> e = header.next; e != header; e = e.next) { 402 if (o == e.element) { 403 return index; 404 } 405 index++; 406 } 407 return -1; 408 } 409 410 /** 411 * Returns the index of the last occurrence of the specified element 412 * in this list, or -1 if this list does not contain the element. 413 * More formally, returns the highest index <tt>i</tt> such that 414 * <tt>get(i)==o</tt>, 415 * or -1 if there is no such index. 416 * 417 * @param o element to search for 418 * @return the index of the last occurrence of the specified element in 419 * this list, or -1 if this list does not contain the element 420 */ 421 public int lastIndexOf(Object o) { 422 int index = size; 423 for (Entry<E> e = header.previous; e != header; e = e.previous) { 424 index--; 425 if (o == e.element) { 426 return index; 427 } 428 } 429 return -1; 430 } 431 432 // Queue operations. 433 434 /** 435 * Retrieves, but does not remove, the head (first element) of this list. 436 * @return the head of this list, or <tt>null</tt> if this list is empty 437 * @since 1.5 438 */ 439 public E peek() { 440 if (size==0) 441 return null; 442 return getFirst(); 443 } 444 445 /** 446 * Retrieves, but does not remove, the head (first element) of this list. 447 * @return the head of this list 448 * @throws NoSuchElementException if this list is empty 449 * @since 1.5 450 */ 451 public E element() { 452 return getFirst(); 453 } 454 455 /** 456 * Retrieves and removes 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 poll() { 461 if (size==0) 462 return null; 463 return removeFirst(); 464 } 465 466 /** 467 * Retrieves and removes the head (first element) of this list. 468 * 469 * @return the head of this list 470 * @throws NoSuchElementException if this list is empty 471 * @since 1.5 472 */ 473 public E remove() { 474 return removeFirst(); 475 } 476 477 /** 478 * Adds the specified element as the tail (last element) of this list. 479 * 480 * @param e the element to add 481 * @return <tt>true</tt> (as specified by {@link java.util.Queue#offer}) 482 * @since 1.5 483 */ 484 public boolean offer(E e) { 485 return add(e); 486 } 487 488 // Deque operations 489 /** 490 * Inserts the specified element at the front of this list. 491 * 492 * @param e the element to insert 493 * @return <tt>true</tt> (as specified by {@link Deque#offerFirst}) 494 * @since 1.6 495 */ 496 public boolean offerFirst(E e) { 497 addFirst(e); 498 return true; 499 } 500 501 /** 502 * Inserts the specified element at the end of this list. 503 * 504 * @param e the element to insert 505 * @return <tt>true</tt> (as specified by {@link Deque#offerLast}) 506 * @since 1.6 507 */ 508 public boolean offerLast(E e) { 509 addLast(e); 510 return true; 511 } 512 513 /** 514 * Retrieves, but does not remove, the first element of this list, 515 * or returns <tt>null</tt> if this list is empty. 516 * 517 * @return the first element of this list, or <tt>null</tt> 518 * if this list is empty 519 * @since 1.6 520 */ 521 public E peekFirst() { 522 if (size==0) 523 return null; 524 return getFirst(); 525 } 526 527 /** 528 * Retrieves, but does not remove, the last element of this list, 529 * or returns <tt>null</tt> if this list is empty. 530 * 531 * @return the last element of this list, or <tt>null</tt> 532 * if this list is empty 533 * @since 1.6 534 */ 535 public E peekLast() { 536 if (size==0) 537 return null; 538 return getLast(); 539 } 540 541 /** 542 * Retrieves and removes the first element of this list, 543 * or returns <tt>null</tt> if this list is empty. 544 * 545 * @return the first element of this list, or <tt>null</tt> if 546 * this list is empty 547 * @since 1.6 548 */ 549 public E pollFirst() { 550 if (size==0) 551 return null; 552 return removeFirst(); 553 } 554 555 /** 556 * Retrieves and removes the last element of this list, 557 * or returns <tt>null</tt> if this list is empty. 558 * 559 * @return the last element of this list, or <tt>null</tt> if 560 * this list is empty 561 * @since 1.6 562 */ 563 public E pollLast() { 564 if (size==0) 565 return null; 566 return removeLast(); 567 } 568 569 /** 570 * Pushes an element onto the stack represented by this list. In other 571 * words, inserts the element at the front of this list. 572 * 573 * <p>This method is equivalent to {@link #addFirst}. 574 * 575 * @param e the element to push 576 * @since 1.6 577 */ 578 public void push(E e) { 579 addFirst(e); 580 } 581 582 /** 583 * Pops an element from the stack represented by this list. In other 584 * words, removes and returns the first element of this list. 585 * 586 * <p>This method is equivalent to {@link #removeFirst()}. 587 * 588 * @return the element at the front of this list (which is the top 589 * of the stack represented by this list) 590 * @throws NoSuchElementException if this list is empty 591 * @since 1.6 592 */ 593 public E pop() { 594 return removeFirst(); 595 } 596 597 /** 598 * Removes the first occurrence of the specified element in this 599 * list (when traversing the list from head to tail). If the list 600 * does not contain the element, it is unchanged. 601 * 602 * @param o element to be removed from this list, if present 603 * @return <tt>true</tt> if the list contained the specified element 604 * @since 1.6 605 */ 606 public boolean removeFirstOccurrence(Object o) { 607 return remove(o); 608 } 609 610 /** 611 * Removes the last occurrence of the specified element in this 612 * list (when traversing the list from head to tail). If the list 613 * does not contain the element, it is unchanged. 614 * 615 * @param o element to be removed from this list, if present 616 * @return <tt>true</tt> if the list contained the specified element 617 * @since 1.6 618 */ 619 public boolean removeLastOccurrence(Object o) { 620 for (Entry<E> e = header.previous; e != header; e = e.previous) { 621 if (o == e.element) { 622 remove(e); 623 return true; 624 } 625 } 626 return false; 627 } 628 629 /** 630 * Returns a list-iterator of the elements in this list (in proper 631 * sequence), starting at the specified position in the list. 632 * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p> 633 * 634 * The list-iterator is <i>fail-fast</i>: if the list is structurally 635 * modified at any time after the Iterator is created, in any way except 636 * through the list-iterator's own <tt>remove</tt> or <tt>add</tt> 637 * methods, the list-iterator will throw a 638 * <tt>ConcurrentModificationException</tt>. Thus, in the face of 639 * concurrent modification, the iterator fails quickly and cleanly, rather 640 * than risking arbitrary, non-deterministic behavior at an undetermined 641 * time in the future. 642 * 643 * @param index index of the first element to be returned from the 644 * list-iterator (by a call to <tt>next</tt>) 645 * @return a ListIterator of the elements in this list (in proper 646 * sequence), starting at the specified position in the list 647 * @throws IndexOutOfBoundsException {@inheritDoc} 648 * @see List#listIterator(int) 649 */ 650 public ListIterator<E> listIterator(int index) { 651 return new ListItr(index); 652 } 653 654 private class ListItr implements ListIterator<E> { 655 private Entry<E> lastReturned = header; 656 private Entry<E> next; 657 private int nextIndex; 658 private int expectedModCount = modCount; 659 660 ListItr(int index) { 661 if (index < 0 || index > size) 662 throw new IndexOutOfBoundsException("Index: "+index+ 663 ", Size: "+size); 664 if (index < (size >> 1)) { 665 next = header.next; 666 for (nextIndex=0; nextIndex<index; nextIndex++) 667 next = next.next; 668 } else { 669 next = header; 670 for (nextIndex=size; nextIndex>index; nextIndex--) 671 next = next.previous; 672 } 673 } 674 675 public boolean hasNext() { 676 return nextIndex != size; 677 } 678 679 public E next() { 680 checkForComodification(); 681 if (nextIndex == size) 682 throw new NoSuchElementException(); 683 684 lastReturned = next; 685 next = next.next; 686 nextIndex++; 687 return lastReturned.element; 688 } 689 690 public boolean hasPrevious() { 691 return nextIndex != 0; 692 } 693 694 public E previous() { 695 if (nextIndex == 0) 696 throw new NoSuchElementException(); 697 698 lastReturned = next = next.previous; 699 nextIndex--; 700 checkForComodification(); 701 return lastReturned.element; 702 } 703 704 public int nextIndex() { 705 return nextIndex; 706 } 707 708 public int previousIndex() { 709 return nextIndex-1; 710 } 711 712 public void remove() { 713 checkForComodification(); 714 Entry<E> lastNext = lastReturned.next; 715 try { 716 IdentityLinkedList.this.remove(lastReturned); 717 } catch (NoSuchElementException e) { 718 throw new IllegalStateException(); 719 } 720 if (next==lastReturned) 721 next = lastNext; 722 else 723 nextIndex--; 724 lastReturned = header; 725 expectedModCount++; 726 } 727 728 public void set(E e) { 729 if (lastReturned == header) 730 throw new IllegalStateException(); 731 checkForComodification(); 732 lastReturned.element = e; 733 } 734 735 public void add(E e) { 736 checkForComodification(); 737 lastReturned = header; 738 addBefore(e, next); 739 nextIndex++; 740 expectedModCount++; 741 } 742 743 final void checkForComodification() { 744 if (modCount != expectedModCount) 745 throw new ConcurrentModificationException(); 746 } 747 } 748 749 private static class Entry<E> { 750 E element; 751 Entry<E> next; 752 Entry<E> previous; 753 754 Entry(E element, Entry<E> next, Entry<E> previous) { 755 this.element = element; 756 this.next = next; 757 this.previous = previous; 758 } 759 } 760 761 private Entry<E> addBefore(E e, Entry<E> entry) { 762 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); 763 newEntry.previous.next = newEntry; 764 newEntry.next.previous = newEntry; 765 size++; 766 modCount++; 767 return newEntry; 768 } 769 770 private E remove(Entry<E> e) { 771 if (e == header) 772 throw new NoSuchElementException(); 773 774 E result = e.element; 775 e.previous.next = e.next; 776 e.next.previous = e.previous; 777 e.next = e.previous = null; 778 e.element = null; 779 size--; 780 modCount++; 781 return result; 782 } 783 784 /** 785 * @since 1.6 786 */ 787 public Iterator<E> descendingIterator() { 788 return new DescendingIterator(); 789 } 790 791 /** Adapter to provide descending iterators via ListItr.previous */ 792 private class DescendingIterator implements Iterator<E> { 793 final ListItr itr = new ListItr(size()); 794 public boolean hasNext() { 795 return itr.hasPrevious(); 796 } 797 public E next() { 798 return itr.previous(); 799 } 800 public void remove() { 801 itr.remove(); 802 } 803 } 804 805 /** 806 * Returns an array containing all of the elements in this list 807 * in proper sequence (from first to last element). 808 * 809 * <p>The returned array will be "safe" in that no references to it are 810 * maintained by this list. (In other words, this method must allocate 811 * a new array). The caller is thus free to modify the returned array. 812 * 813 * <p>This method acts as bridge between array-based and collection-based 814 * APIs. 815 * 816 * @return an array containing all of the elements in this list 817 * in proper sequence 818 */ 819 public Object[] toArray() { 820 Object[] result = new Object[size]; 821 int i = 0; 822 for (Entry<E> e = header.next; e != header; e = e.next) 823 result[i++] = e.element; 824 return result; 825 } 826 827 /** 828 * Returns an array containing all of the elements in this list in 829 * proper sequence (from first to last element); the runtime type of 830 * the returned array is that of the specified array. If the list fits 831 * in the specified array, it is returned therein. Otherwise, a new 832 * array is allocated with the runtime type of the specified array and 833 * the size of this list. 834 * 835 * <p>If the list fits in the specified array with room to spare (i.e., 836 * the array has more elements than the list), the element in the array 837 * immediately following the end of the list is set to <tt>null</tt>. 838 * (This is useful in determining the length of the list <i>only</i> if 839 * the caller knows that the list does not contain any null elements.) 840 * 841 * <p>Like the {@link #toArray()} method, this method acts as bridge between 842 * array-based and collection-based APIs. Further, this method allows 843 * precise control over the runtime type of the output array, and may, 844 * under certain circumstances, be used to save allocation costs. 845 * 846 * <p>Suppose <tt>x</tt> is a list known to contain only strings. 847 * The following code can be used to dump the list into a newly 848 * allocated array of <tt>String</tt>: 849 * 850 * <pre> 851 * String[] y = x.toArray(new String[0]);</pre> 852 * 853 * Note that <tt>toArray(new Object[0])</tt> is identical in function to 854 * <tt>toArray()</tt>. 855 * 856 * @param a the array into which the elements of the list are to 857 * be stored, if it is big enough; otherwise, a new array of the 858 * same runtime type is allocated for this purpose. 859 * @return an array containing the elements of the list 860 * @throws ArrayStoreException if the runtime type of the specified array 861 * is not a supertype of the runtime type of every element in 862 * this list 863 * @throws NullPointerException if the specified array is null 864 */ 865 @SuppressWarnings("unchecked") 866 public <T> T[] toArray(T[] a) { 867 if (a.length < size) 868 a = (T[])java.lang.reflect.Array.newInstance( 869 a.getClass().getComponentType(), size); 870 int i = 0; 871 Object[] result = a; 872 for (Entry<E> e = header.next; e != header; e = e.next) 873 result[i++] = e.element; 874 875 if (a.length > size) 876 a[size] = null; 877 878 return a; 879 } 880 }