    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 *
    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 java.util.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        /** A pointer to the node after this node */
    442        protected Node<E> next;
    443        /** The object contained within this node */
    444        protected E value;
    445
    446        /**
    447         * Constructs a new header node.
    448         */
    449        protected Node() {
    450            previous = this;
    451            next = this;
    452        }
    453
    454        /**
    455         * Constructs a new node.
    456         *
    457         * @param value  the value to store
    458         */
    459        protected Node(final E value) {
    460            this.value = value;
    461        }
    462
    463        /**
    464         * Constructs a new node.
    465         *
    466         * @param previous  the previous node in the list
    467         * @param next  the next node in the list
    468         * @param value  the value to store
    469         */
    470        protected Node(final Node<E> previous, final Node<E> next, final E value) {
    471            this.previous = previous;
    472            this.next = next;
    473            this.value = value;
    474        }
    475
    476        /**
    477         * Gets the next node.
    478         *
    479         * @return the next node
    480         * @since 3.1
    481         */
    482        protected Node<E> getNextNode() {
    483            return next;
    484        }
    485
    486        /**
    487         * Gets the previous node.
    488         *
    489         * @return the previous node
    490         * @since 3.1
    491         */
    492        protected Node<E> getPreviousNode() {
    493            return previous;
    494        }
    495
    496        /**
    497         * Gets the value of the node.
    498         *
    499         * @return the value
    500         * @since 3.1
    501         */
    502        protected E getValue() {
    503            return value;
    504        }
    505
    506        /**
    507         * Sets the next node.
    508         *
    509         * @param next  the next node
    510         * @since 3.1
    511         */
    512        protected void setNextNode(final Node<E> next) {
    513            this.next = next;
    514        }
    515
    516        /**
    517         * Sets the previous node.
    518         *
    519         * @param previous  the previous node
    520         * @since 3.1
    521         */
    522        protected void setPreviousNode(final Node<E> previous) {
    523            this.previous = previous;
    524        }
    525
    526        /**
    527         * Sets the value of the node.
    528         *
    529         * @param value  the value
    530         * @since 3.1
    531         */
    532        protected void setValue(final E value) {
    533            this.value = value;
    534        }
    535    }
    536
    537    /**
    538     * A {@link Node} which indicates the start and end of the list and does not
    539     * hold a value. The value of {@code next} is the first item in the
    540     * list. The value of {@code previous} is the last item in the list.
    541     */
    542    transient Node<E> header;
    543
    544    /** The size of the list */
    545    transient int size;
    546
    547    /** Modification count for iterators */
    548    transient int modCount;
    549
    550    /**
    551     * Constructor that does nothing (intended for deserialization).
    552     * <p>
    553     * If this constructor is used by a serializable subclass then the init()
    554     * method must be called.
    555     */
    556    protected AbstractLinkedList() {
    557    }
    558
    559    /**
    560     * Constructs a list copying data from the specified collection.
    561     *
    562     * @param coll  the collection to copy
    563     */
    564    protected AbstractLinkedList(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     * Adds an element at the beginning.
    597     *
    598     * @param e the element to beginning.
    599     * @return true.
    600     */
    601    public boolean addFirst(final E e) {
    602        addNodeAfter(header, e);
    603        return true;
    604    }
    605
    606    /**
    607     * Adds an element at the end.
    608     *
    609     * @param e the element to add.
    610     * @return true.
    611     */
    612    public boolean addLast(final E e) {
    613        addNodeBefore(header, e);
    614        return true;
    615    }
    616
    617    /**
    618     * Inserts a new node into the list.
    619     *
    620     * @param nodeToInsert  new node to insert
    621     * @param insertBeforeNode  node to insert before
    622     * @throws NullPointerException if either node is null
    623     */
    624    protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
    625        Objects.requireNonNull(nodeToInsert, "nodeToInsert");
    626        Objects.requireNonNull(insertBeforeNode, "insertBeforeNode");
    627        nodeToInsert.next = insertBeforeNode;
    628        nodeToInsert.previous = insertBeforeNode.previous;
    629        insertBeforeNode.previous.next = nodeToInsert;
    630        insertBeforeNode.previous = nodeToInsert;
    631        size++;
    632        modCount++;
    633    }
    634
    635    /**
    636     * Creates a new node with the specified object as its
    637     * {@code value} and inserts it after {@code node}.
    638     * <p>
    639     * This implementation uses {@link #createNode(Object)} and
    640     * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
    641     *
    642     * @param node  node to insert after
    643     * @param value  value of the newly added node
    644     * @throws NullPointerException if {@code node} is null
    645     */
    646    protected void addNodeAfter(final Node<E> node, final E value) {
    647        final Node<E> newNode = createNode(value);
    648        addNode(newNode, node.next);
    649    }
    650
    651    /**
    652     * Creates a new node with the specified object as its
    653     * {@code value} and inserts it before {@code node}.
    654     * <p>
    655     * This implementation uses {@link #createNode(Object)} and
    656     * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
    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     *
    737     * @param inputStream  the stream to read the object from
    738     * @throws IOException  if any error occurs while reading from the stream
    739     * @throws ClassNotFoundException  if a class read from the stream cannot be loaded
    740     */
    741    @SuppressWarnings("unchecked")
    742    protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
    743        init();
    744        final int size = inputStream.readInt();
    745        for (int i = 0; i < size; i++) {
    746            add((E) inputStream.readObject());
    747        }
    748    }
    749
    750    /**
    751     * Serializes the data held in this object to the stream specified.
    752     * <p>
    753     * The first serializable subclass must call this method from
    754     * {@code writeObject}.
    755     *
    756     * @param outputStream  the stream to write the object to
    757     * @throws IOException  if anything goes wrong
    758     */
    759    protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException {
    760        // Write the size so we know how many nodes to read back
    761        outputStream.writeInt(size());
    762        for (final E e : this) {
    763            outputStream.writeObject(e);
    764        }
    765    }
    766
    767    @Override
    768    public boolean equals(final Object obj) {
    769        if (obj == this) {
    770            return true;
    771        }
    772        if (!(obj instanceof List)) {
    773            return false;
    774        }
    775        final List<?> other = (List<?>) obj;
    776        if (other.size() != size()) {
    777            return false;
    778        }
    779        final ListIterator<?> it1 = listIterator();
    780        final ListIterator<?> it2 = other.listIterator();
    781        while (it1.hasNext() && it2.hasNext()) {
    782            if (!Objects.equals(it1.next(), it2.next())) {
    783                return false;
    784            }
    785        }
    786        return !(it1.hasNext() || it2.hasNext());
    787    }
    788
    789    @Override
    790    public E get(final int index) {
    791        final Node<E> node = getNode(index, false);
    792        return node.getValue();
    793    }
    794
    795    /**
    796     * Gets the first element.
    797     *
    798     * @return the first element.
    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     * Gets the last element.
    810     *
    811     * @return the last element.
    812     */
    813    public E getLast() {
    814        final Node<E> node = header.previous;
    815        if (node == header) {
    816            throw new NoSuchElementException();
    817        }
    818        return node.getValue();
    819    }
    820
    821    /**
    822     * Gets the node at a particular index.
    823     *
    824     * @param index  the index, starting from 0
    825     * @param endMarkerAllowed  whether or not the end marker can be returned if
    826     * startIndex is set to the list's size
    827     * @return the node at the given index
    828     * @throws IndexOutOfBoundsException if the index is less than 0; equal to
    829     * the size of the list and endMakerAllowed is false; or greater than the
    830     * size of the list
    831     */
    832    protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException {
    833        // Check the index is within the bounds
    834        if (index < 0) {
    835            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    836                    "index (" + index + ") less than zero.");
    837        }
    838        if (!endMarkerAllowed && index == size) {
    839            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    840                    "index (" + index + ") is the size of the list.");
    841        }
    842        if (index > size) {
    843            throw new IndexOutOfBoundsException("Couldn't get the node: " +
    844                    "index (" + index + ") greater than the size of the " +
    845                    "list (" + size + ").");
    846        }
    847        // Search the list and get the node
    848        Node<E> node;
    849        if (index < size / 2) {
    850            // Search forwards
    851            node = header.next;
    852            for (int currentIndex = 0; currentIndex < index; currentIndex++) {
    853                node = node.next;
    854            }
    855        } else {
    856            // Search backwards
    857            node = header;
    858            for (int currentIndex = size; currentIndex > index; currentIndex--) {
    859                node = node.previous;
    860            }
    861        }
    862        return node;
    863    }
    864
    865    @Override
    866    public int hashCode() {
    867        int hashCode = 1;
    868        for (final E e : this) {
    869            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
    870        }
    871        return hashCode;
    872    }
    873
    874    @Override
    875    public int indexOf(final Object value) {
    876        int i = 0;
    877        for (Node<E> node = header.next; node != header; node = node.next) {
    878            if (isEqualValue(node.getValue(), value)) {
    879                return i;
    880            }
    881            i++;
    882        }
    883        return CollectionUtils.INDEX_NOT_FOUND;
    884    }
    885
    886    /**
    887     * The equivalent of a default constructor, broken out so it can be called
    888     * by any constructor and by {@code readObject}.
    889     * Subclasses which override this method should make sure they call super,
    890     * so the list is initialized properly.
    891     */
    892    protected void init() {
    893        header = createHeaderNode();
    894    }
    895
    896    @Override
    897    public boolean isEmpty() {
    898        return size() == 0;
    899    }
    900
    901    /**
    902     * Compares two values for equals.
    903     * This implementation uses the equals method.
    904     * Subclasses can override this to match differently.
    905     *
    906     * @param value1  the first value to compare, may be null
    907     * @param value2  the second value to compare, may be null
    908     * @return true if equal
    909     */
    910    protected boolean isEqualValue(final Object value1, final Object value2) {
    911        return Objects.equals(value1, value2);
    912    }
    913
    914    @Override
    915    public Iterator<E> iterator() {
    916        return listIterator();
    917    }
    918
    919    @Override
    920    public int lastIndexOf(final Object value) {
    921        int i = size - 1;
    922        for (Node<E> node = header.previous; node != header; node = node.previous) {
    923            if (isEqualValue(node.getValue(), value)) {
    924                return i;
    925            }
    926            i--;
    927        }
    928        return CollectionUtils.INDEX_NOT_FOUND;
    929    }
    930
    931    @Override
    932    public ListIterator<E> listIterator() {
    933        return new LinkedListIterator<>(this, 0);
    934    }
    935
    936    @Override
    937    public ListIterator<E> listIterator(final int fromIndex) {
    938        return new LinkedListIterator<>(this, fromIndex);
    939    }
    940
    941    @Override
    942    public E remove(final int index) {
    943        final Node<E> node = getNode(index, false);
    944        final E oldValue = node.getValue();
    945        removeNode(node);
    946        return oldValue;
    947    }
    948
    949    @Override
    950    public boolean remove(final Object value) {
    951        for (Node<E> node = header.next; node != header; node = node.next) {
    952            if (isEqualValue(node.getValue(), value)) {
    953                removeNode(node);
    954                return true;
    955            }
    956        }
    957        return false;
    958    }
    959
    960    /**
    961     * {@inheritDoc}
    962     * <p>
    963     * This implementation iterates over the elements of this list, checking each element in
    964     * turn to see if it's contained in {@code coll}. If it's contained, it's removed
    965     * from this list. As a consequence, it is advised to use a collection type for
    966     * {@code coll} that provides a fast (e.g. O(1)) implementation of
    967     * {@link Collection#contains(Object)}.
    968     */
    969    @Override
    970    public boolean removeAll(final Collection<?> coll) {
    971        boolean modified = false;
    972        final Iterator<E> it = iterator();
    973        while (it.hasNext()) {
    974            if (coll.contains(it.next())) {
    975                it.remove();
    976                modified = true;
    977            }
    978        }
    979        return modified;
    980    }
    981
    982    /**
    983     * Removes all nodes by resetting the circular list marker.
    984     */
    985    protected void removeAllNodes() {
    986        header.next = header;
    987        header.previous = header;
    988        size = 0;
    989        modCount++;
    990    }
    991
    992    /**
    993     * Removes the first element.
    994     *
    995     * @return The value removed.
    996     */
    997    public E removeFirst() {
    998        final Node<E> node = header.next;
    999        if (node == header) {
    1000            throw new NoSuchElementException();
    1001        }
    1002        final E oldValue = node.getValue();
    1003        removeNode(node);
    1004        return oldValue;
    1005    }
    1006
    1007    /**
    1008     * Removes the last element.
    1009     *
    1010     * @return The value removed.
    1011     */
    1012    public E removeLast() {
    1013        final Node<E> node = header.previous;
    1014        if (node == header) {
    1015            throw new NoSuchElementException();
    1016        }
    1017        final E oldValue = node.getValue();
    1018        removeNode(node);
    1019        return oldValue;
    1020    }
    1021
    1022    /**
    1023     * Removes the specified node from the list.
    1024     *
    1025     * @param node  the node to remove
    1026     * @throws NullPointerException if {@code node} is null
    1027     */
    1028    protected void removeNode(final Node<E> node) {
    1029        Objects.requireNonNull(node, "node");
    1030        node.previous.next = node.next;
    1031        node.next.previous = node.previous;
    1032        size--;
    1033        modCount++;
    1034    }
    1035
    1036    /**
    1037     * {@inheritDoc}
    1038     * <p>
    1039     * This implementation iterates over the elements of this list, checking each element in
    1040     * turn to see if it's contained in {@code coll}. If it's not contained, it's removed
    1041     * from this list. As a consequence, it is advised to use a collection type for
    1042     * {@code coll} that provides a fast (e.g. O(1)) implementation of
    1043     * {@link Collection#contains(Object)}.
    1044     */
    1045    @Override
    1046    public boolean retainAll(final Collection<?> coll) {
    1047        boolean modified = false;
    1048        final Iterator<E> it = iterator();
    1049        while (it.hasNext()) {
    1050            if (!coll.contains(it.next())) {
    1051                it.remove();
    1052                modified = true;
    1053            }
    1054        }
    1055        return modified;
    1056    }
    1057
    1058    @Override
    1059    public E set(final int index, final E value) {
    1060        final Node<E> node = getNode(index, false);
    1061        final E oldValue = node.getValue();
    1062        updateNode(node, value);
    1063        return oldValue;
    1064    }
    1065
    1066    @Override
    1067    public int size() {
    1068        return size;
    1069    }
    1070
    1071    /**
    1072     * Gets a sublist of the main list.
    1073     *
    1074     * @param fromIndexInclusive  the index to start from
    1075     * @param toIndexExclusive  the index to end at
    1076     * @return the new sublist
    1077     */
    1078    @Override
    1079    public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
    1080        return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive);
    1081    }
    1082
    1083    @Override
    1084    public Object[] toArray() {
    1085        return toArray(new Object[size]);
    1086    }
    1087
    1088    @Override
    1089    @SuppressWarnings("unchecked")
    1090    public <T> T[] toArray(T[] array) {
    1091        // Extend the array if needed
    1092        if (array.length < size) {
    1093            final Class<?> componentType = array.getClass().getComponentType();
    1094            array = (T[]) Array.newInstance(componentType, size);
    1095        }
    1096        // Copy the values into the array
    1097        int i = 0;
    1098        for (Node<E> node = header.next; node != header; node = node.next, i++) {
    1099            array[i] = (T) node.getValue();
    1100        }
    1101        // Set the value after the last value to null
    1102        if (array.length > size) {
    1103            array[size] = null;
    1104        }
    1105        return array;
    1106    }
    1107
    1108    @Override
    1109    public String toString() {
    1110        if (isEmpty()) {
    1111            return "[]";
    1112        }
    1113        final StringBuilder buf = new StringBuilder(16 * size());
    1114        buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
    1115
    1116        final Iterator<E> it = iterator();
    1117        boolean hasNext = it.hasNext();
    1118        while (hasNext) {
    1119            final Object value = it.next();
    1120            buf.append(value == this ? "(this Collection)" : value);
    1121            hasNext = it.hasNext();
    1122            if (hasNext) {
    1123                buf.append(", ");
    1124            }
    1125        }
    1126        buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
    1127        return buf.toString();
    1128    }
    1129
    1130    /**
    1131     * Updates the node with a new value.
    1132     * This implementation sets the value on the node.
    1133     * Subclasses can override this to record the change.
    1134     *
    1135     * @param node  node to update
    1136     * @param value  new value of the node
    1137     */
    1138    protected void updateNode(final Node<E> node, final E value) {
    1139        node.setValue(value);
    1140    }
    1141
    1142}