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