001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.list; 018 019import java.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.lang.reflect.Array; 023import java.util.AbstractList; 024import java.util.Collection; 025import java.util.ConcurrentModificationException; 026import java.util.Iterator; 027import java.util.List; 028import java.util.ListIterator; 029import java.util.NoSuchElementException; 030import java.util.Objects; 031 032import org.apache.commons.collections4.CollectionUtils; 033import org.apache.commons.collections4.OrderedIterator; 034 035/** 036 * An abstract implementation of a linked list which provides numerous points for 037 * subclasses to override. 038 * <p> 039 * Overridable methods are provided to change the storage node and to change how 040 * nodes are added to and removed. Hopefully, all you need for unusual subclasses 041 * is here. 042 * </p> 043 * 044 * @param <E> the type of elements in this list 045 * @since 3.0 046 */ 047public abstract class AbstractLinkedList<E> implements List<E> { 048 049 /* 050 * Implementation notes: 051 * - a standard circular doubly-linked list 052 * - a marker node is stored to mark the start and the end of the list 053 * - node creation and removal always occurs through createNode() and 054 * removeNode(). 055 * - a modification count is kept, with the same semantics as 056 * {@link java.util.LinkedList}. 057 * - respects {@link AbstractList#modCount} 058 */ 059 060 /** 061 * A list iterator over the linked list. 062 * 063 * @param <E> the type of elements in this iterator. 064 */ 065 protected static class LinkedListIterator<E> implements ListIterator<E>, OrderedIterator<E> { 066 067 /** The parent list */ 068 protected final AbstractLinkedList<E> parent; 069 070 /** 071 * The node that will be returned by {@link #next()}. If this is equal 072 * to {@link AbstractLinkedList#header} then there are no more values to return. 073 */ 074 protected Node<E> next; 075 076 /** 077 * The index of {@link #next}. 078 */ 079 protected int nextIndex; 080 081 /** 082 * The last node that was returned by {@link #next()} or {@link 083 * #previous()}. Set to {@code null} if {@link #next()} or {@link 084 * #previous()} haven't been called, or if the node has been removed 085 * with {@link #remove()} or a new node added with {@link #add(Object)}. 086 * Should be accessed through {@link #getLastNodeReturned()} to enforce 087 * this behavior. 088 */ 089 protected Node<E> current; 090 091 /** 092 * The modification count that the list is expected to have. If the list 093 * doesn't have this count, then a 094 * {@link java.util.ConcurrentModificationException} may be thrown by 095 * the operations. 096 */ 097 protected int expectedModCount; 098 099 /** 100 * Create a ListIterator for a list. 101 * 102 * @param parent the parent list 103 * @param fromIndex the index to start at 104 * @throws IndexOutOfBoundsException if fromIndex is less than 0 or greater than the size of the list 105 */ 106 protected LinkedListIterator(final AbstractLinkedList<E> parent, final int fromIndex) 107 throws IndexOutOfBoundsException { 108 this.parent = parent; 109 this.expectedModCount = parent.modCount; 110 this.next = parent.getNode(fromIndex, true); 111 this.nextIndex = fromIndex; 112 } 113 114 @Override 115 public void add(final E obj) { 116 checkModCount(); 117 parent.addNodeBefore(next, obj); 118 current = null; 119 nextIndex++; 120 expectedModCount++; 121 } 122 123 /** 124 * Checks the modification count of the list is the value that this 125 * object expects. 126 * 127 * @throws ConcurrentModificationException If the list's modification 128 * count isn't the value that was expected. 129 */ 130 protected void checkModCount() { 131 if (parent.modCount != expectedModCount) { 132 throw new ConcurrentModificationException(); 133 } 134 } 135 136 /** 137 * Gets the last node returned. 138 * 139 * @return the last node returned 140 * @throws IllegalStateException If {@link #next()} or {@link #previous()} haven't been called, 141 * or if the node has been removed with {@link #remove()} or a new node added with {@link #add(Object)}. 142 */ 143 protected Node<E> getLastNodeReturned() throws IllegalStateException { 144 if (current == null) { 145 throw new IllegalStateException(); 146 } 147 return current; 148 } 149 150 @Override 151 public boolean hasNext() { 152 return next != parent.header; 153 } 154 155 @Override 156 public boolean hasPrevious() { 157 return next.previous != parent.header; 158 } 159 160 @Override 161 public E next() { 162 checkModCount(); 163 if (!hasNext()) { 164 throw new NoSuchElementException("No element at index " + nextIndex + "."); 165 } 166 final E value = next.getValue(); 167 current = next; 168 next = next.next; 169 nextIndex++; 170 return value; 171 } 172 173 @Override 174 public int nextIndex() { 175 return nextIndex; 176 } 177 178 @Override 179 public E previous() { 180 checkModCount(); 181 if (!hasPrevious()) { 182 throw new NoSuchElementException("Already at start of list."); 183 } 184 next = next.previous; 185 final E value = next.getValue(); 186 current = next; 187 nextIndex--; 188 return value; 189 } 190 191 @Override 192 public int previousIndex() { 193 // not normally overridden, as relative to nextIndex() 194 return nextIndex() - 1; 195 } 196 197 @Override 198 public void remove() { 199 checkModCount(); 200 if (current == next) { 201 // remove() following previous() 202 next = next.next; 203 parent.removeNode(getLastNodeReturned()); 204 } else { 205 // remove() following next() 206 parent.removeNode(getLastNodeReturned()); 207 nextIndex--; 208 } 209 current = null; 210 expectedModCount++; 211 } 212 213 @Override 214 public void set(final E obj) { 215 checkModCount(); 216 getLastNodeReturned().setValue(obj); 217 } 218 219 } 220 221 /** 222 * The sublist implementation for AbstractLinkedList. 223 * 224 * @param <E> the type of elements in this list. 225 */ 226 protected static class LinkedSubList<E> extends AbstractList<E> { 227 /** The main list */ 228 AbstractLinkedList<E> parent; 229 /** Offset from the main list */ 230 int offset; 231 /** Sublist size */ 232 int size; 233 /** Sublist modCount */ 234 int expectedModCount; 235 236 protected LinkedSubList(final AbstractLinkedList<E> parent, final int fromIndex, final int toIndex) { 237 if (fromIndex < 0) { 238 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 239 } 240 if (toIndex > parent.size()) { 241 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 242 } 243 if (fromIndex > toIndex) { 244 throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); 245 } 246 this.parent = parent; 247 this.offset = fromIndex; 248 this.size = toIndex - fromIndex; 249 this.expectedModCount = parent.modCount; 250 } 251 252 @Override 253 public void add(final int index, final E obj) { 254 rangeCheck(index, size + 1); 255 checkModCount(); 256 parent.add(index + offset, obj); 257 expectedModCount = parent.modCount; 258 size++; 259 modCount++; 260 } 261 262 @Override 263 public boolean addAll(final Collection<? extends E> coll) { 264 return addAll(size, coll); 265 } 266 267 @Override 268 public boolean addAll(final int index, final Collection<? extends E> coll) { 269 rangeCheck(index, size + 1); 270 final int cSize = coll.size(); 271 if (cSize == 0) { 272 return false; 273 } 274 275 checkModCount(); 276 parent.addAll(offset + index, coll); 277 expectedModCount = parent.modCount; 278 size += cSize; 279 modCount++; 280 return true; 281 } 282 283 protected void checkModCount() { 284 if (parent.modCount != expectedModCount) { 285 throw new ConcurrentModificationException(); 286 } 287 } 288 289 @Override 290 public void clear() { 291 checkModCount(); 292 final Iterator<E> it = iterator(); 293 while (it.hasNext()) { 294 it.next(); 295 it.remove(); 296 } 297 } 298 299 @Override 300 public E get(final int index) { 301 rangeCheck(index, size); 302 checkModCount(); 303 return parent.get(index + offset); 304 } 305 306 @Override 307 public Iterator<E> iterator() { 308 checkModCount(); 309 return parent.createSubListIterator(this); 310 } 311 312 @Override 313 public ListIterator<E> listIterator(final int index) { 314 rangeCheck(index, size + 1); 315 checkModCount(); 316 return parent.createSubListListIterator(this, index); 317 } 318 319 protected void rangeCheck(final int index, final int beyond) { 320 if (index < 0 || index >= beyond) { 321 throw new IndexOutOfBoundsException("Index '" + index + "' out of bounds for size '" + size + "'"); 322 } 323 } 324 325 @Override 326 public E remove(final int index) { 327 rangeCheck(index, size); 328 checkModCount(); 329 final E result = parent.remove(index + offset); 330 expectedModCount = parent.modCount; 331 size--; 332 modCount++; 333 return result; 334 } 335 336 @Override 337 public E set(final int index, final E obj) { 338 rangeCheck(index, size); 339 checkModCount(); 340 return parent.set(index + offset, obj); 341 } 342 343 @Override 344 public int size() { 345 checkModCount(); 346 return size; 347 } 348 349 @Override 350 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) { 351 return new LinkedSubList<>(parent, fromIndexInclusive + offset, toIndexExclusive + offset); 352 } 353 } 354 355 /** 356 * A list iterator over the linked sub list. 357 * 358 * @param <E> the type of elements in this iterator. 359 */ 360 protected static class LinkedSubListIterator<E> extends LinkedListIterator<E> { 361 362 /** The sub list */ 363 protected final LinkedSubList<E> sub; 364 365 protected LinkedSubListIterator(final LinkedSubList<E> sub, final int startIndex) { 366 super(sub.parent, startIndex + sub.offset); 367 this.sub = sub; 368 } 369 370 @Override 371 public void add(final E obj) { 372 super.add(obj); 373 sub.expectedModCount = parent.modCount; 374 sub.size++; 375 } 376 377 @Override 378 public boolean hasNext() { 379 return nextIndex() < sub.size; 380 } 381 382 @Override 383 public boolean hasPrevious() { 384 return previousIndex() >= 0; 385 } 386 387 @Override 388 public int nextIndex() { 389 return super.nextIndex() - sub.offset; 390 } 391 392 @Override 393 public void remove() { 394 super.remove(); 395 sub.expectedModCount = parent.modCount; 396 sub.size--; 397 } 398 } 399 400 /** 401 * A node within the linked list. 402 * <p> 403 * From Commons Collections 3.1, all access to the {@code value} property 404 * is via the methods on this class. 405 */ 406 protected static class Node<E> { 407 408 /** A pointer to the node before this node */ 409 protected Node<E> previous; 410 /** A pointer to the node after this node */ 411 protected Node<E> next; 412 /** The object contained within this node */ 413 protected E value; 414 415 /** 416 * Constructs a new header node. 417 */ 418 protected Node() { 419 previous = this; 420 next = this; 421 } 422 423 /** 424 * Constructs a new node. 425 * 426 * @param value the value to store 427 */ 428 protected Node(final E value) { 429 this.value = value; 430 } 431 432 /** 433 * Constructs a new node. 434 * 435 * @param previous the previous node in the list 436 * @param next the next node in the list 437 * @param value the value to store 438 */ 439 protected Node(final Node<E> previous, final Node<E> next, final E value) { 440 this.previous = previous; 441 this.next = next; 442 this.value = value; 443 } 444 445 /** 446 * Gets the next node. 447 * 448 * @return the next node 449 * @since 3.1 450 */ 451 protected Node<E> getNextNode() { 452 return next; 453 } 454 455 /** 456 * Gets the previous node. 457 * 458 * @return the previous node 459 * @since 3.1 460 */ 461 protected Node<E> getPreviousNode() { 462 return previous; 463 } 464 465 /** 466 * Gets the value of the node. 467 * 468 * @return the value 469 * @since 3.1 470 */ 471 protected E getValue() { 472 return value; 473 } 474 475 /** 476 * Sets the next node. 477 * 478 * @param next the next node 479 * @since 3.1 480 */ 481 protected void setNextNode(final Node<E> next) { 482 this.next = next; 483 } 484 485 /** 486 * Sets the previous node. 487 * 488 * @param previous the previous node 489 * @since 3.1 490 */ 491 protected void setPreviousNode(final Node<E> previous) { 492 this.previous = previous; 493 } 494 495 /** 496 * Sets the value of the node. 497 * 498 * @param value the value 499 * @since 3.1 500 */ 501 protected void setValue(final E value) { 502 this.value = value; 503 } 504 } 505 506 /** 507 * A {@link Node} which indicates the start and end of the list and does not 508 * hold a value. The value of {@code next} is the first item in the 509 * list. The value of {@code previous} is the last item in the list. 510 */ 511 transient Node<E> header; 512 513 /** The size of the list */ 514 transient int size; 515 516 /** Modification count for iterators */ 517 transient int modCount; 518 519 /** 520 * Constructor that does nothing (intended for deserialization). 521 * <p> 522 * If this constructor is used by a serializable subclass then the init() 523 * method must be called. 524 */ 525 protected AbstractLinkedList() { 526 } 527 528 /** 529 * Constructs a list copying data from the specified collection. 530 * 531 * @param coll the collection to copy 532 */ 533 protected AbstractLinkedList(final Collection<? extends E> coll) { 534 init(); 535 addAll(coll); 536 } 537 538 @Override 539 public boolean add(final E value) { 540 addLast(value); 541 return true; 542 } 543 544 @Override 545 public void add(final int index, final E value) { 546 final Node<E> node = getNode(index, true); 547 addNodeBefore(node, value); 548 } 549 550 @Override 551 public boolean addAll(final Collection<? extends E> coll) { 552 return addAll(size, coll); 553 } 554 555 @Override 556 public boolean addAll(final int index, final Collection<? extends E> coll) { 557 final Node<E> node = getNode(index, true); 558 for (final E e : coll) { 559 addNodeBefore(node, e); 560 } 561 return true; 562 } 563 564 public boolean addFirst(final E o) { 565 addNodeAfter(header, o); 566 return true; 567 } 568 569 public boolean addLast(final E o) { 570 addNodeBefore(header, o); 571 return true; 572 } 573 574 /** 575 * Inserts a new node into the list. 576 * 577 * @param nodeToInsert new node to insert 578 * @param insertBeforeNode node to insert before 579 * @throws NullPointerException if either node is null 580 */ 581 protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) { 582 Objects.requireNonNull(nodeToInsert, "nodeToInsert"); 583 Objects.requireNonNull(insertBeforeNode, "insertBeforeNode"); 584 nodeToInsert.next = insertBeforeNode; 585 nodeToInsert.previous = insertBeforeNode.previous; 586 insertBeforeNode.previous.next = nodeToInsert; 587 insertBeforeNode.previous = nodeToInsert; 588 size++; 589 modCount++; 590 } 591 592 /** 593 * Creates a new node with the specified object as its 594 * {@code value} and inserts it after {@code node}. 595 * <p> 596 * This implementation uses {@link #createNode(Object)} and 597 * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}. 598 * 599 * @param node node to insert after 600 * @param value value of the newly added node 601 * @throws NullPointerException if {@code node} is null 602 */ 603 protected void addNodeAfter(final Node<E> node, final E value) { 604 final Node<E> newNode = createNode(value); 605 addNode(newNode, node.next); 606 } 607 608 /** 609 * Creates a new node with the specified object as its 610 * {@code value} and inserts it before {@code node}. 611 * <p> 612 * This implementation uses {@link #createNode(Object)} and 613 * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}. 614 * 615 * @param node node to insert before 616 * @param value value of the newly added node 617 * @throws NullPointerException if {@code node} is null 618 */ 619 protected void addNodeBefore(final Node<E> node, final E value) { 620 final Node<E> newNode = createNode(value); 621 addNode(newNode, node); 622 } 623 624 @Override 625 public void clear() { 626 removeAllNodes(); 627 } 628 629 @Override 630 public boolean contains(final Object value) { 631 return indexOf(value) != -1; 632 } 633 634 @Override 635 public boolean containsAll(final Collection<?> coll) { 636 for (final Object o : coll) { 637 if (!contains(o)) { 638 return false; 639 } 640 } 641 return true; 642 } 643 644 /** 645 * Creates a new node with previous, next and element all set to null. 646 * This implementation creates a new empty Node. 647 * Subclasses can override this to create a different class. 648 * 649 * @return newly created node 650 */ 651 protected Node<E> createHeaderNode() { 652 return new Node<>(); 653 } 654 655 /** 656 * Creates a new node with the specified properties. 657 * This implementation creates a new Node with data. 658 * Subclasses can override this to create a different class. 659 * 660 * @param value value of the new node 661 * @return a new node containing the value 662 */ 663 protected Node<E> createNode(final E value) { 664 return new Node<>(value); 665 } 666 667 /** 668 * Creates an iterator for the sublist. 669 * 670 * @param subList the sublist to get an iterator for 671 * @return a new iterator on the given sublist 672 */ 673 protected Iterator<E> createSubListIterator(final LinkedSubList<E> subList) { 674 return createSubListListIterator(subList, 0); 675 } 676 677 /** 678 * Creates a list iterator for the sublist. 679 * 680 * @param subList the sublist to get an iterator for 681 * @param fromIndex the index to start from, relative to the sublist 682 * @return a new list iterator on the given sublist 683 */ 684 protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) { 685 return new LinkedSubListIterator<>(subList, fromIndex); 686 } 687 688 /** 689 * Deserializes the data held in this object to the stream specified. 690 * <p> 691 * The first serializable subclass must call this method from 692 * {@code readObject}. 693 * 694 * @param inputStream the stream to read the object from 695 * @throws IOException if any error occurs while reading from the stream 696 * @throws ClassNotFoundException if a class read from the stream can not be loaded 697 */ 698 @SuppressWarnings("unchecked") 699 protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException { 700 init(); 701 final int size = inputStream.readInt(); 702 for (int i = 0; i < size; i++) { 703 add((E) inputStream.readObject()); 704 } 705 } 706 707 /** 708 * Serializes the data held in this object to the stream specified. 709 * <p> 710 * The first serializable subclass must call this method from 711 * {@code writeObject}. 712 * 713 * @param outputStream the stream to write the object to 714 * @throws IOException if anything goes wrong 715 */ 716 protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException { 717 // Write the size so we know how many nodes to read back 718 outputStream.writeInt(size()); 719 for (final E e : this) { 720 outputStream.writeObject(e); 721 } 722 } 723 724 @Override 725 public boolean equals(final Object obj) { 726 if (obj == this) { 727 return true; 728 } 729 if (!(obj instanceof List)) { 730 return false; 731 } 732 final List<?> other = (List<?>) obj; 733 if (other.size() != size()) { 734 return false; 735 } 736 final ListIterator<?> it1 = listIterator(); 737 final ListIterator<?> it2 = other.listIterator(); 738 while (it1.hasNext() && it2.hasNext()) { 739 if (!Objects.equals(it1.next(), it2.next())) { 740 return false; 741 } 742 } 743 return !(it1.hasNext() || it2.hasNext()); 744 } 745 746 @Override 747 public E get(final int index) { 748 final Node<E> node = getNode(index, false); 749 return node.getValue(); 750 } 751 752 public E getFirst() { 753 final Node<E> node = header.next; 754 if (node == header) { 755 throw new NoSuchElementException(); 756 } 757 return node.getValue(); 758 } 759 760 public E getLast() { 761 final Node<E> node = header.previous; 762 if (node == header) { 763 throw new NoSuchElementException(); 764 } 765 return node.getValue(); 766 } 767 768 /** 769 * Gets the node at a particular index. 770 * 771 * @param index the index, starting from 0 772 * @param endMarkerAllowed whether or not the end marker can be returned if 773 * startIndex is set to the list's size 774 * @return the node at the given index 775 * @throws IndexOutOfBoundsException if the index is less than 0; equal to 776 * the size of the list and endMakerAllowed is false; or greater than the 777 * size of the list 778 */ 779 protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException { 780 // Check the index is within the bounds 781 if (index < 0) { 782 throw new IndexOutOfBoundsException("Couldn't get the node: " + 783 "index (" + index + ") less than zero."); 784 } 785 if (!endMarkerAllowed && index == size) { 786 throw new IndexOutOfBoundsException("Couldn't get the node: " + 787 "index (" + index + ") is the size of the list."); 788 } 789 if (index > size) { 790 throw new IndexOutOfBoundsException("Couldn't get the node: " + 791 "index (" + index + ") greater than the size of the " + 792 "list (" + size + ")."); 793 } 794 // Search the list and get the node 795 Node<E> node; 796 if (index < size / 2) { 797 // Search forwards 798 node = header.next; 799 for (int currentIndex = 0; currentIndex < index; currentIndex++) { 800 node = node.next; 801 } 802 } else { 803 // Search backwards 804 node = header; 805 for (int currentIndex = size; currentIndex > index; currentIndex--) { 806 node = node.previous; 807 } 808 } 809 return node; 810 } 811 812 @Override 813 public int hashCode() { 814 int hashCode = 1; 815 for (final E e : this) { 816 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 817 } 818 return hashCode; 819 } 820 821 @Override 822 public int indexOf(final Object value) { 823 int i = 0; 824 for (Node<E> node = header.next; node != header; node = node.next) { 825 if (isEqualValue(node.getValue(), value)) { 826 return i; 827 } 828 i++; 829 } 830 return CollectionUtils.INDEX_NOT_FOUND; 831 } 832 833 /** 834 * The equivalent of a default constructor, broken out so it can be called 835 * by any constructor and by {@code readObject}. 836 * Subclasses which override this method should make sure they call super, 837 * so the list is initialized properly. 838 */ 839 protected void init() { 840 header = createHeaderNode(); 841 } 842 843 @Override 844 public boolean isEmpty() { 845 return size() == 0; 846 } 847 848 /** 849 * Compares two values for equals. 850 * This implementation uses the equals method. 851 * Subclasses can override this to match differently. 852 * 853 * @param value1 the first value to compare, may be null 854 * @param value2 the second value to compare, may be null 855 * @return true if equal 856 */ 857 protected boolean isEqualValue(final Object value1, final Object value2) { 858 return Objects.equals(value1, value2); 859 } 860 861 @Override 862 public Iterator<E> iterator() { 863 return listIterator(); 864 } 865 866 @Override 867 public int lastIndexOf(final Object value) { 868 int i = size - 1; 869 for (Node<E> node = header.previous; node != header; node = node.previous) { 870 if (isEqualValue(node.getValue(), value)) { 871 return i; 872 } 873 i--; 874 } 875 return CollectionUtils.INDEX_NOT_FOUND; 876 } 877 878 @Override 879 public ListIterator<E> listIterator() { 880 return new LinkedListIterator<>(this, 0); 881 } 882 883 @Override 884 public ListIterator<E> listIterator(final int fromIndex) { 885 return new LinkedListIterator<>(this, fromIndex); 886 } 887 888 @Override 889 public E remove(final int index) { 890 final Node<E> node = getNode(index, false); 891 final E oldValue = node.getValue(); 892 removeNode(node); 893 return oldValue; 894 } 895 896 @Override 897 public boolean remove(final Object value) { 898 for (Node<E> node = header.next; node != header; node = node.next) { 899 if (isEqualValue(node.getValue(), value)) { 900 removeNode(node); 901 return true; 902 } 903 } 904 return false; 905 } 906 907 /** 908 * {@inheritDoc} 909 * <p> 910 * This implementation iterates over the elements of this list, checking each element in 911 * turn to see if it's contained in {@code coll}. If it's contained, it's removed 912 * from this list. As a consequence, it is advised to use a collection type for 913 * {@code coll} that provides a fast (e.g. O(1)) implementation of 914 * {@link Collection#contains(Object)}. 915 */ 916 @Override 917 public boolean removeAll(final Collection<?> coll) { 918 boolean modified = false; 919 final Iterator<E> it = iterator(); 920 while (it.hasNext()) { 921 if (coll.contains(it.next())) { 922 it.remove(); 923 modified = true; 924 } 925 } 926 return modified; 927 } 928 929 /** 930 * Removes all nodes by resetting the circular list marker. 931 */ 932 protected void removeAllNodes() { 933 header.next = header; 934 header.previous = header; 935 size = 0; 936 modCount++; 937 } 938 939 public E removeFirst() { 940 final Node<E> node = header.next; 941 if (node == header) { 942 throw new NoSuchElementException(); 943 } 944 final E oldValue = node.getValue(); 945 removeNode(node); 946 return oldValue; 947 } 948 949 public E removeLast() { 950 final Node<E> node = header.previous; 951 if (node == header) { 952 throw new NoSuchElementException(); 953 } 954 final E oldValue = node.getValue(); 955 removeNode(node); 956 return oldValue; 957 } 958 959 /** 960 * Removes the specified node from the list. 961 * 962 * @param node the node to remove 963 * @throws NullPointerException if {@code node} is null 964 */ 965 protected void removeNode(final Node<E> node) { 966 Objects.requireNonNull(node, "node"); 967 node.previous.next = node.next; 968 node.next.previous = node.previous; 969 size--; 970 modCount++; 971 } 972 973 /** 974 * {@inheritDoc} 975 * <p> 976 * This implementation iterates over the elements of this list, checking each element in 977 * turn to see if it's contained in {@code coll}. If it's not contained, it's removed 978 * from this list. As a consequence, it is advised to use a collection type for 979 * {@code coll} that provides a fast (e.g. O(1)) implementation of 980 * {@link Collection#contains(Object)}. 981 */ 982 @Override 983 public boolean retainAll(final Collection<?> coll) { 984 boolean modified = false; 985 final Iterator<E> it = iterator(); 986 while (it.hasNext()) { 987 if (!coll.contains(it.next())) { 988 it.remove(); 989 modified = true; 990 } 991 } 992 return modified; 993 } 994 995 @Override 996 public E set(final int index, final E value) { 997 final Node<E> node = getNode(index, false); 998 final E oldValue = node.getValue(); 999 updateNode(node, value); 1000 return oldValue; 1001 } 1002 1003 @Override 1004 public int size() { 1005 return size; 1006 } 1007 1008 /** 1009 * Gets a sublist of the main list. 1010 * 1011 * @param fromIndexInclusive the index to start from 1012 * @param toIndexExclusive the index to end at 1013 * @return the new sublist 1014 */ 1015 @Override 1016 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) { 1017 return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive); 1018 } 1019 1020 @Override 1021 public Object[] toArray() { 1022 return toArray(new Object[size]); 1023 } 1024 1025 @Override 1026 @SuppressWarnings("unchecked") 1027 public <T> T[] toArray(T[] array) { 1028 // Extend the array if needed 1029 if (array.length < size) { 1030 final Class<?> componentType = array.getClass().getComponentType(); 1031 array = (T[]) Array.newInstance(componentType, size); 1032 } 1033 // Copy the values into the array 1034 int i = 0; 1035 for (Node<E> node = header.next; node != header; node = node.next, i++) { 1036 array[i] = (T) node.getValue(); 1037 } 1038 // Set the value after the last value to null 1039 if (array.length > size) { 1040 array[size] = null; 1041 } 1042 return array; 1043 } 1044 1045 @Override 1046 public String toString() { 1047 if (isEmpty()) { 1048 return "[]"; 1049 } 1050 final StringBuilder buf = new StringBuilder(16 * size()); 1051 buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX); 1052 1053 final Iterator<E> it = iterator(); 1054 boolean hasNext = it.hasNext(); 1055 while (hasNext) { 1056 final Object value = it.next(); 1057 buf.append(value == this ? "(this Collection)" : value); 1058 hasNext = it.hasNext(); 1059 if (hasNext) { 1060 buf.append(", "); 1061 } 1062 } 1063 buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX); 1064 return buf.toString(); 1065 } 1066 1067 /** 1068 * Updates the node with a new value. 1069 * This implementation sets the value on the node. 1070 * Subclasses can override this to record the change. 1071 * 1072 * @param node node to update 1073 * @param value new value of the node 1074 */ 1075 protected void updateNode(final Node<E> node, final E value) { 1076 node.setValue(value); 1077 } 1078 1079}