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