AbstractLinkedList.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.list;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.OrderedIterator;

/**
 * An abstract implementation of a linked list which provides numerous points for
 * subclasses to override.
 * <p>
 * Overridable methods are provided to change the storage node and to change how
 * nodes are added to and removed. Hopefully, all you need for unusual subclasses
 * is here.
 * </p>
 *
 * @param <E> the type of elements in this list
 * @since 3.0
 * @deprecated use {@link AbstractLinkedListJava21} instead
 */
@Deprecated
public abstract class AbstractLinkedList<E> implements List<E> {

    /*
     * Implementation notes:
     * - a standard circular doubly-linked list
     * - a marker node is stored to mark the start and the end of the list
     * - node creation and removal always occurs through createNode() and
     *   removeNode().
     * - a modification count is kept, with the same semantics as
     * {@link java.util.LinkedList}.
     * - respects {@link AbstractList#modCount}
     */

    /**
     * A list iterator over the linked list.
     *
     * @param <E> the type of elements in this iterator.
     */
    protected static class LinkedListIterator<E> implements ListIterator<E>, OrderedIterator<E> {

        /** The parent list */
        protected final AbstractLinkedList<E> parent;

        /**
         * The node that will be returned by {@link #next()}. If this is equal
         * to {@link AbstractLinkedList#header} then there are no more values to return.
         */
        protected Node<E> next;

        /**
         * The index of {@link #next}.
         */
        protected int nextIndex;

        /**
         * The last node that was returned by {@link #next()} or {@link
         * #previous()}. Set to {@code null} if {@link #next()} or {@link
         * #previous()} haven't been called, or if the node has been removed
         * with {@link #remove()} or a new node added with {@link #add(Object)}.
         * Should be accessed through {@link #getLastNodeReturned()} to enforce
         * this behavior.
         */
        protected Node<E> current;

        /**
         * The modification count that the list is expected to have. If the list
         * doesn't have this count, then a
         * {@link java.util.ConcurrentModificationException} may be thrown by
         * the operations.
         */
        protected int expectedModCount;

        /**
         * Create a ListIterator for a list.
         *
         * @param parent  the parent list.
         * @param fromIndex  The starting index.
         * @throws IndexOutOfBoundsException if fromIndex is less than 0 or greater than the size of the list.
         */
        protected LinkedListIterator(final AbstractLinkedList<E> parent, final int fromIndex)
                throws IndexOutOfBoundsException {
            this.parent = parent;
            this.expectedModCount = parent.modCount;
            this.next = parent.getNode(fromIndex, true);
            this.nextIndex = fromIndex;
        }

        @Override
        public void add(final E obj) {
            checkModCount();
            parent.addNodeBefore(next, obj);
            current = null;
            nextIndex++;
            expectedModCount++;
        }

        /**
         * Checks the modification count of the list is the value that this
         * object expects.
         *
         * @throws ConcurrentModificationException If the list's modification
         * count isn't the value that was expected.
         */
        protected void checkModCount() {
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

        /**
         * Gets the last node returned.
         *
         * @return the last node returned
         * @throws IllegalStateException If {@link #next()} or {@link #previous()} haven't been called,
         * or if the node has been removed with {@link #remove()} or a new node added with {@link #add(Object)}.
         */
        protected Node<E> getLastNodeReturned() throws IllegalStateException {
            if (current == null) {
                throw new IllegalStateException();
            }
            return current;
        }

        @Override
        public boolean hasNext() {
            return next != parent.header;
        }

        @Override
        public boolean hasPrevious() {
            return next.previous != parent.header;
        }

        @Override
        public E next() {
            checkModCount();
            if (!hasNext()) {
                throw new NoSuchElementException("No element at index " + nextIndex + ".");
            }
            final E value = next.getValue();
            current = next;
            next = next.next;
            nextIndex++;
            return value;
        }

        @Override
        public int nextIndex() {
            return nextIndex;
        }

        @Override
        public E previous() {
            checkModCount();
            if (!hasPrevious()) {
                throw new NoSuchElementException("Already at start of list.");
            }
            next = next.previous;
            final E value = next.getValue();
            current = next;
            nextIndex--;
            return value;
        }

        @Override
        public int previousIndex() {
            // not normally overridden, as relative to nextIndex()
            return nextIndex() - 1;
        }

        @Override
        public void remove() {
            checkModCount();
            if (current == next) {
                // remove() following previous()
                next = next.next;
                parent.removeNode(getLastNodeReturned());
            } else {
                // remove() following next()
                parent.removeNode(getLastNodeReturned());
                nextIndex--;
            }
            current = null;
            expectedModCount++;
        }

        @Override
        public void set(final E value) {
            checkModCount();
            getLastNodeReturned().setValue(value);
        }

    }

    /**
     * The sublist implementation for AbstractLinkedList.
     *
     * @param <E> the type of elements in this list.
     */
    protected static class LinkedSubList<E> extends AbstractList<E> {

        /** The main list */
        AbstractLinkedList<E> parent;

        /** Offset from the main list */
        int offset;

        /** Sublist size */
        int size;

        /** Sublist modCount */
        int expectedModCount;

        /**
         * Constructs a new instance.
         *
         * @param parent The parent AbstractLinkedList.
         * @param fromIndex An index greater or equal to 0 and less than {@code toIndex}.
         * @param toIndex An index greater than {@code fromIndex}.
         */
        protected LinkedSubList(final AbstractLinkedList<E> parent, final int fromIndex, final int toIndex) {
            if (fromIndex < 0) {
                throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
            }
            if (toIndex > parent.size()) {
                throw new IndexOutOfBoundsException("toIndex = " + toIndex);
            }
            if (fromIndex > toIndex) {
                throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
            }
            this.parent = parent;
            this.offset = fromIndex;
            this.size = toIndex - fromIndex;
            this.expectedModCount = parent.modCount;
        }

        @Override
        public void add(final int index, final E obj) {
            rangeCheck(index, size + 1);
            checkModCount();
            parent.add(index + offset, obj);
            expectedModCount = parent.modCount;
            size++;
            modCount++;
        }

        @Override
        public boolean addAll(final Collection<? extends E> coll) {
            return addAll(size, coll);
        }

        @Override
        public boolean addAll(final int index, final Collection<? extends E> coll) {
            rangeCheck(index, size + 1);
            final int cSize = coll.size();
            if (cSize == 0) {
                return false;
            }

            checkModCount();
            parent.addAll(offset + index, coll);
            expectedModCount = parent.modCount;
            size += cSize;
            modCount++;
            return true;
        }

        /**
         * Throws a {@link ConcurrentModificationException} if this instance fails its concurrency check.
         */
        protected void checkModCount() {
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public void clear() {
            checkModCount();
            final Iterator<E> it = iterator();
            while (it.hasNext()) {
                it.next();
                it.remove();
            }
        }

        @Override
        public E get(final int index) {
            rangeCheck(index, size);
            checkModCount();
            return parent.get(index + offset);
        }

        @Override
        public Iterator<E> iterator() {
            checkModCount();
            return parent.createSubListIterator(this);
        }

        @Override
        public ListIterator<E> listIterator(final int index) {
            rangeCheck(index, size + 1);
            checkModCount();
            return parent.createSubListListIterator(this, index);
        }

        /**
         * Throws an {@link IndexOutOfBoundsException} if the given indices are out of bounds.
         *
         * @param index lower index.
         * @param beyond upper index.
         */
        protected void rangeCheck(final int index, final int beyond) {
            if (index < 0 || index >= beyond) {
                throw new IndexOutOfBoundsException("Index '" + index + "' out of bounds for size '" + size + "'");
            }
        }

        @Override
        public E remove(final int index) {
            rangeCheck(index, size);
            checkModCount();
            final E result = parent.remove(index + offset);
            expectedModCount = parent.modCount;
            size--;
            modCount++;
            return result;
        }

        @Override
        public E set(final int index, final E obj) {
            rangeCheck(index, size);
            checkModCount();
            return parent.set(index + offset, obj);
        }

        @Override
        public int size() {
            checkModCount();
            return size;
        }

        @Override
        public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
            return new LinkedSubList<>(parent, fromIndexInclusive + offset, toIndexExclusive + offset);
        }
    }

    /**
     * A list iterator over the linked sub list.
     *
     * @param <E> the type of elements in this iterator.
     */
    protected static class LinkedSubListIterator<E> extends LinkedListIterator<E> {

        /** The sub list. */
        protected final LinkedSubList<E> sub;

        /**
         * Constructs a new instance.
         *
         * @param sub The sub-list.
         * @param startIndex The starting index.
         */
        protected LinkedSubListIterator(final LinkedSubList<E> sub, final int startIndex) {
            super(sub.parent, startIndex + sub.offset);
            this.sub = sub;
        }

        @Override
        public void add(final E obj) {
            super.add(obj);
            sub.expectedModCount = parent.modCount;
            sub.size++;
        }

        @Override
        public boolean hasNext() {
            return nextIndex() < sub.size;
        }

        @Override
        public boolean hasPrevious() {
            return previousIndex() >= 0;
        }

        @Override
        public int nextIndex() {
            return super.nextIndex() - sub.offset;
        }

        @Override
        public void remove() {
            super.remove();
            sub.expectedModCount = parent.modCount;
            sub.size--;
        }
    }

    /**
     * A node within the linked list.
     * <p>
     * From Commons Collections 3.1, all access to the {@code value} property
     * is via the methods on this class.
     * </p>
     *
     * @param <E> The node value type.
     */
    protected static class Node<E> {

        /** A pointer to the node before this node */
        protected Node<E> previous;
        /** A pointer to the node after this node */
        protected Node<E> next;
        /** The object contained within this node */
        protected E value;

        /**
         * Constructs a new header node.
         */
        protected Node() {
            previous = this;
            next = this;
        }

        /**
         * Constructs a new node.
         *
         * @param value  the value to store
         */
        protected Node(final E value) {
            this.value = value;
        }

        /**
         * Constructs a new node.
         *
         * @param previous  the previous node in the list
         * @param next  the next node in the list
         * @param value  the value to store
         */
        protected Node(final Node<E> previous, final Node<E> next, final E value) {
            this.previous = previous;
            this.next = next;
            this.value = value;
        }

        /**
         * Gets the next node.
         *
         * @return the next node
         * @since 3.1
         */
        protected Node<E> getNextNode() {
            return next;
        }

        /**
         * Gets the previous node.
         *
         * @return the previous node
         * @since 3.1
         */
        protected Node<E> getPreviousNode() {
            return previous;
        }

        /**
         * Gets the value of the node.
         *
         * @return the value
         * @since 3.1
         */
        protected E getValue() {
            return value;
        }

        /**
         * Sets the next node.
         *
         * @param next  the next node
         * @since 3.1
         */
        protected void setNextNode(final Node<E> next) {
            this.next = next;
        }

        /**
         * Sets the previous node.
         *
         * @param previous  the previous node
         * @since 3.1
         */
        protected void setPreviousNode(final Node<E> previous) {
            this.previous = previous;
        }

        /**
         * Sets the value of the node.
         *
         * @param value  the value
         * @since 3.1
         */
        protected void setValue(final E value) {
            this.value = value;
        }
    }

    /**
     * A {@link Node} which indicates the start and end of the list and does not
     * hold a value. The value of {@code next} is the first item in the
     * list. The value of {@code previous} is the last item in the list.
     */
    transient Node<E> header;

    /** The size of the list */
    transient int size;

    /** Modification count for iterators */
    transient int modCount;

    /**
     * Constructor that does nothing (intended for deserialization).
     * <p>
     * If this constructor is used by a serializable subclass then the init()
     * method must be called.
     */
    protected AbstractLinkedList() {
    }

    /**
     * Constructs a list copying data from the specified collection.
     *
     * @param coll  the collection to copy
     */
    protected AbstractLinkedList(final Collection<? extends E> coll) {
        init();
        addAll(coll);
    }

    @Override
    public boolean add(final E value) {
        addLast(value);
        return true;
    }

    @Override
    public void add(final int index, final E value) {
        final Node<E> node = getNode(index, true);
        addNodeBefore(node, value);
    }

    @Override
    public boolean addAll(final Collection<? extends E> coll) {
        return addAll(size, coll);
    }

    @Override
    public boolean addAll(final int index, final Collection<? extends E> coll) {
        final Node<E> node = getNode(index, true);
        for (final E e : coll) {
            addNodeBefore(node, e);
        }
        return true;
    }

    /**
     * Adds an element at the beginning.
     *
     * @param e the element to beginning.
     * @return true.
     */
    public boolean addFirst(final E e) {
        addNodeAfter(header, e);
        return true;
    }

    /**
     * Adds an element at the end.
     *
     * @param e the element to add.
     * @return true.
     */
    public boolean addLast(final E e) {
        addNodeBefore(header, e);
        return true;
    }

    /**
     * Inserts a new node into the list.
     *
     * @param nodeToInsert  new node to insert
     * @param insertBeforeNode  node to insert before
     * @throws NullPointerException if either node is null
     */
    protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
        Objects.requireNonNull(nodeToInsert, "nodeToInsert");
        Objects.requireNonNull(insertBeforeNode, "insertBeforeNode");
        nodeToInsert.next = insertBeforeNode;
        nodeToInsert.previous = insertBeforeNode.previous;
        insertBeforeNode.previous.next = nodeToInsert;
        insertBeforeNode.previous = nodeToInsert;
        size++;
        modCount++;
    }

    /**
     * Creates a new node with the specified object as its
     * {@code value} and inserts it after {@code node}.
     * <p>
     * This implementation uses {@link #createNode(Object)} and
     * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
     *
     * @param node  node to insert after
     * @param value  value of the newly added node
     * @throws NullPointerException if {@code node} is null
     */
    protected void addNodeAfter(final Node<E> node, final E value) {
        final Node<E> newNode = createNode(value);
        addNode(newNode, node.next);
    }

    /**
     * Creates a new node with the specified object as its
     * {@code value} and inserts it before {@code node}.
     * <p>
     * This implementation uses {@link #createNode(Object)} and
     * {@link #addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)}.
     *
     * @param node  node to insert before
     * @param value  value of the newly added node
     * @throws NullPointerException if {@code node} is null
     */
    protected void addNodeBefore(final Node<E> node, final E value) {
        final Node<E> newNode = createNode(value);
        addNode(newNode, node);
    }

    @Override
    public void clear() {
        removeAllNodes();
    }

    @Override
    public boolean contains(final Object value) {
        return indexOf(value) != -1;
    }

    @Override
    public boolean containsAll(final Collection<?> coll) {
        for (final Object o : coll) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    /**
     * Creates a new node with previous, next and element all set to null.
     * This implementation creates a new empty Node.
     * Subclasses can override this to create a different class.
     *
     * @return  newly created node
     */
    protected Node<E> createHeaderNode() {
        return new Node<>();
    }

    /**
     * Creates a new node with the specified properties.
     * This implementation creates a new Node with data.
     * Subclasses can override this to create a different class.
     *
     * @param value  value of the new node
     * @return a new node containing the value
     */
    protected Node<E> createNode(final E value) {
        return new Node<>(value);
    }

    /**
     * Creates an iterator for the sublist.
     *
     * @param subList  the sublist to get an iterator for
     * @return a new iterator on the given sublist
     */
    protected Iterator<E> createSubListIterator(final LinkedSubList<E> subList) {
        return createSubListListIterator(subList, 0);
    }

    /**
     * Creates a list iterator for the sublist.
     *
     * @param subList  the sublist to get an iterator for
     * @param fromIndex  the index to start from, relative to the sublist
     * @return a new list iterator on the given sublist
     */
    protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) {
        return new LinkedSubListIterator<>(subList, fromIndex);
    }

    /**
     * Deserializes the data held in this object to the stream specified.
     * <p>
     * The first serializable subclass must call this method from
     * {@code readObject}.
     *
     * @param inputStream  the stream to read the object from
     * @throws IOException  if any error occurs while reading from the stream
     * @throws ClassNotFoundException  if a class read from the stream cannot be loaded
     */
    @SuppressWarnings("unchecked")
    protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException {
        init();
        final int size = inputStream.readInt();
        for (int i = 0; i < size; i++) {
            add((E) inputStream.readObject());
        }
    }

    /**
     * Serializes the data held in this object to the stream specified.
     * <p>
     * The first serializable subclass must call this method from
     * {@code writeObject}.
     *
     * @param outputStream  the stream to write the object to
     * @throws IOException  if anything goes wrong
     */
    protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException {
        // Write the size so we know how many nodes to read back
        outputStream.writeInt(size());
        for (final E e : this) {
            outputStream.writeObject(e);
        }
    }

    @Override
    public boolean equals(final Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof List)) {
            return false;
        }
        final List<?> other = (List<?>) obj;
        if (other.size() != size()) {
            return false;
        }
        final ListIterator<?> it1 = listIterator();
        final ListIterator<?> it2 = other.listIterator();
        while (it1.hasNext() && it2.hasNext()) {
            if (!Objects.equals(it1.next(), it2.next())) {
                return false;
            }
        }
        return !(it1.hasNext() || it2.hasNext());
    }

    @Override
    public E get(final int index) {
        final Node<E> node = getNode(index, false);
        return node.getValue();
    }

    /**
     * Gets the first element.
     *
     * @return the first element.
     */
    public E getFirst() {
        final Node<E> node = header.next;
        if (node == header) {
            throw new NoSuchElementException();
        }
        return node.getValue();
    }

    /**
     * Gets the last element.
     *
     * @return the last element.
     */
    public E getLast() {
        final Node<E> node = header.previous;
        if (node == header) {
            throw new NoSuchElementException();
        }
        return node.getValue();
    }

    /**
     * Gets the node at a particular index.
     *
     * @param index  the index, starting from 0
     * @param endMarkerAllowed  whether or not the end marker can be returned if
     * startIndex is set to the list's size
     * @return the node at the given index
     * @throws IndexOutOfBoundsException if the index is less than 0; equal to
     * the size of the list and endMakerAllowed is false; or greater than the
     * size of the list
     */
    protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException {
        // Check the index is within the bounds
        if (index < 0) {
            throw new IndexOutOfBoundsException("Couldn't get the node: " +
                    "index (" + index + ") less than zero.");
        }
        if (!endMarkerAllowed && index == size) {
            throw new IndexOutOfBoundsException("Couldn't get the node: " +
                    "index (" + index + ") is the size of the list.");
        }
        if (index > size) {
            throw new IndexOutOfBoundsException("Couldn't get the node: " +
                    "index (" + index + ") greater than the size of the " +
                    "list (" + size + ").");
        }
        // Search the list and get the node
        Node<E> node;
        if (index < size / 2) {
            // Search forwards
            node = header.next;
            for (int currentIndex = 0; currentIndex < index; currentIndex++) {
                node = node.next;
            }
        } else {
            // Search backwards
            node = header;
            for (int currentIndex = size; currentIndex > index; currentIndex--) {
                node = node.previous;
            }
        }
        return node;
    }

    @Override
    public int hashCode() {
        int hashCode = 1;
        for (final E e : this) {
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }

    @Override
    public int indexOf(final Object value) {
        int i = 0;
        for (Node<E> node = header.next; node != header; node = node.next) {
            if (isEqualValue(node.getValue(), value)) {
                return i;
            }
            i++;
        }
        return CollectionUtils.INDEX_NOT_FOUND;
    }

    /**
     * The equivalent of a default constructor, broken out so it can be called
     * by any constructor and by {@code readObject}.
     * Subclasses which override this method should make sure they call super,
     * so the list is initialized properly.
     */
    protected void init() {
        header = createHeaderNode();
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Compares two values for equals.
     * This implementation uses the equals method.
     * Subclasses can override this to match differently.
     *
     * @param value1  the first value to compare, may be null
     * @param value2  the second value to compare, may be null
     * @return true if equal
     */
    protected boolean isEqualValue(final Object value1, final Object value2) {
        return Objects.equals(value1, value2);
    }

    @Override
    public Iterator<E> iterator() {
        return listIterator();
    }

    @Override
    public int lastIndexOf(final Object value) {
        int i = size - 1;
        for (Node<E> node = header.previous; node != header; node = node.previous) {
            if (isEqualValue(node.getValue(), value)) {
                return i;
            }
            i--;
        }
        return CollectionUtils.INDEX_NOT_FOUND;
    }

    @Override
    public ListIterator<E> listIterator() {
        return new LinkedListIterator<>(this, 0);
    }

    @Override
    public ListIterator<E> listIterator(final int fromIndex) {
        return new LinkedListIterator<>(this, fromIndex);
    }

    @Override
    public E remove(final int index) {
        final Node<E> node = getNode(index, false);
        final E oldValue = node.getValue();
        removeNode(node);
        return oldValue;
    }

    @Override
    public boolean remove(final Object value) {
        for (Node<E> node = header.next; node != header; node = node.next) {
            if (isEqualValue(node.getValue(), value)) {
                removeNode(node);
                return true;
            }
        }
        return false;
    }

    /**
     * {@inheritDoc}
     * <p>
     * This implementation iterates over the elements of this list, checking each element in
     * turn to see if it's contained in {@code coll}. If it's contained, it's removed
     * from this list. As a consequence, it is advised to use a collection type for
     * {@code coll} that provides a fast (for example O(1)) implementation of
     * {@link Collection#contains(Object)}.
     */
    @Override
    public boolean removeAll(final Collection<?> coll) {
        boolean modified = false;
        final Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (coll.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    /**
     * Removes all nodes by resetting the circular list marker.
     */
    protected void removeAllNodes() {
        header.next = header;
        header.previous = header;
        size = 0;
        modCount++;
    }

    /**
     * Removes the first element.
     *
     * @return The value removed.
     */
    public E removeFirst() {
        final Node<E> node = header.next;
        if (node == header) {
            throw new NoSuchElementException();
        }
        final E oldValue = node.getValue();
        removeNode(node);
        return oldValue;
    }

    /**
     * Removes the last element.
     *
     * @return The value removed.
     */
    public E removeLast() {
        final Node<E> node = header.previous;
        if (node == header) {
            throw new NoSuchElementException();
        }
        final E oldValue = node.getValue();
        removeNode(node);
        return oldValue;
    }

    /**
     * Removes the specified node from the list.
     *
     * @param node  the node to remove
     * @throws NullPointerException if {@code node} is null
     */
    protected void removeNode(final Node<E> node) {
        Objects.requireNonNull(node, "node");
        node.previous.next = node.next;
        node.next.previous = node.previous;
        size--;
        modCount++;
    }

    /**
     * {@inheritDoc}
     * <p>
     * This implementation iterates over the elements of this list, checking each element in
     * turn to see if it's contained in {@code coll}. If it's not contained, it's removed
     * from this list. As a consequence, it is advised to use a collection type for
     * {@code coll} that provides a fast (for example O(1)) implementation of
     * {@link Collection#contains(Object)}.
     */
    @Override
    public boolean retainAll(final Collection<?> coll) {
        boolean modified = false;
        final Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!coll.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public E set(final int index, final E value) {
        final Node<E> node = getNode(index, false);
        final E oldValue = node.getValue();
        updateNode(node, value);
        return oldValue;
    }

    @Override
    public int size() {
        return size;
    }

    /**
     * Gets a sublist of the main list.
     *
     * @param fromIndexInclusive  the index to start from
     * @param toIndexExclusive  the index to end at
     * @return the new sublist
     */
    @Override
    public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) {
        return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive);
    }

    @Override
    public Object[] toArray() {
        return toArray(new Object[size]);
    }

    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] array) {
        // Extend the array if needed
        if (array.length < size) {
            final Class<?> componentType = array.getClass().getComponentType();
            array = (T[]) Array.newInstance(componentType, size);
        }
        // Copy the values into the array
        int i = 0;
        for (Node<E> node = header.next; node != header; node = node.next, i++) {
            array[i] = (T) node.getValue();
        }
        // Set the value after the last value to null
        if (array.length > size) {
            array[size] = null;
        }
        return array;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
        final StringBuilder buf = new StringBuilder(16 * size());
        buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);

        final Iterator<E> it = iterator();
        boolean hasNext = it.hasNext();
        while (hasNext) {
            final Object value = it.next();
            buf.append(value == this ? "(this Collection)" : value);
            hasNext = it.hasNext();
            if (hasNext) {
                buf.append(", ");
            }
        }
        buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
        return buf.toString();
    }

    /**
     * Updates the node with a new value.
     * This implementation sets the value on the node.
     * Subclasses can override this to record the change.
     *
     * @param node  node to update
     * @param value  new value of the node
     */
    protected void updateNode(final Node<E> node, final E value) {
        node.setValue(value);
    }

}