1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20import java.io.IOException; 21import java.io.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24import java.lang.reflect.Array; 25 26/** 27 * LinkedList is an implementation of {@link List}, backed by a doubly-linked list. 28 * All optional operations including adding, removing, and replacing elements are supported. 29 * 30 * <p>All elements are permitted, including null. 31 * 32 * <p>This class is primarily useful if you need queue-like behavior. It may also be useful 33 * as a list if you expect your lists to contain zero or one element, but still require the 34 * ability to scale to slightly larger numbers of elements. In general, though, you should 35 * probably use {@link ArrayList} if you don't need the queue-like behavior. 36 * 37 * @since 1.2 38 */ 39public class LinkedList<E> extends AbstractSequentialList<E> implements 40 List<E>, Deque<E>, Queue<E>, Cloneable, Serializable { 41 42 private static final long serialVersionUID = 876323262645176354L; 43 44 transient int size = 0; 45 46 transient Link<E> voidLink; 47 48 private static final class Link<ET> { 49 ET data; 50 51 Link<ET> previous, next; 52 53 Link(ET o, Link<ET> p, Link<ET> n) { 54 data = o; 55 previous = p; 56 next = n; 57 } 58 } 59 60 private static final class LinkIterator<ET> implements ListIterator<ET> { 61 int pos, expectedModCount; 62 63 final LinkedList<ET> list; 64 65 Link<ET> link, lastLink; 66 67 LinkIterator(LinkedList<ET> object, int location) { 68 list = object; 69 expectedModCount = list.modCount; 70 if (location >= 0 && location <= list.size) { 71 // pos ends up as -1 if list is empty, it ranges from -1 to 72 // list.size - 1 73 // if link == voidLink then pos must == -1 74 link = list.voidLink; 75 if (location < list.size / 2) { 76 for (pos = -1; pos + 1 < location; pos++) { 77 link = link.next; 78 } 79 } else { 80 for (pos = list.size; pos >= location; pos--) { 81 link = link.previous; 82 } 83 } 84 } else { 85 throw new IndexOutOfBoundsException(); 86 } 87 } 88 89 public void add(ET object) { 90 if (expectedModCount == list.modCount) { 91 Link<ET> next = link.next; 92 Link<ET> newLink = new Link<ET>(object, link, next); 93 link.next = newLink; 94 next.previous = newLink; 95 link = newLink; 96 lastLink = null; 97 pos++; 98 expectedModCount++; 99 list.size++; 100 list.modCount++; 101 } else { 102 throw new ConcurrentModificationException(); 103 } 104 } 105 106 public boolean hasNext() { 107 return link.next != list.voidLink; 108 } 109 110 public boolean hasPrevious() { 111 return link != list.voidLink; 112 } 113 114 public ET next() { 115 if (expectedModCount == list.modCount) { 116 LinkedList.Link<ET> next = link.next; 117 if (next != list.voidLink) { 118 lastLink = link = next; 119 pos++; 120 return link.data; 121 } 122 throw new NoSuchElementException(); 123 } 124 throw new ConcurrentModificationException(); 125 } 126 127 public int nextIndex() { 128 return pos + 1; 129 } 130 131 public ET previous() { 132 if (expectedModCount == list.modCount) { 133 if (link != list.voidLink) { 134 lastLink = link; 135 link = link.previous; 136 pos--; 137 return lastLink.data; 138 } 139 throw new NoSuchElementException(); 140 } 141 throw new ConcurrentModificationException(); 142 } 143 144 public int previousIndex() { 145 return pos; 146 } 147 148 public void remove() { 149 if (expectedModCount == list.modCount) { 150 if (lastLink != null) { 151 Link<ET> next = lastLink.next; 152 Link<ET> previous = lastLink.previous; 153 next.previous = previous; 154 previous.next = next; 155 if (lastLink == link) { 156 pos--; 157 } 158 link = previous; 159 lastLink = null; 160 expectedModCount++; 161 list.size--; 162 list.modCount++; 163 } else { 164 throw new IllegalStateException(); 165 } 166 } else { 167 throw new ConcurrentModificationException(); 168 } 169 } 170 171 public void set(ET object) { 172 if (expectedModCount == list.modCount) { 173 if (lastLink != null) { 174 lastLink.data = object; 175 } else { 176 throw new IllegalStateException(); 177 } 178 } else { 179 throw new ConcurrentModificationException(); 180 } 181 } 182 } 183 184 /* 185 * NOTES:descendingIterator is not fail-fast, according to the documentation 186 * and test case. 187 */ 188 private class ReverseLinkIterator<ET> implements Iterator<ET> { 189 private int expectedModCount; 190 191 private final LinkedList<ET> list; 192 193 private Link<ET> link; 194 195 private boolean canRemove; 196 197 ReverseLinkIterator(LinkedList<ET> linkedList) { 198 list = linkedList; 199 expectedModCount = list.modCount; 200 link = list.voidLink; 201 canRemove = false; 202 } 203 204 public boolean hasNext() { 205 return link.previous != list.voidLink; 206 } 207 208 public ET next() { 209 if (expectedModCount == list.modCount) { 210 if (hasNext()) { 211 link = link.previous; 212 canRemove = true; 213 return link.data; 214 } 215 throw new NoSuchElementException(); 216 } 217 throw new ConcurrentModificationException(); 218 219 } 220 221 public void remove() { 222 if (expectedModCount == list.modCount) { 223 if (canRemove) { 224 Link<ET> next = link.previous; 225 Link<ET> previous = link.next; 226 next.next = previous; 227 previous.previous = next; 228 link = previous; 229 list.size--; 230 list.modCount++; 231 expectedModCount++; 232 canRemove = false; 233 return; 234 } 235 throw new IllegalStateException(); 236 } 237 throw new ConcurrentModificationException(); 238 } 239 } 240 241 /** 242 * Constructs a new empty instance of {@code LinkedList}. 243 */ 244 public LinkedList() { 245 voidLink = new Link<E>(null, null, null); 246 voidLink.previous = voidLink; 247 voidLink.next = voidLink; 248 } 249 250 /** 251 * Constructs a new instance of {@code LinkedList} that holds all of the 252 * elements contained in the specified {@code collection}. The order of the 253 * elements in this new {@code LinkedList} will be determined by the 254 * iteration order of {@code collection}. 255 * 256 * @param collection 257 * the collection of elements to add. 258 */ 259 public LinkedList(Collection<? extends E> collection) { 260 this(); 261 addAll(collection); 262 } 263 264 /** 265 * Inserts the specified object into this {@code LinkedList} at the 266 * specified location. The object is inserted before any previous element at 267 * the specified location. If the location is equal to the size of this 268 * {@code LinkedList}, the object is added at the end. 269 * 270 * @param location 271 * the index at which to insert. 272 * @param object 273 * the object to add. 274 * @throws IndexOutOfBoundsException 275 * if {@code location < 0 || location > size()} 276 */ 277 @Override 278 public void add(int location, E object) { 279 if (location >= 0 && location <= size) { 280 Link<E> link = voidLink; 281 if (location < (size / 2)) { 282 for (int i = 0; i <= location; i++) { 283 link = link.next; 284 } 285 } else { 286 for (int i = size; i > location; i--) { 287 link = link.previous; 288 } 289 } 290 Link<E> previous = link.previous; 291 Link<E> newLink = new Link<E>(object, previous, link); 292 previous.next = newLink; 293 link.previous = newLink; 294 size++; 295 modCount++; 296 } else { 297 throw new IndexOutOfBoundsException(); 298 } 299 } 300 301 /** 302 * Adds the specified object at the end of this {@code LinkedList}. 303 * 304 * @param object 305 * the object to add. 306 * @return always true 307 */ 308 @Override 309 public boolean add(E object) { 310 return addLastImpl(object); 311 } 312 313 private boolean addLastImpl(E object) { 314 Link<E> oldLast = voidLink.previous; 315 Link<E> newLink = new Link<E>(object, oldLast, voidLink); 316 voidLink.previous = newLink; 317 oldLast.next = newLink; 318 size++; 319 modCount++; 320 return true; 321 } 322 323 /** 324 * Inserts the objects in the specified collection at the specified location 325 * in this {@code LinkedList}. The objects are added in the order they are 326 * returned from the collection's iterator. 327 * 328 * @param location 329 * the index at which to insert. 330 * @param collection 331 * the collection of objects 332 * @return {@code true} if this {@code LinkedList} is modified, 333 * {@code false} otherwise. 334 * @throws ClassCastException 335 * if the class of an object is inappropriate for this list. 336 * @throws IllegalArgumentException 337 * if an object cannot be added to this list. 338 * @throws IndexOutOfBoundsException 339 * if {@code location < 0 || location > size()} 340 */ 341 @Override 342 public boolean addAll(int location, Collection<? extends E> collection) { 343 if (location < 0 || location > size) { 344 throw new IndexOutOfBoundsException(); 345 } 346 int adding = collection.size(); 347 if (adding == 0) { 348 return false; 349 } 350 Collection<? extends E> elements = (collection == this) ? 351 new ArrayList<E>(collection) : collection; 352 353 Link<E> previous = voidLink; 354 if (location < (size / 2)) { 355 for (int i = 0; i < location; i++) { 356 previous = previous.next; 357 } 358 } else { 359 for (int i = size; i >= location; i--) { 360 previous = previous.previous; 361 } 362 } 363 Link<E> next = previous.next; 364 for (E e : elements) { 365 Link<E> newLink = new Link<E>(e, previous, null); 366 previous.next = newLink; 367 previous = newLink; 368 } 369 previous.next = next; 370 next.previous = previous; 371 size += adding; 372 modCount++; 373 return true; 374 } 375 376 /** 377 * Adds the objects in the specified Collection to this {@code LinkedList}. 378 * 379 * @param collection 380 * the collection of objects. 381 * @return {@code true} if this {@code LinkedList} is modified, 382 * {@code false} otherwise. 383 */ 384 @Override 385 public boolean addAll(Collection<? extends E> collection) { 386 int adding = collection.size(); 387 if (adding == 0) { 388 return false; 389 } 390 Collection<? extends E> elements = (collection == this) ? 391 new ArrayList<E>(collection) : collection; 392 393 Link<E> previous = voidLink.previous; 394 for (E e : elements) { 395 Link<E> newLink = new Link<E>(e, previous, null); 396 previous.next = newLink; 397 previous = newLink; 398 } 399 previous.next = voidLink; 400 voidLink.previous = previous; 401 size += adding; 402 modCount++; 403 return true; 404 } 405 406 /** 407 * Adds the specified object at the beginning of this {@code LinkedList}. 408 * 409 * @param object 410 * the object to add. 411 */ 412 public void addFirst(E object) { 413 addFirstImpl(object); 414 } 415 416 private boolean addFirstImpl(E object) { 417 Link<E> oldFirst = voidLink.next; 418 Link<E> newLink = new Link<E>(object, voidLink, oldFirst); 419 voidLink.next = newLink; 420 oldFirst.previous = newLink; 421 size++; 422 modCount++; 423 return true; 424 } 425 426 /** 427 * Adds the specified object at the end of this {@code LinkedList}. 428 * 429 * @param object 430 * the object to add. 431 */ 432 public void addLast(E object) { 433 addLastImpl(object); 434 } 435 436 /** 437 * Removes all elements from this {@code LinkedList}, leaving it empty. 438 * 439 * @see List#isEmpty 440 * @see #size 441 */ 442 @Override 443 public void clear() { 444 if (size > 0) { 445 size = 0; 446 voidLink.next = voidLink; 447 voidLink.previous = voidLink; 448 modCount++; 449 } 450 } 451 452 /** 453 * Returns a new {@code LinkedList} with the same elements and size as this 454 * {@code LinkedList}. 455 * 456 * @return a shallow copy of this {@code LinkedList}. 457 * @see java.lang.Cloneable 458 */ 459 @SuppressWarnings("unchecked") 460 @Override 461 public Object clone() { 462 try { 463 LinkedList<E> l = (LinkedList<E>) super.clone(); 464 l.size = 0; 465 l.voidLink = new Link<E>(null, null, null); 466 l.voidLink.previous = l.voidLink; 467 l.voidLink.next = l.voidLink; 468 l.addAll(this); 469 return l; 470 } catch (CloneNotSupportedException e) { 471 throw new AssertionError(e); 472 } 473 } 474 475 /** 476 * Searches this {@code LinkedList} for the specified object. 477 * 478 * @param object 479 * the object to search for. 480 * @return {@code true} if {@code object} is an element of this 481 * {@code LinkedList}, {@code false} otherwise 482 */ 483 @Override 484 public boolean contains(Object object) { 485 Link<E> link = voidLink.next; 486 if (object != null) { 487 while (link != voidLink) { 488 if (object.equals(link.data)) { 489 return true; 490 } 491 link = link.next; 492 } 493 } else { 494 while (link != voidLink) { 495 if (link.data == null) { 496 return true; 497 } 498 link = link.next; 499 } 500 } 501 return false; 502 } 503 504 @Override 505 public E get(int location) { 506 if (location >= 0 && location < size) { 507 Link<E> link = voidLink; 508 if (location < (size / 2)) { 509 for (int i = 0; i <= location; i++) { 510 link = link.next; 511 } 512 } else { 513 for (int i = size; i > location; i--) { 514 link = link.previous; 515 } 516 } 517 return link.data; 518 } 519 throw new IndexOutOfBoundsException(); 520 } 521 522 /** 523 * Returns the first element in this {@code LinkedList}. 524 * 525 * @return the first element. 526 * @throws NoSuchElementException 527 * if this {@code LinkedList} is empty. 528 */ 529 public E getFirst() { 530 return getFirstImpl(); 531 } 532 533 private E getFirstImpl() { 534 Link<E> first = voidLink.next; 535 if (first != voidLink) { 536 return first.data; 537 } 538 throw new NoSuchElementException(); 539 } 540 541 /** 542 * Returns the last element in this {@code LinkedList}. 543 * 544 * @return the last element 545 * @throws NoSuchElementException 546 * if this {@code LinkedList} is empty 547 */ 548 public E getLast() { 549 Link<E> last = voidLink.previous; 550 if (last != voidLink) { 551 return last.data; 552 } 553 throw new NoSuchElementException(); 554 } 555 556 @Override 557 public int indexOf(Object object) { 558 int pos = 0; 559 Link<E> link = voidLink.next; 560 if (object != null) { 561 while (link != voidLink) { 562 if (object.equals(link.data)) { 563 return pos; 564 } 565 link = link.next; 566 pos++; 567 } 568 } else { 569 while (link != voidLink) { 570 if (link.data == null) { 571 return pos; 572 } 573 link = link.next; 574 pos++; 575 } 576 } 577 return -1; 578 } 579 580 /** 581 * Searches this {@code LinkedList} for the specified object and returns the 582 * index of the last occurrence. 583 * 584 * @param object 585 * the object to search for 586 * @return the index of the last occurrence of the object, or -1 if it was 587 * not found. 588 */ 589 @Override 590 public int lastIndexOf(Object object) { 591 int pos = size; 592 Link<E> link = voidLink.previous; 593 if (object != null) { 594 while (link != voidLink) { 595 pos--; 596 if (object.equals(link.data)) { 597 return pos; 598 } 599 link = link.previous; 600 } 601 } else { 602 while (link != voidLink) { 603 pos--; 604 if (link.data == null) { 605 return pos; 606 } 607 link = link.previous; 608 } 609 } 610 return -1; 611 } 612 613 /** 614 * Returns a ListIterator on the elements of this {@code LinkedList}. The 615 * elements are iterated in the same order that they occur in the 616 * {@code LinkedList}. The iteration starts at the specified location. 617 * 618 * @param location 619 * the index at which to start the iteration 620 * @return a ListIterator on the elements of this {@code LinkedList} 621 * @throws IndexOutOfBoundsException 622 * if {@code location < 0 || location > size()} 623 * @see ListIterator 624 */ 625 @Override 626 public ListIterator<E> listIterator(int location) { 627 return new LinkIterator<E>(this, location); 628 } 629 630 /** 631 * Removes the object at the specified location from this {@code LinkedList}. 632 * 633 * @param location 634 * the index of the object to remove 635 * @return the removed object 636 * @throws IndexOutOfBoundsException 637 * if {@code location < 0 || location >= size()} 638 */ 639 @Override 640 public E remove(int location) { 641 if (location >= 0 && location < size) { 642 Link<E> link = voidLink; 643 if (location < (size / 2)) { 644 for (int i = 0; i <= location; i++) { 645 link = link.next; 646 } 647 } else { 648 for (int i = size; i > location; i--) { 649 link = link.previous; 650 } 651 } 652 Link<E> previous = link.previous; 653 Link<E> next = link.next; 654 previous.next = next; 655 next.previous = previous; 656 size--; 657 modCount++; 658 return link.data; 659 } 660 throw new IndexOutOfBoundsException(); 661 } 662 663 @Override 664 public boolean remove(Object object) { 665 return removeFirstOccurrenceImpl(object); 666 } 667 668 /** 669 * Removes the first object from this {@code LinkedList}. 670 * 671 * @return the removed object. 672 * @throws NoSuchElementException 673 * if this {@code LinkedList} is empty. 674 */ 675 public E removeFirst() { 676 return removeFirstImpl(); 677 } 678 679 private E removeFirstImpl() { 680 Link<E> first = voidLink.next; 681 if (first != voidLink) { 682 Link<E> next = first.next; 683 voidLink.next = next; 684 next.previous = voidLink; 685 size--; 686 modCount++; 687 return first.data; 688 } 689 throw new NoSuchElementException(); 690 } 691 692 /** 693 * Removes the last object from this {@code LinkedList}. 694 * 695 * @return the removed object. 696 * @throws NoSuchElementException 697 * if this {@code LinkedList} is empty. 698 */ 699 public E removeLast() { 700 return removeLastImpl(); 701 } 702 703 private E removeLastImpl() { 704 Link<E> last = voidLink.previous; 705 if (last != voidLink) { 706 Link<E> previous = last.previous; 707 voidLink.previous = previous; 708 previous.next = voidLink; 709 size--; 710 modCount++; 711 return last.data; 712 } 713 throw new NoSuchElementException(); 714 } 715 716 /** 717 * {@inheritDoc} 718 * 719 * @see java.util.Deque#descendingIterator() 720 * @since 1.6 721 */ 722 public Iterator<E> descendingIterator() { 723 return new ReverseLinkIterator<E>(this); 724 } 725 726 /** 727 * {@inheritDoc} 728 * 729 * @see java.util.Deque#offerFirst(java.lang.Object) 730 * @since 1.6 731 */ 732 public boolean offerFirst(E e) { 733 return addFirstImpl(e); 734 } 735 736 /** 737 * {@inheritDoc} 738 * 739 * @see java.util.Deque#offerLast(java.lang.Object) 740 * @since 1.6 741 */ 742 public boolean offerLast(E e) { 743 return addLastImpl(e); 744 } 745 746 /** 747 * {@inheritDoc} 748 * 749 * @see java.util.Deque#peekFirst() 750 * @since 1.6 751 */ 752 public E peekFirst() { 753 return peekFirstImpl(); 754 } 755 756 /** 757 * {@inheritDoc} 758 * 759 * @see java.util.Deque#peekLast() 760 * @since 1.6 761 */ 762 public E peekLast() { 763 Link<E> last = voidLink.previous; 764 return (last == voidLink) ? null : last.data; 765 } 766 767 /** 768 * {@inheritDoc} 769 * 770 * @see java.util.Deque#pollFirst() 771 * @since 1.6 772 */ 773 public E pollFirst() { 774 return (size == 0) ? null : removeFirstImpl(); 775 } 776 777 /** 778 * {@inheritDoc} 779 * 780 * @see java.util.Deque#pollLast() 781 * @since 1.6 782 */ 783 public E pollLast() { 784 return (size == 0) ? null : removeLastImpl(); 785 } 786 787 /** 788 * {@inheritDoc} 789 * 790 * @see java.util.Deque#pop() 791 * @since 1.6 792 */ 793 public E pop() { 794 return removeFirstImpl(); 795 } 796 797 /** 798 * {@inheritDoc} 799 * 800 * @see java.util.Deque#push(java.lang.Object) 801 * @since 1.6 802 */ 803 public void push(E e) { 804 addFirstImpl(e); 805 } 806 807 /** 808 * {@inheritDoc} 809 * 810 * @see java.util.Deque#removeFirstOccurrence(java.lang.Object) 811 * @since 1.6 812 */ 813 public boolean removeFirstOccurrence(Object o) { 814 return removeFirstOccurrenceImpl(o); 815 } 816 817 /** 818 * {@inheritDoc} 819 * 820 * @see java.util.Deque#removeLastOccurrence(java.lang.Object) 821 * @since 1.6 822 */ 823 public boolean removeLastOccurrence(Object o) { 824 Iterator<E> iter = new ReverseLinkIterator<E>(this); 825 return removeOneOccurrence(o, iter); 826 } 827 828 private boolean removeFirstOccurrenceImpl(Object o) { 829 Iterator<E> iter = new LinkIterator<E>(this, 0); 830 return removeOneOccurrence(o, iter); 831 } 832 833 private boolean removeOneOccurrence(Object o, Iterator<E> iter) { 834 while (iter.hasNext()) { 835 E element = iter.next(); 836 if (o == null ? element == null : o.equals(element)) { 837 iter.remove(); 838 return true; 839 } 840 } 841 return false; 842 } 843 844 /** 845 * Replaces the element at the specified location in this {@code LinkedList} 846 * with the specified object. 847 * 848 * @param location 849 * the index at which to put the specified object. 850 * @param object 851 * the object to add. 852 * @return the previous element at the index. 853 * @throws ClassCastException 854 * if the class of an object is inappropriate for this list. 855 * @throws IllegalArgumentException 856 * if an object cannot be added to this list. 857 * @throws IndexOutOfBoundsException 858 * if {@code location < 0 || location >= size()} 859 */ 860 @Override 861 public E set(int location, E object) { 862 if (location >= 0 && location < size) { 863 Link<E> link = voidLink; 864 if (location < (size / 2)) { 865 for (int i = 0; i <= location; i++) { 866 link = link.next; 867 } 868 } else { 869 for (int i = size; i > location; i--) { 870 link = link.previous; 871 } 872 } 873 E result = link.data; 874 link.data = object; 875 return result; 876 } 877 throw new IndexOutOfBoundsException(); 878 } 879 880 /** 881 * Returns the number of elements in this {@code LinkedList}. 882 * 883 * @return the number of elements in this {@code LinkedList}. 884 */ 885 @Override 886 public int size() { 887 return size; 888 } 889 890 public boolean offer(E o) { 891 return addLastImpl(o); 892 } 893 894 public E poll() { 895 return size == 0 ? null : removeFirst(); 896 } 897 898 public E remove() { 899 return removeFirstImpl(); 900 } 901 902 public E peek() { 903 return peekFirstImpl(); 904 } 905 906 private E peekFirstImpl() { 907 Link<E> first = voidLink.next; 908 return first == voidLink ? null : first.data; 909 } 910 911 public E element() { 912 return getFirstImpl(); 913 } 914 915 /** 916 * Returns a new array containing all elements contained in this 917 * {@code LinkedList}. 918 * 919 * @return an array of the elements from this {@code LinkedList}. 920 */ 921 @Override 922 public Object[] toArray() { 923 int index = 0; 924 Object[] contents = new Object[size]; 925 Link<E> link = voidLink.next; 926 while (link != voidLink) { 927 contents[index++] = link.data; 928 link = link.next; 929 } 930 return contents; 931 } 932 933 /** 934 * Returns an array containing all elements contained in this 935 * {@code LinkedList}. If the specified array is large enough to hold the 936 * elements, the specified array is used, otherwise an array of the same 937 * type is created. If the specified array is used and is larger than this 938 * {@code LinkedList}, the array element following the collection elements 939 * is set to null. 940 * 941 * @param contents 942 * the array. 943 * @return an array of the elements from this {@code LinkedList}. 944 * @throws ArrayStoreException 945 * if the type of an element in this {@code LinkedList} cannot 946 * be stored in the type of the specified array. 947 */ 948 @Override 949 @SuppressWarnings("unchecked") 950 public <T> T[] toArray(T[] contents) { 951 int index = 0; 952 if (size > contents.length) { 953 Class<?> ct = contents.getClass().getComponentType(); 954 contents = (T[]) Array.newInstance(ct, size); 955 } 956 Link<E> link = voidLink.next; 957 while (link != voidLink) { 958 contents[index++] = (T) link.data; 959 link = link.next; 960 } 961 if (index < contents.length) { 962 contents[index] = null; 963 } 964 return contents; 965 } 966 967 private void writeObject(ObjectOutputStream stream) throws IOException { 968 stream.defaultWriteObject(); 969 stream.writeInt(size); 970 Iterator<E> it = iterator(); 971 while (it.hasNext()) { 972 stream.writeObject(it.next()); 973 } 974 } 975 976 @SuppressWarnings("unchecked") 977 private void readObject(ObjectInputStream stream) throws IOException, 978 ClassNotFoundException { 979 stream.defaultReadObject(); 980 size = stream.readInt(); 981 voidLink = new Link<E>(null, null, null); 982 Link<E> link = voidLink; 983 for (int i = size; --i >= 0;) { 984 Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null); 985 link.next = nextLink; 986 link = nextLink; 987 } 988 link.next = voidLink; 989 voidLink.previous = link; 990 } 991} 992