    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     * </p>
    555     */
    556    protected AbstractLinkedListJava21() {
    557    }
    558
    559    /**
    560     * Constructs a list copying data from the specified collection.
    561     *
    562     * @param coll  the collection to copy
    563     */
    564    protected AbstractLinkedListJava21(final Collection<? extends E> coll) {
    565        init();
    566        addAll(coll);
    567    }
    568
    569    @Override
    570    public boolean add(final E value) {
    571        addLast(value);
    572        return true;
    573    }
    574
    575    @Override
    576    public void add(final int index, final E value) {
    577        final Node<E> node = getNode(index, true);
    578        addNodeBefore(node, value);
    579    }
    580
    581    @Override
    582    public boolean addAll(final Collection<? extends E> coll) {
    583        return addAll(size, coll);
    584    }
    585
    586    @Override
    587    public boolean addAll(final int index, final Collection<? extends E> coll) {
    588        final Node<E> node = getNode(index, true);
    589        for (final E e : coll) {
    590            addNodeBefore(node, e);
    591        }
    592        return true;
    593    }
    594
    595    /**
    596     * {@inheritDoc}
    597     */
    598    public void addFirst(final E o) {
    599        addNodeAfter(header, o);
    600    }
    601
    602    /**
    603     * {@inheritDoc}
    604     */
    605    public void addLast(final E o) {
    606        addNodeBefore(header, o);
    607    }
    608
    609    /**
    610     * Inserts a new node into the list.
    611     *
    612     * @param nodeToInsert  new node to insert
    613     * @param insertBeforeNode  node to insert before
    614     * @throws NullPointerException if either node is null
    615     */
    616    protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
    617        Objects.requireNonNull(nodeToInsert, "nodeToInsert");
    618        Objects.requireNonNull(insertBeforeNode, "insertBeforeNode");
    619        nodeToInsert.next = insertBeforeNode;
    620        nodeToInsert.previous = insertBeforeNode.previous;
    621        insertBeforeNode.previous.next = nodeToInsert;
    622        insertBeforeNode.previous = nodeToInsert;
    623        size++;
    624        modCount++;
    625    }
    626
    627    /**
    628     * Creates a new node with the specified object as its
    629     * {@code value} and inserts it after {@code node}.
    630     * <p>
    631     * This implementation uses {@link #createNode(Object)} and
    632     * {@link #addNode(AbstractLinkedListJava21.Node,AbstractLinkedListJava21.Node)}.
    633     * </p>
    634     *
    635     * @param node  node to insert after
    636     * @param value  value of the newly added node
    637     * @throws NullPointerException if {@code node} is null
    638     */
    639    protected void addNodeAfter(final Node<E> node, final E value) {
    640        final Node<E> newNode = createNode(value);
    641        addNode(newNode, node.next);
    642    }
    643
    644    /**
    645     * Creates a new node with the specified object as its
    646     * {@code value} and inserts it before {@code node}.
    647     * <p>
    648     * This implementation uses {@link #createNode(Object)} and
    649     * {@link #addNode(AbstractLinkedListJava21.Node,AbstractLinkedListJava21.Node)}.
    650     * </p>
    651     *
    652     * @param node  node to insert before
    653     * @param value  value of the newly added node
    654     * @throws NullPointerException if {@code node} is null
    655     */
    656    protected void addNodeBefore(final Node<E> node, final E value) {
    657        final Node<E> newNode = createNode(value);
    658        addNode(newNode, node);
    659    }
    660
    661    @Override
    662    public void clear() {
    663        removeAllNodes();
    664    }
    665
    666    @Override
    667    public boolean contains(final Object value) {
    668        return indexOf(value) != -1;
    669    }
    670
    671    @Override
    672    public boolean containsAll(final Collection<?> coll) {
    673        for (final Object o : coll) {
    674            if (!contains(o)) {
    675                return false;
    676            }
    677        }
    678        return true;
    679    }
    680
    681    /**
    682     * Creates a new node with previous, next and element all set to null.
    683     * This implementation creates a new empty Node.
    684     * Subclasses can override this to create a different class.
    685     *
    686     * @return  newly created node
    687     */
    688    protected Node<E> createHeaderNode() {
    689        return new Node<>();
    690    }
    691
    692    /**
    693     * Creates a new node with the specified properties.
    694     * This implementation creates a new Node with data.
    695     * Subclasses can override this to create a different class.
    696     *
    697     * @param value  value of the new node
    698     * @return a new node containing the value
    699     */
    700    protected Node<E> createNode(final E value) {
    701        return new Node<>(value);
    702    }
    703
    704    /**
    705     * Creates an iterator for the sublist.
    706     *
    707     * @param subList  the sublist to get an iterator for
    708     * @return a new iterator on the given sublist
    709     */
    710    protected Iterator<E> createSubListIterator(final LinkedSubList<E> subList) {
    711        return createSubListListIterator(subList, 0);
    712    }
    713
    714    /**
    715     * Creates a list iterator for the sublist.
    716     *
    717     * @param subList  the sublist to get an iterator for
    718     * @param fromIndex  the index to start from, relative to the sublist
    719     * @return a new list iterator on the given sublist
    720     */
    721    protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) {
    722        return new LinkedSubListIterator<>(subList, fromIndex);
    723    }
    724
    725    /**
    726     * Deserializes the data held in this object to the stream specified.
    727     * <p>
    728     * The first serializable subclass must call this method from
    729     * {@code readObject}.
    730     * </p>
    731     *
    732     * @param inputStream  the stream to read the object from
    733     * @throws IOException  if any error occurs while reading from the stream
    734     * @throws ClassNotFoundException  if a class read from the stream cannot be loaded
    735     */
    736    @SuppressWarnings("unchecked")
    737    protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
    738        init();
    739        final int size = inputStream.readInt();
    740        for (int i = 0; i < size; i++) {
    741            add((E) inputStream.readObject());
    742        }
    743    }
    744
    745    /**
    746     * Serializes the data held in this object to the stream specified.
    747     * <p>
    748     * The first serializable subclass must call this method from
    749     * {@code writeObject}.
    750     * </p>
    751     *
    752     * @param outputStream  the stream to write the object to
    753     * @throws IOException  if anything goes wrong
    754     */
    755    protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException {
    756        // Write the size so we know how many nodes to read back
    757        outputStream.writeInt(size());
    758        for (final E e : this) {
    759            outputStream.writeObject(e);
    760        }
    761    }
    762
    763    @Override
    764    public boolean equals(final Object obj) {
    765        if (obj == this) {
    766            return true;
    767        }
    768        if (!(obj instanceof List)) {
    769            return false;
    770        }
    771        final List<?> other = (List<?>) obj;
    772        if (other.size() != size()) {
    773            return false;
    774        }
    775        final ListIterator<?> it1 = listIterator();
    776        final ListIterator<?> it2 = other.listIterator();
    777        while (it1.hasNext() && it2.hasNext()) {
    778            if (!Objects.equals(it1.next(), it2.next())) {
    779                return false;
    780            }
    781        }
    782        return !(it1.hasNext() || it2.hasNext());
    783    }
    784
    785    @Override
    786    public E get(final int index) {
    787        final Node<E> node = getNode(index, false);
    788        return node.getValue();
    789    }
    790
    791    /**
    792     * {@inheritDoc}
    793     */
    794    public E getFirst() {
    795        final Node<E> node = header.next;
    796        if (node == header) {
    797            throw new NoSuchElementException();
    798        }
    799        return node.getValue();
    800    }
    801
    802    /**
    803     * {@inheritDoc}
    804     */
    805    public E getLast() {
    806        final Node<E> node = header.previous;
    807        if (node == header) {
    808            throw new NoSuchElementException();
    809        }
    810        return node.getValue();
    811    }
    812
    813    /**
    814     * Gets the node at a particular index.
    815     *
    816     * @param index  the index, starting from 0
    817     * @param endMarkerAllowed  whether or not the end marker can be returned if
    818     * startIndex is set to the list's size
    819     * @return the node at the given index
    820     * @throws IndexOutOfBoundsException if the index is less than 0; equal to
    821     * the size of the list and endMakerAllowed is false; or greater than the
    822     * size of the list
    823     */
    824    protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException {
    825        // Check the index is within the bounds
    826        if (index < 0) {
    827            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    828                    "index (" + index + ") less than zero.");
    829        }
    830        if (!endMarkerAllowed && index == size) {
    831            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    832                    "index (" + index + ") is the size of the list.");
    833        }
    834        if (index > size) {
    835            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    836                    "index (" + index + ") greater than the size of the " +
    837                    "list (" + size + ").");
    838        }
    839        // Search the list and get the node
    840        Node<E> node;
    841        if (index < size / 2) {
    842            // Search forwards
    843            node = header.next;
    844            for (int currentIndex = 0; currentIndex < index; currentIndex++) {
    845                node = node.next;
    846            }
    847        } else {
    848            // Search backwards
    849            node = header;
    850            for (int currentIndex = size; currentIndex > index; currentIndex--) {
    851                node = node.previous;
    852            }
    853        }
    854        return node;
    855    }
    856
    857    @Override
    858    public int hashCode() {
    859        int hashCode = 1;
    860        for (final E e : this) {
    861            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
    862        }
    863        return hashCode;
    864    }
    865
    866    @Override
    867    public int indexOf(final Object value) {
    868        int i = 0;
    869        for (Node<E> node = header.next; node != header; node = node.next) {
    870            if (isEqualValue(node.getValue(), value)) {
    871                return i;
    872            }
    873            i++;
    874        }
    875        return CollectionUtils.INDEX_NOT_FOUND;
    876    }
    877
    878    /**
    879     * The equivalent of a default constructor, broken out so it can be called
    880     * by any constructor and by {@code readObject}.
    881     * Subclasses which override this method should make sure they call super,
    882     * so the list is initialized properly.
    883     */
    884    protected void init() {
    885        header = createHeaderNode();
    886    }
    887
    888    @Override
    889    public boolean isEmpty() {
    890        return size() == 0;
    891    }
    892
    893    /**
    894     * Compares two values for equals.
    895     * This implementation uses the equals method.
    896     * Subclasses can override this to match differently.
    897     *
    898     * @param value1  the first value to compare, may be null
    899     * @param value2  the second value to compare, may be null
    900     * @return true if equal
    901     */
    902    protected boolean isEqualValue(final Object value1, final Object value2) {
    903        return Objects.equals(value1, value2);
    904    }
    905
    906    @Override
    907    public Iterator<E> iterator() {
    908        return listIterator();
    909    }
    910
    911    @Override
    912    public int lastIndexOf(final Object value) {
    913        int i = size - 1;
    914        for (Node<E> node = header.previous; node != header; node = node.previous) {
    915            if (isEqualValue(node.getValue(), value)) {
    916                return i;
    917            }
    918            i--;
    919        }
    920        return CollectionUtils.INDEX_NOT_FOUND;
    921    }
    922
    923    @Override
    924    public ListIterator<E> listIterator() {
    925        return new LinkedListIterator<>(this, 0);
    926    }
    927
    928    @Override
    929    public ListIterator<E> listIterator(final int fromIndex) {
    930        return new LinkedListIterator<>(this, fromIndex);
    931    }
    932
    933    @Override
    934    public E remove(final int index) {
    935        final Node<E> node = getNode(index, false);
    936        final E oldValue = node.getValue();
    937        removeNode(node);
    938        return oldValue;
    939    }
    940
    941    @Override
    942    public boolean remove(final Object value) {
    943        for (Node<E> node = header.next; node != header; node = node.next) {
    944            if (isEqualValue(node.getValue(), value)) {
    945                removeNode(node);
    946                return true;
    947            }
    948        }
    949        return false;
    950    }
    951
    952    /**
    953     * {@inheritDoc}
    954     * <p>
    955     * This implementation iterates over the elements of this list, checking each element in
    956     * turn to see if it's contained in {@code coll}. If it's contained, it's removed
    957     * from this list. As a consequence, it is advised to use a collection type for
    958     * {@code coll} that provides a fast (for example O(1)) implementation of
    959     * {@link Collection#contains(Object)}.
    960     * </p>
    961     */
    962    @Override
    963    public boolean removeAll(final Collection<?> coll) {
    964        boolean modified = false;
    965        final Iterator<E> it = iterator();
    966        while (it.hasNext()) {
    967            if (coll.contains(it.next())) {
    968                it.remove();
    969                modified = true;
    970            }
    971        }
    972        return modified;
    973    }
    974
    975    /**
    976     * Removes all nodes by resetting the circular list marker.
    977     */
    978    protected void removeAllNodes() {
    979        header.next = header;
    980        header.previous = header;
    981        size = 0;
    982        modCount++;
    983    }
    984
    985    /**
    986     * {@inheritDoc}
    987     */
    988    public E removeFirst() {
    989        final Node<E> node = header.next;
    990        if (node == header) {
    991            throw new NoSuchElementException();
    992        }
    993        final E oldValue = node.getValue();
    994        removeNode(node);
    995        return oldValue;
    996    }
    997
    998    /**
    999     * {@inheritDoc}
    1000     */
    1001    public E removeLast() {
    1002        final Node<E> node = header.previous;
    1003        if (node == header) {
    1004            throw new NoSuchElementException();
    1005        }
    1006        final E oldValue = node.getValue();
    1007        removeNode(node);
    1008        return oldValue;
    1009    }
    1010
    1011    /**
    1012     * Removes the specified node from the list.
    1013     *
    1014     * @param node  the node to remove
    1015     * @throws NullPointerException if {@code node} is null
    1016     */
    1017    protected void removeNode(final Node<E> node) {
    1018        Objects.requireNonNull(node, "node");
    1019        node.previous.next = node.next;
    1020        node.next.previous = node.previous;
    1021        size--;
    1022        modCount++;
    1023    }
    1024
    1025    /**
    1026     * {@inheritDoc}
    1027     * <p>
    1028     * This implementation iterates over the elements of this list, checking each element in
    1029     * turn to see if it's contained in {@code coll}. If it's not contained, it's removed
    1030     * from this list. As a consequence, it is advised to use a collection type for
    1031     * {@code coll} that provides a fast (for example O(1)) implementation of
    1032     * {@link Collection#contains(Object)}.
    1033     * </p>
    1034     */
    1035    @Override
    1036    public boolean retainAll(final Collection<?> coll) {
    1037        boolean modified = false;
    1038        final Iterator<E> it = iterator();
    1039        while (it.hasNext()) {
    1040            if (!coll.contains(it.next())) {
    1041                it.remove();
    1042                modified = true;
    1043            }
    1044        }
    1045        return modified;
    1046    }
    1047
    1048    @Override
    1049    public E set(final int index, final E value) {
    1050        final Node<E> node = getNode(index, false);
    1051        final E oldValue = node.getValue();
    1052        updateNode(node, value);
    1053        return oldValue;
    1054    }
    1055
    1056    @Override
    1057    public int size() {
    1058        return size;
    1059    }
    1060
    1061    /**
    1062     * Gets a sublist of the main list.
    1063     *
    1064     * @param fromIndexInclusive  the index to start from
    1065     * @param toIndexExclusive  the index to end at
    1066     * @return the new sublist
    1067     */
    1068    @Override
    1069    public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
    1070        return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive);
    1071    }
    1072
    1073    @Override
    1074    public Object[] toArray() {
    1075        return toArray(new Object[size]);
    1076    }
    1077
    1078    @Override
    1079    @SuppressWarnings("unchecked")
    1080    public <T> T[] toArray(T[] array) {
    1081        // Extend the array if needed
    1082        if (array.length < size) {
    1083            final Class<?> componentType = array.getClass().getComponentType();
    1084            array = (T[]) Array.newInstance(componentType, size);
    1085        }
    1086        // Copy the values into the array
    1087        int i = 0;
    1088        for (Node<E> node = header.next; node != header; node = node.next, i++) {
    1089            array[i] = (T) node.getValue();
    1090        }
    1091        // Set the value after the last value to null
    1092        if (array.length > size) {
    1093            array[size] = null;
    1094        }
    1095        return array;
    1096    }
    1097
    1098    @Override
    1099    public String toString() {
    1100        if (isEmpty()) {
    1101            return "[]";
    1102        }
    1103        final StringBuilder buf = new StringBuilder(16 * size());
    1104        buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
    1105
    1106        final Iterator<E> it = iterator();
    1107        boolean hasNext = it.hasNext();
    1108        while (hasNext) {
    1109            final Object value = it.next();
    1110            buf.append(value == this ? "(this Collection)" : value);
    1111            hasNext = it.hasNext();
    1112            if (hasNext) {
    1113                buf.append(", ");
    1114            }
    1115        }
    1116        buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
    1117        return buf.toString();
    1118    }
    1119
    1120    /**
    1121     * Updates the node with a new value.
    1122     * This implementation sets the value on the node.
    1123     * Subclasses can override this to record the change.
    1124     *
    1125     * @param node  node to update
    1126     * @param value  new value of the node
    1127     */
    1128    protected void updateNode(final Node<E> node, final E value) {
    1129        node.setValue(value);
    1130    }
    1131
    1132}