1 /* 2 * Copyright (c) 1997, 2006, 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 java.util; 27 28 /** 29 * Linked list implementation of the {@code List} interface. 30 * Implements all optional list operations, and permits all elements 31 * (including {@code null}). In addition to implementing the {@code 32 * List} interface, the {@code LinkedList} class provides uniformly 33 * named methods to {@code get}, {@code remove} and {@code add} an 34 * element at the beginning (<i>operation</i>{@code First}) and end 35 * (<i>operation</i>{@code Last}) of the list. These operations allow 36 * linked lists to be used as a stack, {@linkplain Queue queue}, or 37 * {@linkplain Deque deque} (double-ended queue); by implementing the 38 * {@link Deque} interface, support is included for first-in-first-out 39 * operations for {@code add} and {@code poll}. 40 * 41 * <p>All of the operations perform as could be expected for a doubly-linked 42 * list. Operations that index into the list will traverse the list from 43 * the beginning or the end, whichever is closer to the specified index. 44 * 45 * <p><strong>Note that this implementation is not synchronized.</strong> 46 * If multiple threads access a linked list concurrently, and at least 47 * one of the threads modifies the list structurally, it <i>must</i> be 48 * synchronized externally. (A structural modification is any operation 49 * that adds or deletes one or more elements; merely setting the value of 50 * an element is not a structural modification.) This is typically 51 * accomplished by synchronizing on some object that naturally 52 * encapsulates the list. 53 * 54 * If no such object exists, the list should be "wrapped" using the 55 * {@link Collections#synchronizedList Collections.synchronizedList} 56 * method. This is best done at creation time, to prevent accidental 57 * unsynchronized access to the list:<pre> 58 * List list = Collections.synchronizedList(new LinkedList(...));</pre> 59 * 60 * <p>The iterators returned by this class's {@code iterator} and 61 * {@code listIterator} methods are <i>fail-fast</i>: if the list is 62 * structurally modified at any time after the iterator is created, in 63 * any way except through the Iterator's own {@code remove} or 64 * {@code add} methods, the iterator will throw a {@link 65 * ConcurrentModificationException}. Thus, in the face of concurrent 66 * modification, the iterator fails quickly and cleanly, rather than 67 * risking arbitrary, non-deterministic behavior at an undetermined 68 * time in the future. 69 * 70 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 71 * as it is, generally speaking, impossible to make any hard guarantees in the 72 * presence of unsynchronized concurrent modification. Fail-fast iterators 73 * throw {@code ConcurrentModificationException} on a best-effort basis. 74 * Therefore, it would be wrong to write a program that depended on this 75 * exception for its correctness: <i>the fail-fast behavior of iterators 76 * should be used only to detect bugs.</i> 77 * 78 * <p>This class is a member of the 79 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 80 * Java Collections Framework</a>. 81 * 82 * @author Josh Bloch 83 * @see List 84 * @see ArrayList 85 * @since 1.2 86 * @param <E> the type of elements held in this collection 87 */ 88 89 public class LinkedList<E> 90 extends AbstractSequentialList<E> 91 implements List<E>, Deque<E>, Cloneable, java.io.Serializable 92 { 93 transient int size = 0; 94 95 /** 96 * Pointer to first node. 97 * Invariant: (first == null && last == null) || 98 * (first.prev == null && first.item != null) 99 */ 100 transient Node<E> first; 101 102 /** 103 * Pointer to last node. 104 * Invariant: (first == null && last == null) || 105 * (last.next == null && last.item != null) 106 */ 107 transient Node<E> last; 108 109 /** 110 * Constructs an empty list. 111 */ 112 public LinkedList() { 113 } 114 115 /** 116 * Constructs a list containing the elements of the specified 117 * collection, in the order they are returned by the collection's 118 * iterator. 119 * 120 * @param c the collection whose elements are to be placed into this list 121 * @throws NullPointerException if the specified collection is null 122 */ 123 public LinkedList(Collection<? extends E> c) { 124 this(); 125 addAll(c); 126 } 127 128 /** 129 * Links e as first element. 130 */ 131 private void linkFirst(E e) { 132 final Node<E> f = first; 133 final Node<E> newNode = new Node<E>(null, e, f); 134 first = newNode; 135 if (f == null) 136 last = newNode; 137 else 138 f.prev = newNode; 139 size++; 140 modCount++; 141 } 142 143 /** 144 * Links e as last element. 145 */ 146 void linkLast(E e) { 147 final Node<E> l = last; 148 final Node<E> newNode = new Node<E>(l, e, null); 149 last = newNode; 150 if (l == null) 151 first = newNode; 152 else 153 l.next = newNode; 154 size++; 155 modCount++; 156 } 157 158 /** 159 * Inserts element e before non-null Node succ. 160 */ 161 void linkBefore(E e, Node<E> succ) { 162 // assert succ != null; 163 final Node<E> pred = succ.prev; 164 final Node<E> newNode = new Node<E>(pred, e, succ); 165 succ.prev = newNode; 166 if (pred == null) 167 first = newNode; 168 else 169 pred.next = newNode; 170 size++; 171 modCount++; 172 } 173 174 /** 175 * Unlinks non-null first node f. 176 */ 177 private E unlinkFirst(Node<E> f) { 178 // assert f == first && f != null; 179 final E element = f.item; 180 final Node<E> next = f.next; 181 f.item = null; 182 f.next = null; // help GC 183 first = next; 184 if (next == null) 185 last = null; 186 else 187 next.prev = null; 188 size--; 189 modCount++; 190 return element; 191 } 192 193 /** 194 * Unlinks non-null last node l. 195 */ 196 private E unlinkLast(Node<E> l) { 197 // assert l == last && l != null; 198 final E element = l.item; 199 final Node<E> prev = l.prev; 200 l.item = null; 201 l.prev = null; // help GC 202 last = prev; 203 if (prev == null) 204 first = null; 205 else 206 prev.next = null; 207 size--; 208 modCount++; 209 return element; 210 } 211 212 /** 213 * Unlinks non-null node x. 214 */ 215 E unlink(Node<E> x) { 216 // assert x != null; 217 final E element = x.item; 218 final Node<E> next = x.next; 219 final Node<E> prev = x.prev; 220 221 if (prev == null) { 222 first = next; 223 } else { 224 prev.next = next; 225 x.prev = null; 226 } 227 228 if (next == null) { 229 last = prev; 230 } else { 231 next.prev = prev; 232 x.next = null; 233 } 234 235 x.item = null; 236 size--; 237 modCount++; 238 return element; 239 } 240 241 /** 242 * Returns the first element in this list. 243 * 244 * @return the first element in this list 245 * @throws NoSuchElementException if this list is empty 246 */ 247 public E getFirst() { 248 final Node<E> f = first; 249 if (f == null) 250 throw new NoSuchElementException(); 251 return f.item; 252 } 253 254 /** 255 * Returns the last element in this list. 256 * 257 * @return the last element in this list 258 * @throws NoSuchElementException if this list is empty 259 */ 260 public E getLast() { 261 final Node<E> l = last; 262 if (l == null) 263 throw new NoSuchElementException(); 264 return l.item; 265 } 266 267 /** 268 * Removes and returns the first element from this list. 269 * 270 * @return the first element from this list 271 * @throws NoSuchElementException if this list is empty 272 */ 273 public E removeFirst() { 274 final Node<E> f = first; 275 if (f == null) 276 throw new NoSuchElementException(); 277 return unlinkFirst(f); 278 } 279 280 /** 281 * Removes and returns the last element from this list. 282 * 283 * @return the last element from this list 284 * @throws NoSuchElementException if this list is empty 285 */ 286 public E removeLast() { 287 final Node<E> l = last; 288 if (l == null) 289 throw new NoSuchElementException(); 290 return unlinkLast(l); 291 } 292 293 /** 294 * Inserts the specified element at the beginning of this list. 295 * 296 * @param e the element to add 297 */ 298 public void addFirst(E e) { 299 linkFirst(e); 300 } 301 302 /** 303 * Appends the specified element to the end of this list. 304 * 305 * <p>This method is equivalent to {@link #add}. 306 * 307 * @param e the element to add 308 */ 309 public void addLast(E e) { 310 linkLast(e); 311 } 312 313 /** 314 * Returns {@code true} if this list contains the specified element. 315 * More formally, returns {@code true} if and only if this list contains 316 * at least one element {@code e} such that 317 * <tt>(o==null ? e==null : o.equals(e))</tt>. 318 * 319 * @param o element whose presence in this list is to be tested 320 * @return {@code true} if this list contains the specified element 321 */ 322 public boolean contains(Object o) { 323 return indexOf(o) != -1; 324 } 325 326 /** 327 * Returns the number of elements in this list. 328 * 329 * @return the number of elements in this list 330 */ 331 public int size() { 332 return size; 333 } 334 335 /** 336 * Appends the specified element to the end of this list. 337 * 338 * <p>This method is equivalent to {@link #addLast}. 339 * 340 * @param e element to be appended to this list 341 * @return {@code true} (as specified by {@link Collection#add}) 342 */ 343 public boolean add(E e) { 344 linkLast(e); 345 return true; 346 } 347 348 /** 349 * Removes the first occurrence of the specified element from this list, 350 * if it is present. If this list does not contain the element, it is 351 * unchanged. More formally, removes the element with the lowest index 352 * {@code i} such that 353 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> 354 * (if such an element exists). Returns {@code true} if this list 355 * contained the specified element (or equivalently, if this list 356 * changed as a result of the call). 357 * 358 * @param o element to be removed from this list, if present 359 * @return {@code true} if this list contained the specified element 360 */ 361 public boolean remove(Object o) { 362 if (o == null) { 363 for (Node<E> x = first; x != null; x = x.next) { 364 if (x.item == null) { 365 unlink(x); 366 return true; 367 } 368 } 369 } else { 370 for (Node<E> x = first; x != null; x = x.next) { 371 if (o.equals(x.item)) { 372 unlink(x); 373 return true; 374 } 375 } 376 } 377 return false; 378 } 379 380 /** 381 * Appends all of the elements in the specified collection to the end of 382 * this list, in the order that they are returned by the specified 383 * collection's iterator. The behavior of this operation is undefined if 384 * the specified collection is modified while the operation is in 385 * progress. (Note that this will occur if the specified collection is 386 * this list, and it's nonempty.) 387 * 388 * @param c collection containing elements to be added to this list 389 * @return {@code true} if this list changed as a result of the call 390 * @throws NullPointerException if the specified collection is null 391 */ 392 public boolean addAll(Collection<? extends E> c) { 393 return addAll(size, c); 394 } 395 396 /** 397 * Inserts all of the elements in the specified collection into this 398 * list, starting at the specified position. Shifts the element 399 * currently at that position (if any) and any subsequent elements to 400 * the right (increases their indices). The new elements will appear 401 * in the list in the order that they are returned by the 402 * specified collection's iterator. 403 * 404 * @param index index at which to insert the first element 405 * from the specified collection 406 * @param c collection containing elements to be added to this list 407 * @return {@code true} if this list changed as a result of the call 408 * @throws IndexOutOfBoundsException {@inheritDoc} 409 * @throws NullPointerException if the specified collection is null 410 */ 411 public boolean addAll(int index, Collection<? extends E> c) { 412 checkPositionIndex(index); 413 414 Object[] a = c.toArray(); 415 int numNew = a.length; 416 if (numNew == 0) 417 return false; 418 419 Node<E> pred, succ; 420 if (index == size) { 421 succ = null; 422 pred = last; 423 } else { 424 succ = node(index); 425 pred = succ.prev; 426 } 427 428 for (Object o : a) { 429 @SuppressWarnings("unchecked") E e = (E) o; 430 Node<E> newNode = new Node<E>(pred, e, null); 431 if (pred == null) 432 first = newNode; 433 else 434 pred.next = newNode; 435 pred = newNode; 436 } 437 438 if (succ == null) { 439 last = pred; 440 } else { 441 pred.next = succ; 442 succ.prev = pred; 443 } 444 445 size += numNew; 446 modCount++; 447 return true; 448 } 449 450 /** 451 * Removes all of the elements from this list. 452 * The list will be empty after this call returns. 453 */ 454 public void clear() { 455 // Clearing all of the links between nodes is "unnecessary", but: 456 // - helps a generational GC if the discarded nodes inhabit 457 // more than one generation 458 // - is sure to free memory even if there is a reachable Iterator 459 for (Node<E> x = first; x != null; ) { 460 Node<E> next = x.next; 461 x.item = null; 462 x.next = null; 463 x.prev = null; 464 x = next; 465 } 466 first = last = null; 467 size = 0; 468 modCount++; 469 } 470 471 472 // Positional Access Operations 473 474 /** 475 * Returns the element at the specified position in this list. 476 * 477 * @param index index of the element to return 478 * @return the element at the specified position in this list 479 * @throws IndexOutOfBoundsException {@inheritDoc} 480 */ 481 public E get(int index) { 482 checkElementIndex(index); 483 return node(index).item; 484 } 485 486 /** 487 * Replaces the element at the specified position in this list with the 488 * specified element. 489 * 490 * @param index index of the element to replace 491 * @param element element to be stored at the specified position 492 * @return the element previously at the specified position 493 * @throws IndexOutOfBoundsException {@inheritDoc} 494 */ 495 public E set(int index, E element) { 496 checkElementIndex(index); 497 Node<E> x = node(index); 498 E oldVal = x.item; 499 x.item = element; 500 return oldVal; 501 } 502 503 /** 504 * Inserts the specified element at the specified position in this list. 505 * Shifts the element currently at that position (if any) and any 506 * subsequent elements to the right (adds one to their indices). 507 * 508 * @param index index at which the specified element is to be inserted 509 * @param element element to be inserted 510 * @throws IndexOutOfBoundsException {@inheritDoc} 511 */ 512 public void add(int index, E element) { 513 checkPositionIndex(index); 514 515 if (index == size) 516 linkLast(element); 517 else 518 linkBefore(element, node(index)); 519 } 520 521 /** 522 * Removes the element at the specified position in this list. Shifts any 523 * subsequent elements to the left (subtracts one from their indices). 524 * Returns the element that was removed from the list. 525 * 526 * @param index the index of the element to be removed 527 * @return the element previously at the specified position 528 * @throws IndexOutOfBoundsException {@inheritDoc} 529 */ 530 public E remove(int index) { 531 checkElementIndex(index); 532 return unlink(node(index)); 533 } 534 535 /** 536 * Tells if the argument is the index of an existing element. 537 */ 538 private boolean isElementIndex(int index) { 539 return index >= 0 && index < size; 540 } 541 542 /** 543 * Tells if the argument is the index of a valid position for an 544 * iterator or an add operation. 545 */ 546 private boolean isPositionIndex(int index) { 547 return index >= 0 && index <= size; 548 } 549 550 /** 551 * Constructs an IndexOutOfBoundsException detail message. 552 * Of the many possible refactorings of the error handling code, 553 * this "outlining" performs best with both server and client VMs. 554 */ 555 private String outOfBoundsMsg(int index) { 556 return "Index: "+index+", Size: "+size; 557 } 558 559 private void checkElementIndex(int index) { 560 if (!isElementIndex(index)) 561 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 562 } 563 564 private void checkPositionIndex(int index) { 565 if (!isPositionIndex(index)) 566 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 567 } 568 569 /** 570 * Returns the (non-null) Node at the specified element index. 571 */ 572 Node<E> node(int index) { 573 // assert isElementIndex(index); 574 575 if (index < (size >> 1)) { 576 Node<E> x = first; 577 for (int i = 0; i < index; i++) 578 x = x.next; 579 return x; 580 } else { 581 Node<E> x = last; 582 for (int i = size - 1; i > index; i--) 583 x = x.prev; 584 return x; 585 } 586 } 587 588 // Search Operations 589 590 /** 591 * Returns the index of the first occurrence of the specified element 592 * in this list, or -1 if this list does not contain the element. 593 * More formally, returns the lowest index {@code i} such that 594 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 595 * or -1 if there is no such index. 596 * 597 * @param o element to search for 598 * @return the index of the first occurrence of the specified element in 599 * this list, or -1 if this list does not contain the element 600 */ 601 public int indexOf(Object o) { 602 int index = 0; 603 if (o == null) { 604 for (Node<E> x = first; x != null; x = x.next) { 605 if (x.item == null) 606 return index; 607 index++; 608 } 609 } else { 610 for (Node<E> x = first; x != null; x = x.next) { 611 if (o.equals(x.item)) 612 return index; 613 index++; 614 } 615 } 616 return -1; 617 } 618 619 /** 620 * Returns the index of the last occurrence of the specified element 621 * in this list, or -1 if this list does not contain the element. 622 * More formally, returns the highest index {@code i} such that 623 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 624 * or -1 if there is no such index. 625 * 626 * @param o element to search for 627 * @return the index of the last occurrence of the specified element in 628 * this list, or -1 if this list does not contain the element 629 */ 630 public int lastIndexOf(Object o) { 631 int index = size; 632 if (o == null) { 633 for (Node<E> x = last; x != null; x = x.prev) { 634 index--; 635 if (x.item == null) 636 return index; 637 } 638 } else { 639 for (Node<E> x = last; x != null; x = x.prev) { 640 index--; 641 if (o.equals(x.item)) 642 return index; 643 } 644 } 645 return -1; 646 } 647 648 // Queue operations. 649 650 /** 651 * Retrieves, but does not remove, the head (first element) of this list. 652 * 653 * @return the head of this list, or {@code null} if this list is empty 654 * @since 1.5 655 */ 656 public E peek() { 657 final Node<E> f = first; 658 return (f == null) ? null : f.item; 659 } 660 661 /** 662 * Retrieves, but does not remove, the head (first element) of this list. 663 * 664 * @return the head of this list 665 * @throws NoSuchElementException if this list is empty 666 * @since 1.5 667 */ 668 public E element() { 669 return getFirst(); 670 } 671 672 /** 673 * Retrieves and removes the head (first element) of this list. 674 * 675 * @return the head of this list, or {@code null} if this list is empty 676 * @since 1.5 677 */ 678 public E poll() { 679 final Node<E> f = first; 680 return (f == null) ? null : unlinkFirst(f); 681 } 682 683 /** 684 * Retrieves and removes the head (first element) of this list. 685 * 686 * @return the head of this list 687 * @throws NoSuchElementException if this list is empty 688 * @since 1.5 689 */ 690 public E remove() { 691 return removeFirst(); 692 } 693 694 /** 695 * Adds the specified element as the tail (last element) of this list. 696 * 697 * @param e the element to add 698 * @return {@code true} (as specified by {@link Queue#offer}) 699 * @since 1.5 700 */ 701 public boolean offer(E e) { 702 return add(e); 703 } 704 705 // Deque operations 706 /** 707 * Inserts the specified element at the front of this list. 708 * 709 * @param e the element to insert 710 * @return {@code true} (as specified by {@link Deque#offerFirst}) 711 * @since 1.6 712 */ 713 public boolean offerFirst(E e) { 714 addFirst(e); 715 return true; 716 } 717 718 /** 719 * Inserts the specified element at the end of this list. 720 * 721 * @param e the element to insert 722 * @return {@code true} (as specified by {@link Deque#offerLast}) 723 * @since 1.6 724 */ 725 public boolean offerLast(E e) { 726 addLast(e); 727 return true; 728 } 729 730 /** 731 * Retrieves, but does not remove, the first element of this list, 732 * or returns {@code null} if this list is empty. 733 * 734 * @return the first element of this list, or {@code null} 735 * if this list is empty 736 * @since 1.6 737 */ 738 public E peekFirst() { 739 final Node<E> f = first; 740 return (f == null) ? null : f.item; 741 } 742 743 /** 744 * Retrieves, but does not remove, the last element of this list, 745 * or returns {@code null} if this list is empty. 746 * 747 * @return the last element of this list, or {@code null} 748 * if this list is empty 749 * @since 1.6 750 */ 751 public E peekLast() { 752 final Node<E> l = last; 753 return (l == null) ? null : l.item; 754 } 755 756 /** 757 * Retrieves and removes the first element of this list, 758 * or returns {@code null} if this list is empty. 759 * 760 * @return the first element of this list, or {@code null} if 761 * this list is empty 762 * @since 1.6 763 */ 764 public E pollFirst() { 765 final Node<E> f = first; 766 return (f == null) ? null : unlinkFirst(f); 767 } 768 769 /** 770 * Retrieves and removes the last element of this list, 771 * or returns {@code null} if this list is empty. 772 * 773 * @return the last element of this list, or {@code null} if 774 * this list is empty 775 * @since 1.6 776 */ 777 public E pollLast() { 778 final Node<E> l = last; 779 return (l == null) ? null : unlinkLast(l); 780 } 781 782 /** 783 * Pushes an element onto the stack represented by this list. In other 784 * words, inserts the element at the front of this list. 785 * 786 * <p>This method is equivalent to {@link #addFirst}. 787 * 788 * @param e the element to push 789 * @since 1.6 790 */ 791 public void push(E e) { 792 addFirst(e); 793 } 794 795 /** 796 * Pops an element from the stack represented by this list. In other 797 * words, removes and returns the first element of this list. 798 * 799 * <p>This method is equivalent to {@link #removeFirst()}. 800 * 801 * @return the element at the front of this list (which is the top 802 * of the stack represented by this list) 803 * @throws NoSuchElementException if this list is empty 804 * @since 1.6 805 */ 806 public E pop() { 807 return removeFirst(); 808 } 809 810 /** 811 * Removes the first occurrence of the specified element in this 812 * list (when traversing the list from head to tail). If the list 813 * does not contain the element, it is unchanged. 814 * 815 * @param o element to be removed from this list, if present 816 * @return {@code true} if the list contained the specified element 817 * @since 1.6 818 */ 819 public boolean removeFirstOccurrence(Object o) { 820 return remove(o); 821 } 822 823 /** 824 * Removes the last occurrence of the specified element in this 825 * list (when traversing the list from head to tail). If the list 826 * does not contain the element, it is unchanged. 827 * 828 * @param o element to be removed from this list, if present 829 * @return {@code true} if the list contained the specified element 830 * @since 1.6 831 */ 832 public boolean removeLastOccurrence(Object o) { 833 if (o == null) { 834 for (Node<E> x = last; x != null; x = x.prev) { 835 if (x.item == null) { 836 unlink(x); 837 return true; 838 } 839 } 840 } else { 841 for (Node<E> x = last; x != null; x = x.prev) { 842 if (o.equals(x.item)) { 843 unlink(x); 844 return true; 845 } 846 } 847 } 848 return false; 849 } 850 851 /** 852 * Returns a list-iterator of the elements in this list (in proper 853 * sequence), starting at the specified position in the list. 854 * Obeys the general contract of {@code List.listIterator(int)}.<p> 855 * 856 * The list-iterator is <i>fail-fast</i>: if the list is structurally 857 * modified at any time after the Iterator is created, in any way except 858 * through the list-iterator's own {@code remove} or {@code add} 859 * methods, the list-iterator will throw a 860 * {@code ConcurrentModificationException}. Thus, in the face of 861 * concurrent modification, the iterator fails quickly and cleanly, rather 862 * than risking arbitrary, non-deterministic behavior at an undetermined 863 * time in the future. 864 * 865 * @param index index of the first element to be returned from the 866 * list-iterator (by a call to {@code next}) 867 * @return a ListIterator of the elements in this list (in proper 868 * sequence), starting at the specified position in the list 869 * @throws IndexOutOfBoundsException {@inheritDoc} 870 * @see List#listIterator(int) 871 */ 872 public ListIterator<E> listIterator(int index) { 873 checkPositionIndex(index); 874 return new ListItr(index); 875 } 876 877 private class ListItr implements ListIterator<E> { 878 private Node<E> lastReturned = null; 879 private Node<E> next; 880 private int nextIndex; 881 private int expectedModCount = modCount; 882 883 ListItr(int index) { 884 // assert isPositionIndex(index); 885 next = (index == size) ? null : node(index); 886 nextIndex = index; 887 } 888 889 public boolean hasNext() { 890 return nextIndex < size; 891 } 892 893 public E next() { 894 checkForComodification(); 895 if (!hasNext()) 896 throw new NoSuchElementException(); 897 898 lastReturned = next; 899 next = next.next; 900 nextIndex++; 901 return lastReturned.item; 902 } 903 904 public boolean hasPrevious() { 905 return nextIndex > 0; 906 } 907 908 public E previous() { 909 checkForComodification(); 910 if (!hasPrevious()) 911 throw new NoSuchElementException(); 912 913 lastReturned = next = (next == null) ? last : next.prev; 914 nextIndex--; 915 return lastReturned.item; 916 } 917 918 public int nextIndex() { 919 return nextIndex; 920 } 921 922 public int previousIndex() { 923 return nextIndex - 1; 924 } 925 926 public void remove() { 927 checkForComodification(); 928 if (lastReturned == null) 929 throw new IllegalStateException(); 930 931 Node<E> lastNext = lastReturned.next; 932 unlink(lastReturned); 933 if (next == lastReturned) 934 next = lastNext; 935 else 936 nextIndex--; 937 lastReturned = null; 938 expectedModCount++; 939 } 940 941 public void set(E e) { 942 if (lastReturned == null) 943 throw new IllegalStateException(); 944 checkForComodification(); 945 lastReturned.item = e; 946 } 947 948 public void add(E e) { 949 checkForComodification(); 950 lastReturned = null; 951 if (next == null) 952 linkLast(e); 953 else 954 linkBefore(e, next); 955 nextIndex++; 956 expectedModCount++; 957 } 958 959 final void checkForComodification() { 960 if (modCount != expectedModCount) 961 throw new ConcurrentModificationException(); 962 } 963 } 964 965 private static class Node<E> { 966 E item; 967 Node<E> next; 968 Node<E> prev; 969 970 Node(Node<E> prev, E element, Node<E> next) { 971 this.item = element; 972 this.next = next; 973 this.prev = prev; 974 } 975 } 976 977 /** 978 * @since 1.6 979 */ 980 public Iterator<E> descendingIterator() { 981 return new DescendingIterator(); 982 } 983 984 /** 985 * Adapter to provide descending iterators via ListItr.previous 986 */ 987 private class DescendingIterator implements Iterator<E> { 988 private final ListItr itr = new ListItr(size()); 989 public boolean hasNext() { 990 return itr.hasPrevious(); 991 } 992 public E next() { 993 return itr.previous(); 994 } 995 public void remove() { 996 itr.remove(); 997 } 998 } 999 1000 @SuppressWarnings("unchecked") 1001 private LinkedList<E> superClone() { 1002 try { 1003 return (LinkedList<E>) super.clone(); 1004 } catch (CloneNotSupportedException e) { 1005 throw new InternalError(); 1006 } 1007 } 1008 1009 /** 1010 * Returns a shallow copy of this {@code LinkedList}. (The elements 1011 * themselves are not cloned.) 1012 * 1013 * @return a shallow copy of this {@code LinkedList} instance 1014 */ 1015 public Object clone() { 1016 LinkedList<E> clone = superClone(); 1017 1018 // Put clone into "virgin" state 1019 clone.first = clone.last = null; 1020 clone.size = 0; 1021 clone.modCount = 0; 1022 1023 // Initialize clone with our elements 1024 for (Node<E> x = first; x != null; x = x.next) 1025 clone.add(x.item); 1026 1027 return clone; 1028 } 1029 1030 /** 1031 * Returns an array containing all of the elements in this list 1032 * in proper sequence (from first to last element). 1033 * 1034 * <p>The returned array will be "safe" in that no references to it are 1035 * maintained by this list. (In other words, this method must allocate 1036 * a new array). The caller is thus free to modify the returned array. 1037 * 1038 * <p>This method acts as bridge between array-based and collection-based 1039 * APIs. 1040 * 1041 * @return an array containing all of the elements in this list 1042 * in proper sequence 1043 */ 1044 public Object[] toArray() { 1045 Object[] result = new Object[size]; 1046 int i = 0; 1047 for (Node<E> x = first; x != null; x = x.next) 1048 result[i++] = x.item; 1049 return result; 1050 } 1051 1052 /** 1053 * Returns an array containing all of the elements in this list in 1054 * proper sequence (from first to last element); the runtime type of 1055 * the returned array is that of the specified array. If the list fits 1056 * in the specified array, it is returned therein. Otherwise, a new 1057 * array is allocated with the runtime type of the specified array and 1058 * the size of this list. 1059 * 1060 * <p>If the list fits in the specified array with room to spare (i.e., 1061 * the array has more elements than the list), the element in the array 1062 * immediately following the end of the list is set to {@code null}. 1063 * (This is useful in determining the length of the list <i>only</i> if 1064 * the caller knows that the list does not contain any null elements.) 1065 * 1066 * <p>Like the {@link #toArray()} method, this method acts as bridge between 1067 * array-based and collection-based APIs. Further, this method allows 1068 * precise control over the runtime type of the output array, and may, 1069 * under certain circumstances, be used to save allocation costs. 1070 * 1071 * <p>Suppose {@code x} is a list known to contain only strings. 1072 * The following code can be used to dump the list into a newly 1073 * allocated array of {@code String}: 1074 * 1075 * <pre> 1076 * String[] y = x.toArray(new String[0]);</pre> 1077 * 1078 * Note that {@code toArray(new Object[0])} is identical in function to 1079 * {@code toArray()}. 1080 * 1081 * @param a the array into which the elements of the list are to 1082 * be stored, if it is big enough; otherwise, a new array of the 1083 * same runtime type is allocated for this purpose. 1084 * @return an array containing the elements of the list 1085 * @throws ArrayStoreException if the runtime type of the specified array 1086 * is not a supertype of the runtime type of every element in 1087 * this list 1088 * @throws NullPointerException if the specified array is null 1089 */ 1090 @SuppressWarnings("unchecked") 1091 public <T> T[] toArray(T[] a) { 1092 if (a.length < size) 1093 a = (T[])java.lang.reflect.Array.newInstance( 1094 a.getClass().getComponentType(), size); 1095 int i = 0; 1096 Object[] result = a; 1097 for (Node<E> x = first; x != null; x = x.next) 1098 result[i++] = x.item; 1099 1100 if (a.length > size) 1101 a[size] = null; 1102 1103 return a; 1104 } 1105 1106 private static final long serialVersionUID = 876323262645176354L; 1107 1108 /** 1109 * Saves the state of this {@code LinkedList} instance to a stream 1110 * (that is, serializes it). 1111 * 1112 * @serialData The size of the list (the number of elements it 1113 * contains) is emitted (int), followed by all of its 1114 * elements (each an Object) in the proper order. 1115 */ 1116 private void writeObject(java.io.ObjectOutputStream s) 1117 throws java.io.IOException { 1118 // Write out any hidden serialization magic 1119 s.defaultWriteObject(); 1120 1121 // Write out size 1122 s.writeInt(size); 1123 1124 // Write out all elements in the proper order. 1125 for (Node<E> x = first; x != null; x = x.next) 1126 s.writeObject(x.item); 1127 } 1128 1129 /** 1130 * Reconstitutes this {@code LinkedList} instance from a stream 1131 * (that is, deserializes it). 1132 */ 1133 @SuppressWarnings("unchecked") 1134 private void readObject(java.io.ObjectInputStream s) 1135 throws java.io.IOException, ClassNotFoundException { 1136 // Read in any hidden serialization magic 1137 s.defaultReadObject(); 1138 1139 // Read in size 1140 int size = s.readInt(); 1141 1142 // Read in all elements in the proper order. 1143 for (int i = 0; i < size; i++) 1144 linkLast((E)s.readObject()); 1145 } 1146 }