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