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 }