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