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>, 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 (0 <= location && 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 * Constructs a new empty instance of {@code LinkedList}. 186 */ 187 public LinkedList() { 188 voidLink = new Link<E>(null, null, null); 189 voidLink.previous = voidLink; 190 voidLink.next = voidLink; 191 } 192 193 /** 194 * Constructs a new instance of {@code LinkedList} that holds all of the 195 * elements contained in the specified {@code collection}. The order of the 196 * elements in this new {@code LinkedList} will be determined by the 197 * iteration order of {@code collection}. 198 * 199 * @param collection 200 * the collection of elements to add. 201 */ 202 public LinkedList(Collection<? extends E> collection) { 203 this(); 204 addAll(collection); 205 } 206 207 /** 208 * Inserts the specified object into this {@code LinkedList} at the 209 * specified location. The object is inserted before any previous element at 210 * the specified location. If the location is equal to the size of this 211 * {@code LinkedList}, the object is added at the end. 212 * 213 * @param location 214 * the index at which to insert. 215 * @param object 216 * the object to add. 217 * @throws IndexOutOfBoundsException 218 * if {@code location < 0 || >= size()} 219 */ 220 @Override 221 public void add(int location, E object) { 222 if (0 <= location && location <= size) { 223 Link<E> link = voidLink; 224 if (location < (size / 2)) { 225 for (int i = 0; i <= location; i++) { 226 link = link.next; 227 } 228 } else { 229 for (int i = size; i > location; i--) { 230 link = link.previous; 231 } 232 } 233 Link<E> previous = link.previous; 234 Link<E> newLink = new Link<E>(object, previous, link); 235 previous.next = newLink; 236 link.previous = newLink; 237 size++; 238 modCount++; 239 } else { 240 throw new IndexOutOfBoundsException(); 241 } 242 } 243 244 /** 245 * Adds the specified object at the end of this {@code LinkedList}. 246 * 247 * @param object 248 * the object to add. 249 * @return always true 250 */ 251 @Override 252 public boolean add(E object) { 253 // Cannot call addLast() as subclasses can override 254 Link<E> oldLast = voidLink.previous; 255 Link<E> newLink = new Link<E>(object, oldLast, voidLink); 256 voidLink.previous = newLink; 257 oldLast.next = newLink; 258 size++; 259 modCount++; 260 return true; 261 } 262 263 /** 264 * Inserts the objects in the specified collection at the specified location 265 * in this {@code LinkedList}. The objects are added in the order they are 266 * returned from the collection's iterator. 267 * 268 * @param location 269 * the index at which to insert. 270 * @param collection 271 * the collection of objects 272 * @return {@code true} if this {@code LinkedList} is modified, 273 * {@code false} otherwise. 274 * @throws ClassCastException 275 * if the class of an object is inappropriate for this list. 276 * @throws IllegalArgumentException 277 * if an object cannot be added to this list. 278 * @throws IndexOutOfBoundsException 279 * if {@code location < 0 || > size()} 280 */ 281 @Override 282 public boolean addAll(int location, Collection<? extends E> collection) { 283 if (location < 0 || location > size) { 284 throw new IndexOutOfBoundsException(); 285 } 286 int adding = collection.size(); 287 if (adding == 0) { 288 return false; 289 } 290 Collection<? extends E> elements = (collection == this) ? 291 new ArrayList<E>(collection) : collection; 292 293 Link<E> previous = voidLink; 294 if (location < (size / 2)) { 295 for (int i = 0; i < location; i++) { 296 previous = previous.next; 297 } 298 } else { 299 for (int i = size; i >= location; i--) { 300 previous = previous.previous; 301 } 302 } 303 Link<E> next = previous.next; 304 for (E e : elements) { 305 Link<E> newLink = new Link<E>(e, previous, null); 306 previous.next = newLink; 307 previous = newLink; 308 } 309 previous.next = next; 310 next.previous = previous; 311 size += adding; 312 modCount++; 313 return true; 314 } 315 316 /** 317 * Adds the objects in the specified Collection to this {@code LinkedList}. 318 * 319 * @param collection 320 * the collection of objects. 321 * @return {@code true} if this {@code LinkedList} is modified, 322 * {@code false} otherwise. 323 */ 324 @Override 325 public boolean addAll(Collection<? extends E> collection) { 326 int adding = collection.size(); 327 if (adding == 0) { 328 return false; 329 } 330 Collection<? extends E> elements = (collection == this) ? 331 new ArrayList<E>(collection) : collection; 332 333 Link<E> previous = voidLink.previous; 334 for (E e : elements) { 335 Link<E> newLink = new Link<E>(e, previous, null); 336 previous.next = newLink; 337 previous = newLink; 338 } 339 previous.next = voidLink; 340 voidLink.previous = previous; 341 size += adding; 342 modCount++; 343 return true; 344 } 345 346 /** 347 * Adds the specified object at the beginning of this {@code LinkedList}. 348 * 349 * @param object 350 * the object to add. 351 */ 352 public void addFirst(E object) { 353 Link<E> oldFirst = voidLink.next; 354 Link<E> newLink = new Link<E>(object, voidLink, oldFirst); 355 voidLink.next = newLink; 356 oldFirst.previous = newLink; 357 size++; 358 modCount++; 359 } 360 361 /** 362 * Adds the specified object at the end of this {@code LinkedList}. 363 * 364 * @param object 365 * the object to add. 366 */ 367 public void addLast(E object) { 368 Link<E> oldLast = voidLink.previous; 369 Link<E> newLink = new Link<E>(object, oldLast, voidLink); 370 voidLink.previous = newLink; 371 oldLast.next = newLink; 372 size++; 373 modCount++; 374 } 375 376 /** 377 * Removes all elements from this {@code LinkedList}, leaving it empty. 378 * 379 * @see List#isEmpty 380 * @see #size 381 */ 382 @Override 383 public void clear() { 384 if (size > 0) { 385 size = 0; 386 voidLink.next = voidLink; 387 voidLink.previous = voidLink; 388 modCount++; 389 } 390 } 391 392 /** 393 * Returns a new {@code LinkedList} with the same elements and size as this 394 * {@code LinkedList}. 395 * 396 * @return a shallow copy of this {@code LinkedList}. 397 * @see java.lang.Cloneable 398 */ 399 @SuppressWarnings("unchecked") 400 @Override 401 public Object clone() { 402 try { 403 LinkedList<E> l = (LinkedList<E>) super.clone(); 404 l.size = 0; 405 l.voidLink = new Link<E>(null, null, null); 406 l.voidLink.previous = l.voidLink; 407 l.voidLink.next = l.voidLink; 408 l.addAll(this); 409 return l; 410 } catch (CloneNotSupportedException e) { 411 throw new AssertionError(e); // android-changed 412 } 413 } 414 415 /** 416 * Searches this {@code LinkedList} for the specified object. 417 * 418 * @param object 419 * the object to search for. 420 * @return {@code true} if {@code object} is an element of this 421 * {@code LinkedList}, {@code false} otherwise 422 */ 423 @Override 424 public boolean contains(Object object) { 425 Link<E> link = voidLink.next; 426 if (object != null) { 427 while (link != voidLink) { 428 if (object.equals(link.data)) { 429 return true; 430 } 431 link = link.next; 432 } 433 } else { 434 while (link != voidLink) { 435 if (link.data == null) { 436 return true; 437 } 438 link = link.next; 439 } 440 } 441 return false; 442 } 443 444 @Override 445 public E get(int location) { 446 if (0 <= location && location < size) { 447 Link<E> link = voidLink; 448 if (location < (size / 2)) { 449 for (int i = 0; i <= location; i++) { 450 link = link.next; 451 } 452 } else { 453 for (int i = size; i > location; i--) { 454 link = link.previous; 455 } 456 } 457 return link.data; 458 } 459 throw new IndexOutOfBoundsException(); 460 } 461 462 /** 463 * Returns the first element in this {@code LinkedList}. 464 * 465 * @return the first element. 466 * @throws NoSuchElementException 467 * if this {@code LinkedList} is empty. 468 */ 469 public E getFirst() { 470 Link<E> first = voidLink.next; 471 if (first != voidLink) { 472 return first.data; 473 } 474 throw new NoSuchElementException(); 475 } 476 477 /** 478 * Returns the last element in this {@code LinkedList}. 479 * 480 * @return the last element 481 * @throws NoSuchElementException 482 * if this {@code LinkedList} is empty 483 */ 484 public E getLast() { 485 Link<E> last = voidLink.previous; 486 if (last != voidLink) { 487 return last.data; 488 } 489 throw new NoSuchElementException(); 490 } 491 492 @Override 493 public int indexOf(Object object) { 494 int pos = 0; 495 Link<E> link = voidLink.next; 496 if (object != null) { 497 while (link != voidLink) { 498 if (object.equals(link.data)) { 499 return pos; 500 } 501 link = link.next; 502 pos++; 503 } 504 } else { 505 while (link != voidLink) { 506 if (link.data == null) { 507 return pos; 508 } 509 link = link.next; 510 pos++; 511 } 512 } 513 return -1; 514 } 515 516 /** 517 * Searches this {@code LinkedList} for the specified object and returns the 518 * index of the last occurrence. 519 * 520 * @param object 521 * the object to search for 522 * @return the index of the last occurrence of the object, or -1 if it was 523 * not found. 524 */ 525 @Override 526 public int lastIndexOf(Object object) { 527 int pos = size; 528 Link<E> link = voidLink.previous; 529 if (object != null) { 530 while (link != voidLink) { 531 pos--; 532 if (object.equals(link.data)) { 533 return pos; 534 } 535 link = link.previous; 536 } 537 } else { 538 while (link != voidLink) { 539 pos--; 540 if (link.data == null) { 541 return pos; 542 } 543 link = link.previous; 544 } 545 } 546 return -1; 547 } 548 549 /** 550 * Returns a ListIterator on the elements of this {@code LinkedList}. The 551 * elements are iterated in the same order that they occur in the 552 * {@code LinkedList}. The iteration starts at the specified location. 553 * 554 * @param location 555 * the index at which to start the iteration 556 * @return a ListIterator on the elements of this {@code LinkedList} 557 * @throws IndexOutOfBoundsException 558 * if {@code location < 0 || >= size()} 559 * @see ListIterator 560 */ 561 @Override 562 public ListIterator<E> listIterator(int location) { 563 return new LinkIterator<E>(this, location); 564 } 565 566 /** 567 * Removes the object at the specified location from this {@code LinkedList}. 568 * 569 * @param location 570 * the index of the object to remove 571 * @return the removed object 572 * @throws IndexOutOfBoundsException 573 * if {@code location < 0 || >= size()} 574 */ 575 @Override 576 public E remove(int location) { 577 if (0 <= location && location < size) { 578 Link<E> link = voidLink; 579 if (location < (size / 2)) { 580 for (int i = 0; i <= location; i++) { 581 link = link.next; 582 } 583 } else { 584 for (int i = size; i > location; i--) { 585 link = link.previous; 586 } 587 } 588 Link<E> previous = link.previous; 589 Link<E> next = link.next; 590 previous.next = next; 591 next.previous = previous; 592 size--; 593 modCount++; 594 return link.data; 595 } 596 throw new IndexOutOfBoundsException(); 597 } 598 599 @Override 600 public boolean remove(Object object) { 601 Link<E> link = voidLink.next; 602 if (object != null) { 603 while (link != voidLink && !object.equals(link.data)) { 604 link = link.next; 605 } 606 } else { 607 while (link != voidLink && link.data != null) { 608 link = link.next; 609 } 610 } 611 if (link == voidLink) { 612 return false; 613 } 614 Link<E> next = link.next; 615 Link<E> previous = link.previous; 616 previous.next = next; 617 next.previous = previous; 618 size--; 619 modCount++; 620 return true; 621 } 622 623 /** 624 * Removes the first object from this {@code LinkedList}. 625 * 626 * @return the removed object. 627 * @throws NoSuchElementException 628 * if this {@code LinkedList} is empty. 629 */ 630 public E removeFirst() { 631 Link<E> first = voidLink.next; 632 if (first != voidLink) { 633 Link<E> next = first.next; 634 voidLink.next = next; 635 next.previous = voidLink; 636 size--; 637 modCount++; 638 return first.data; 639 } 640 throw new NoSuchElementException(); 641 } 642 643 /** 644 * Removes the last object from this {@code LinkedList}. 645 * 646 * @return the removed object. 647 * @throws NoSuchElementException 648 * if this {@code LinkedList} is empty. 649 */ 650 public E removeLast() { 651 Link<E> last = voidLink.previous; 652 if (last != voidLink) { 653 Link<E> previous = last.previous; 654 voidLink.previous = previous; 655 previous.next = voidLink; 656 size--; 657 modCount++; 658 return last.data; 659 } 660 throw new NoSuchElementException(); 661 } 662 663 /** 664 * Replaces the element at the specified location in this {@code LinkedList} 665 * with the specified object. 666 * 667 * @param location 668 * the index at which to put the specified object. 669 * @param object 670 * the object to add. 671 * @return the previous element at the index. 672 * @throws ClassCastException 673 * if the class of an object is inappropriate for this list. 674 * @throws IllegalArgumentException 675 * if an object cannot be added to this list. 676 * @throws IndexOutOfBoundsException 677 * if {@code location < 0 || >= size()} 678 */ 679 @Override 680 public E set(int location, E object) { 681 if (0 <= location && location < size) { 682 Link<E> link = voidLink; 683 if (location < (size / 2)) { 684 for (int i = 0; i <= location; i++) { 685 link = link.next; 686 } 687 } else { 688 for (int i = size; i > location; i--) { 689 link = link.previous; 690 } 691 } 692 E result = link.data; 693 link.data = object; 694 return result; 695 } 696 throw new IndexOutOfBoundsException(); 697 } 698 699 /** 700 * Returns the number of elements in this {@code LinkedList}. 701 * 702 * @return the number of elements in this {@code LinkedList}. 703 */ 704 @Override 705 public int size() { 706 return size; 707 } 708 709 public boolean offer(E o) { 710 add(o); 711 return true; 712 } 713 714 public E poll() { 715 return size == 0 ? null : removeFirst(); 716 } 717 718 public E remove() { 719 return removeFirst(); 720 } 721 722 public E peek() { 723 Link<E> first = voidLink.next; 724 return first == voidLink ? null : first.data; 725 } 726 727 public E element() { 728 return getFirst(); 729 } 730 731 /** 732 * Returns a new array containing all elements contained in this 733 * {@code LinkedList}. 734 * 735 * @return an array of the elements from this {@code LinkedList}. 736 */ 737 @Override 738 public Object[] toArray() { 739 int index = 0; 740 Object[] contents = new Object[size]; 741 Link<E> link = voidLink.next; 742 while (link != voidLink) { 743 contents[index++] = link.data; 744 link = link.next; 745 } 746 return contents; 747 } 748 749 /** 750 * Returns an array containing all elements contained in this 751 * {@code LinkedList}. If the specified array is large enough to hold the 752 * elements, the specified array is used, otherwise an array of the same 753 * type is created. If the specified array is used and is larger than this 754 * {@code LinkedList}, the array element following the collection elements 755 * is set to null. 756 * 757 * @param contents 758 * the array. 759 * @return an array of the elements from this {@code LinkedList}. 760 * @throws ArrayStoreException 761 * if the type of an element in this {@code LinkedList} cannot 762 * be stored in the type of the specified array. 763 */ 764 @Override 765 @SuppressWarnings("unchecked") 766 public <T> T[] toArray(T[] contents) { 767 int index = 0; 768 if (size > contents.length) { 769 Class<?> ct = contents.getClass().getComponentType(); 770 contents = (T[]) Array.newInstance(ct, size); 771 } 772 Link<E> link = voidLink.next; 773 while (link != voidLink) { 774 contents[index++] = (T) link.data; 775 link = link.next; 776 } 777 if (index < contents.length) { 778 contents[index] = null; 779 } 780 return contents; 781 } 782 783 private void writeObject(ObjectOutputStream stream) throws IOException { 784 stream.defaultWriteObject(); 785 stream.writeInt(size); 786 Iterator<E> it = iterator(); 787 while (it.hasNext()) { 788 stream.writeObject(it.next()); 789 } 790 } 791 792 @SuppressWarnings("unchecked") 793 private void readObject(ObjectInputStream stream) throws IOException, 794 ClassNotFoundException { 795 stream.defaultReadObject(); 796 size = stream.readInt(); 797 voidLink = new Link<E>(null, null, null); 798 Link<E> link = voidLink; 799 for (int i = size; --i >= 0;) { 800 Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null); 801 link.next = nextLink; 802 link = nextLink; 803 } 804 link.next = voidLink; 805 voidLink.previous = link; 806 } 807} 808