Package org.apache.commons.collections4.list

# Class AbstractLinkedList<E>

java.lang.Object
org.apache.commons.collections4.list.AbstractLinkedList<E>

Type Parameters:
  `E` - the type of elements in this list

All Implemented Interfaces:
  `Iterable<E>`, `Collection<E>`, `List<E>`

Direct Known Subclasses:
  `CursorableLinkedList`, `NodeCachingLinkedList`

public abstract class AbstractLinkedList<E> extends Object implements List<E>
An abstract implementation of a linked list which provides numerous points for subclasses to override.

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.

Since:
  3.0

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `protected static class`
  `AbstractLinkedList.LinkedListIterator<E>`
  A list iterator over the linked list.
  `protected static class`
  `AbstractLinkedList.LinkedSubList<E>`
  The sublist implementation for AbstractLinkedList.
  `protected static class`
  `AbstractLinkedList.LinkedSubListIterator<E>`
  A list iterator over the linked sub list.
  `protected static class`
  `AbstractLinkedList.Node<E>`
  A node within the linked list.

- ## Constructor Summary

  Constructors
  Modifier
  Constructor
  Description
  `protected`
  `AbstractLinkedList()`
  Constructor that does nothing (intended for deserialization).
  `protected`
  `AbstractLinkedList(Collection<? extends E> coll)`
  Constructs a list copying data from the specified collection.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `add(int index, E value)`
  `boolean`
  `add(E value)`
  `boolean`
  `addAll(int index, Collection<? extends E> coll)`
  `boolean`
  `addAll(Collection<? extends E> coll)`
  `boolean`
  `addFirst(E o)`
  `boolean`
  `addLast(E o)`
  `protected void`
  `addNode(AbstractLinkedList.Node<E> nodeToInsert, AbstractLinkedList.Node<E> insertBeforeNode)`
  Inserts a new node into the list.
  `protected void`
  `addNodeAfter(AbstractLinkedList.Node<E> node, E value)`
  Creates a new node with the specified object as its `value` and inserts it after `node`.
  `protected void`
  `addNodeBefore(AbstractLinkedList.Node<E> node, E value)`
  Creates a new node with the specified object as its `value` and inserts it before `node`.
  `void`
  `clear()`
  `boolean`
  `contains(Object value)`
  `boolean`
  `containsAll(Collection<?> coll)`
  `protected AbstractLinkedList.Node<E>`
  `createHeaderNode()`
  Creates a new node with previous, next and element all set to null.
  `protected AbstractLinkedList.Node<E>`
  `createNode(E value)`
  Creates a new node with the specified properties.
  `protected Iterator<E>`
  `createSubListIterator(AbstractLinkedList.LinkedSubList<E> subList)`
  Creates an iterator for the sublist.
  `protected ListIterator<E>`
  `createSubListListIterator(AbstractLinkedList.LinkedSubList<E> subList, int fromIndex)`
  Creates a list iterator for the sublist.
  `protected void`
  `doReadObject(ObjectInputStream inputStream)`
  Deserializes the data held in this object to the stream specified.
  `protected void`
  `doWriteObject(ObjectOutputStream outputStream)`
  Serializes the data held in this object to the stream specified.
  `boolean`
  `equals(Object obj)`
  `E`
  `get(int index)`
  `E`
  `getFirst()`
  `E`
  `getLast()`
  `protected AbstractLinkedList.Node<E>`
  `getNode(int index, boolean endMarkerAllowed)`
  Gets the node at a particular index.
  `int`
  `hashCode()`
  `int`
  `indexOf(Object value)`
  `protected void`
  `init()`
  The equivalent of a default constructor, broken out so it can be called by any constructor and by `readObject`.
  `boolean`
  `isEmpty()`
  `protected boolean`
  `isEqualValue(Object value1, Object value2)`
  Compares two values for equals.
  `Iterator<E>`
  `iterator()`
  `int`
  `lastIndexOf(Object value)`
  `ListIterator<E>`
  `listIterator()`
  `ListIterator<E>`
  `listIterator(int fromIndex)`
  `E`
  `remove(int index)`
  `boolean`
  `remove(Object value)`
  `boolean`
  `removeAll(Collection<?> coll)`
  `protected void`
  `removeAllNodes()`
  Removes all nodes by resetting the circular list marker.
  `E`
  `removeFirst()`
  `E`
  `removeLast()`
  `protected void`
  `removeNode(AbstractLinkedList.Node<E> node)`
  Removes the specified node from the list.
  `boolean`
  `retainAll(Collection<?> coll)`
  `E`
  `set(int index, E value)`
  `int`
  `size()`
  `List<E>`
  `subList(int fromIndexInclusive, int toIndexExclusive)`
  Gets a sublist of the main list.
  `Object[]`
  `toArray()`
  `<T> T[]`
  `toArray(T[] array)`
  `String`
  `toString()`
  `protected void`
  `updateNode(AbstractLinkedList.Node<E> node, E value)`
  Updates the node with a new value.

  ### Methods inherited from class java.lang.Object

  `clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

  ### Methods inherited from interface java.util.Collection

  `parallelStream, removeIf, stream`

  ### Methods inherited from interface java.lang.Iterable

  `forEach`

  ### Methods inherited from interface java.util.List

  `replaceAll, sort, spliterator`

- ## Constructor Details

  - ### AbstractLinkedList

    protected AbstractLinkedList()
    Constructor that does nothing (intended for deserialization).

    If this constructor is used by a serializable subclass then the init() method must be called.

  - ### AbstractLinkedList

    protected AbstractLinkedList(Collection<? extends E> coll)
    Constructs a list copying data from the specified collection.
    Parameters:
      `coll` - the collection to copy

- ## Method Details

  - ### add

    public boolean add(E value)
    Specified by:
      `add` in interface `Collection<E>`
    Specified by:
      `add` in interface `List<E>`

  - ### add

    public void add(int index, E value)
    Specified by:
      `add` in interface `List<E>`

  - ### addAll

    public boolean addAll(Collection<? extends E> coll)
    Specified by:
      `addAll` in interface `Collection<E>`
    Specified by:
      `addAll` in interface `List<E>`

  - ### addAll

    public boolean addAll(int index, Collection<? extends E> coll)
    Specified by:
      `addAll` in interface `List<E>`

  - ### addFirst

    public boolean addFirst(E o)

  - ### addLast

    public boolean addLast(E o)

  - ### addNode

    protected void addNode(AbstractLinkedList.Node<E> nodeToInsert, AbstractLinkedList.Node<E> insertBeforeNode)
    Inserts a new node into the list.
    Parameters:
      `nodeToInsert` - new node to insert
      `insertBeforeNode` - node to insert before
    Throws:
      `NullPointerException` - if either node is null

  - ### addNodeAfter

    protected void addNodeAfter(AbstractLinkedList.Node<E> node, E value)
    Creates a new node with the specified object as its `value` and inserts it after `node`.

    This implementation uses `createNode(Object)` and `addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)`.

    Parameters:
      `node` - node to insert after
      `value` - value of the newly added node
    Throws:
      `NullPointerException` - if `node` is null

  - ### addNodeBefore

    protected void addNodeBefore(AbstractLinkedList.Node<E> node, E value)
    Creates a new node with the specified object as its `value` and inserts it before `node`.

    This implementation uses `createNode(Object)` and `addNode(AbstractLinkedList.Node,AbstractLinkedList.Node)`.

    Parameters:
      `node` - node to insert before
      `value` - value of the newly added node
    Throws:
      `NullPointerException` - if `node` is null

  - ### clear

    public void clear()
    Specified by:
      `clear` in interface `Collection<E>`
    Specified by:
      `clear` in interface `List<E>`

  - ### contains

    public boolean contains(Object value)
    Specified by:
      `contains` in interface `Collection<E>`
    Specified by:
      `contains` in interface `List<E>`

  - ### containsAll

    public boolean containsAll(Collection<?> coll)
    Specified by:
      `containsAll` in interface `Collection<E>`
    Specified by:
      `containsAll` in interface `List<E>`

  - ### createHeaderNode

    protected AbstractLinkedList.Node<E> createHeaderNode()
    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.
    Returns:
      newly created node

  - ### createNode

    protected AbstractLinkedList.Node<E> createNode(E value)
    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.
    Parameters:
      `value` - value of the new node
    Returns:
      a new node containing the value

  - ### createSubListIterator

    protected Iterator<E> createSubListIterator(AbstractLinkedList.LinkedSubList<E> subList)
    Creates an iterator for the sublist.
    Parameters:
      `subList` - the sublist to get an iterator for
    Returns:
      a new iterator on the given sublist

  - ### createSubListListIterator

    protected ListIterator<E> createSubListListIterator(AbstractLinkedList.LinkedSubList<E> subList, int fromIndex)
    Creates a list iterator for the sublist.
    Parameters:
      `subList` - the sublist to get an iterator for
      `fromIndex` - the index to start from, relative to the sublist
    Returns:
      a new list iterator on the given sublist

  - ### doReadObject

    protected void doReadObject(ObjectInputStream inputStream) throws IOException, ClassNotFoundException
    Deserializes the data held in this object to the stream specified.

    The first serializable subclass must call this method from `readObject`.

    Parameters:
      `inputStream` - the stream to read the object from
    Throws:
      `IOException` - if any error occurs while reading from the stream
      `ClassNotFoundException` - if a class read from the stream can not be loaded

  - ### doWriteObject

    protected void doWriteObject(ObjectOutputStream outputStream) throws IOException
    Serializes the data held in this object to the stream specified.

    The first serializable subclass must call this method from `writeObject`.

    Parameters:
      `outputStream` - the stream to write the object to
    Throws:
      `IOException` - if anything goes wrong

  - ### equals

    public boolean equals(Object obj)
    Specified by:
      `equals` in interface `Collection<E>`
    Specified by:
      `equals` in interface `List<E>`
    Overrides:
      `equals` in class `Object`

  - ### get

    public E get(int index)
    Specified by:
      `get` in interface `List<E>`

  - ### getFirst

    public E getFirst()

  - ### getLast

    public E getLast()

  - ### getNode

    protected AbstractLinkedList.Node<E> getNode(int index, boolean endMarkerAllowed) throws IndexOutOfBoundsException
    Gets the node at a particular index.
    Parameters:
      `index` - the index, starting from 0
      `endMarkerAllowed` - whether or not the end marker can be returned if startIndex is set to the list's size
    Returns:
      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

  - ### hashCode

    public int hashCode()
    Specified by:
      `hashCode` in interface `Collection<E>`
    Specified by:
      `hashCode` in interface `List<E>`
    Overrides:
      `hashCode` in class `Object`

  - ### indexOf

    public int indexOf(Object value)
    Specified by:
      `indexOf` in interface `List<E>`

  - ### init

    protected void init()
    The equivalent of a default constructor, broken out so it can be called by any constructor and by `readObject`. Subclasses which override this method should make sure they call super, so the list is initialized properly.

  - ### isEmpty

    public boolean isEmpty()
    Specified by:
      `isEmpty` in interface `Collection<E>`
    Specified by:
      `isEmpty` in interface `List<E>`

  - ### isEqualValue

    protected boolean isEqualValue(Object value1, Object value2)
    Compares two values for equals. This implementation uses the equals method. Subclasses can override this to match differently.
    Parameters:
      `value1` - the first value to compare, may be null
      `value2` - the second value to compare, may be null
    Returns:
      true if equal

  - ### iterator

    public Iterator<E> iterator()
    Specified by:
      `iterator` in interface `Collection<E>`
    Specified by:
      `iterator` in interface `Iterable<E>`
    Specified by:
      `iterator` in interface `List<E>`

  - ### lastIndexOf

    public int lastIndexOf(Object value)
    Specified by:
      `lastIndexOf` in interface `List<E>`

  - ### listIterator

    public ListIterator<E> listIterator()
    Specified by:
      `listIterator` in interface `List<E>`

  - ### listIterator

    public ListIterator<E> listIterator(int fromIndex)
    Specified by:
      `listIterator` in interface `List<E>`

  - ### remove

    public E remove(int index)
    Specified by:
      `remove` in interface `List<E>`

  - ### remove

    public boolean remove(Object value)
    Specified by:
      `remove` in interface `Collection<E>`
    Specified by:
      `remove` in interface `List<E>`

  - ### removeAll

    public boolean removeAll(Collection<?> coll)

    This implementation iterates over the elements of this list, checking each element in turn to see if it's contained in `coll`. If it's contained, it's removed from this list. As a consequence, it is advised to use a collection type for `coll` that provides a fast (e.g. O(1)) implementation of `Collection.contains(Object)`.

    Specified by:
      `removeAll` in interface `Collection<E>`
    Specified by:
      `removeAll` in interface `List<E>`

  - ### removeAllNodes

    protected void removeAllNodes()
    Removes all nodes by resetting the circular list marker.

  - ### removeFirst

    public E removeFirst()

  - ### removeLast

    public E removeLast()

  - ### removeNode

    protected void removeNode(AbstractLinkedList.Node<E> node)
    Removes the specified node from the list.
    Parameters:
      `node` - the node to remove
    Throws:
      `NullPointerException` - if `node` is null

  - ### retainAll

    public boolean retainAll(Collection<?> coll)

    This implementation iterates over the elements of this list, checking each element in turn to see if it's contained in `coll`. If it's not contained, it's removed from this list. As a consequence, it is advised to use a collection type for `coll` that provides a fast (e.g. O(1)) implementation of `Collection.contains(Object)`.

    Specified by:
      `retainAll` in interface `Collection<E>`
    Specified by:
      `retainAll` in interface `List<E>`

  - ### set

    public E set(int index, E value)
    Specified by:
      `set` in interface `List<E>`

  - ### size

    public int size()
    Specified by:
      `size` in interface `Collection<E>`
    Specified by:
      `size` in interface `List<E>`

  - ### subList

    public List<E> subList(int fromIndexInclusive, int toIndexExclusive)
    Gets a sublist of the main list.
    Specified by:
      `subList` in interface `List<E>`
    Parameters:
      `fromIndexInclusive` - the index to start from
      `toIndexExclusive` - the index to end at
    Returns:
      the new sublist

  - ### toArray

    public Object[] toArray()
    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`

  - ### toArray

    public <T> T[] toArray(T[] array)
    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`

  - ### toString

    public String toString()
    Overrides:
      `toString` in class `Object`

  - ### updateNode

    protected void updateNode(AbstractLinkedList.Node<E> node, E value)
    Updates the node with a new value. This implementation sets the value on the node. Subclasses can override this to record the change.
    Parameters:
      `node` - node to update
      `value` - new value of the node