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