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