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