# Class LinkedList<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.AbstractSequentialList<E>
java.util.LinkedList<E>

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

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>

LinkedList is an implementation of List, backed by a linked list. All optional operations are supported, adding, removing and replacing. The elements can be any objects.

##### Since

1.2

- ## Field Summary

  ### Fields inherited from class AbstractList

  `modCount`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `LinkedList()`
  Constructs a new empty instance of `LinkedList`.
  `LinkedList(Collection<? extends E> collection)`
  Constructs a new instance of `LinkedList` that holds all of the elements contained in the specified `collection`.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `void`
  `add(int location, E object)`
  Inserts the specified object into this `LinkedList` at the specified location.
  `boolean`
  `add(E object)`
  Adds the specified object at the end of this `LinkedList`.
  `boolean`
  `addAll(int location, Collection<? extends E> collection)`
  Inserts the objects in the specified collection at the specified location in this `LinkedList`.
  `boolean`
  `addAll(Collection<? extends E> collection)`
  Adds the objects in the specified Collection to this `LinkedList`.
  `void`
  `addFirst(E object)`
  Adds the specified object at the beginning of this `LinkedList`.
  `void`
  `addLast(E object)`
  Adds the specified object at the end of this `LinkedList`.
  `void`
  `clear()`
  Removes all elements from this `LinkedList`, leaving it empty.
  `boolean`
  `contains(Object object)`
  Searches this `LinkedList` for the specified object.
  `Iterator<E>`
  `descendingIterator()`
  Returns the iterator in reverse order, from tail to head.
  `E`
  `element()`
  Gets but does not remove the element at the head of the queue.
  `E`
  `get(int location)`
  Returns the element at the specified location in this list.
  `E`
  `getFirst()`
  Returns the first element in this `LinkedList`.
  `E`
  `getLast()`
  Returns the last element in this `LinkedList`.
  `int`
  `indexOf(Object object)`
  Searches this list for the specified object and returns the index of the first occurrence.
  `int`
  `lastIndexOf(Object object)`
  Searches this `LinkedList` for the specified object and returns the index of the last occurrence.
  `ListIterator<E>`
  `listIterator(int location)`
  Returns a ListIterator on the elements of this `LinkedList`.
  `boolean`
  `offer(E o)`
  Inserts the specified element into the queue provided that the condition allows such an operation.
  `boolean`
  `offerFirst(E e)`
  Inserts an element at the head of this deque unless it would violate size limit.
  `boolean`
  `offerLast(E e)`
  Inserts an element at the tail of this deque unless it would violate size limit.
  `E`
  `peek()`
  Gets but does not remove the element at the head of the queue.
  `E`
  `peekFirst()`
  Gets but not removes the head element of this deque.
  `E`
  `peekLast()`
  Gets but not removes the tail element of this deque.
  `E`
  `poll()`
  Gets and removes the element at the head of the queue, or returns `null` if there is no element in the queue.
  `E`
  `pollFirst()`
  Gets and removes the head element of this deque.
  `E`
  `pollLast()`
  Gets and removes the tail element of this deque.
  `E`
  `pop()`
  Pops the head element of the deque, just same as removeFirst().
  `void`
  `push(E e)`
  Pushes the element to the deque(at the head of the deque), just same as addFirst(E).
  `E`
  `remove()`
  Gets and removes the element at the head of the queue.
  `E`
  `remove(int location)`
  Removes the object at the specified location from this `LinkedList`.
  `boolean`
  `remove(Object object)`
  Removes one instance of the specified object from this `Collection` if one is contained (optional).
  `E`
  `removeFirst()`
  Removes the first object from this `LinkedList`.
  `boolean`
  `removeFirstOccurrence(Object o)`
  Removes the first equivalent element of the specified object.
  `E`
  `removeLast()`
  Removes the last object from this `LinkedList`.
  `boolean`
  `removeLastOccurrence(Object o)`
  Removes the last equivalent element of the specified object.
  `E`
  `set(int location, E object)`
  Replaces the element at the specified location in this `LinkedList` with the specified object.
  `int`
  `size()`
  Returns the number of elements in this `LinkedList`.
  `Object[]`
  `toArray()`
  Returns a new array containing all elements contained in this `LinkedList`.
  `<T> T[]`
  `toArray(T[] contents)`
  Returns an array containing all elements contained in this `LinkedList`.

  ### Methods inherited from class AbstractSequentialList

  `iterator`

  ### Methods inherited from class AbstractList

  `equals, hashCode, listIterator, removeRange, subList`

  ### Methods inherited from class AbstractCollection

  `containsAll, isEmpty, removeAll, retainAll, toString`

  ### Methods inherited from class Object

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

  ### Methods inherited from interface Collection

  `removeIf`

  ### Methods inherited from interface Iterable

  `forEach`

  ### Methods inherited from interface List

  `containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, replaceAll, retainAll, sort, subList`

- ## Constructor Details

  - ### LinkedList

    public LinkedList()
    Constructs a new empty instance of `LinkedList`.

  - ### LinkedList

    public LinkedList(Collection<? extends E> collection)

    Constructs a new instance of `LinkedList` that holds all of the elements contained in the specified `collection`. The order of the elements in this new `LinkedList` will be determined by the iteration order of `collection`.

    ###### Parameters

    - `collection`: the collection of elements to add.

- ## Method Details

  - ### add

    public void add(int location, E object)

    Inserts the specified object into this `LinkedList` at the specified location. The object is inserted before any previous element at the specified location. If the location is equal to the size of this `LinkedList`, the object is added at the end.

    ###### Parameters

    - `location`: the index at which to insert.

    - `object`: the object to add.

    ###### Throws

    - `IndexOutOfBoundsException`: if `location = size()`
    Specified by:
      `add` in interface `List<E>`
    Overrides:
      `add` in class `AbstractSequentialList<E>`

  - ### add

    public boolean add(E object)

    Adds the specified object at the end of this `LinkedList`.

    ###### Parameters

    - `object`: the object to add.

    ###### Returns

    always true

    Specified by:
      `add` in interface `Collection<E>`
    Specified by:
      `add` in interface `List<E>`
    Overrides:
      `add` in class `AbstractList<E>`
    Returns:

      `true` if this `Collection` is modified, `false` otherwise.

      ###### Throws

      - `UnsupportedOperationException`: if adding to this `Collection` is not supported.

      - `ClassCastException`: @throws ClassCastException if the class of the object is inappropriate for this collection.

      - `IllegalArgumentException`: if the object cannot be added to this `Collection`.

      - `NullPointerException`: if null elements cannot be added to the `Collection`.

  - ### addAll

    public boolean addAll(int location, Collection<? extends E> collection)

    Inserts the objects in the specified collection at the specified location in this `LinkedList`. The objects are added in the order they are returned from the collection's iterator.

    ###### Parameters

    - `location`: the index at which to insert.

    - `collection`: the collection of objects

    ###### Returns

    Specified by:
      `addAll` in interface `List<E>`
    Overrides:
      `addAll` in class `AbstractSequentialList<E>`
    Returns:

      `true` if this `LinkedList` is modified, `false` otherwise.

      ###### Throws

      - `ClassCastException`: if the class of an object is inappropriate for this list.

      - `IllegalArgumentException`: if an object cannot be added to this list.

      - `IndexOutOfBoundsException`: if `location size()`

  - ### addAll

    public boolean addAll(Collection<? extends E> collection)

    Adds the objects in the specified Collection to this `LinkedList`.

    ###### Parameters

    - `collection`: the collection of objects.

    ###### Returns

    Specified by:
      `addAll` in interface `Collection<E>`
    Specified by:
      `addAll` in interface `List<E>`
    Overrides:
      `addAll` in class `AbstractCollection<E>`
    Returns:
      `true` if this `LinkedList` is modified, `false` otherwise.

  - ### addFirst

    public void addFirst(E object)

    Adds the specified object at the beginning of this `LinkedList`.

    ###### Parameters

    - `object`: the object to add.
    Specified by:
      `addFirst` in interface `Deque<E>`

  - ### addLast

    public void addLast(E object)

    Adds the specified object at the end of this `LinkedList`.

    ###### Parameters

    - `object`: the object to add.
    Specified by:
      `addLast` in interface `Deque<E>`

  - ### clear

    public void clear()

    Removes all elements from this `LinkedList`, leaving it empty.

    ###### See also

    - List#isEmpty

    - #size

    Specified by:
      `clear` in interface `Collection<E>`
    Specified by:
      `clear` in interface `List<E>`
    Overrides:
      `clear` in class `AbstractList<E>`

  - ### contains

    public boolean contains(Object object)

    Searches this `LinkedList` for the specified object.

    ###### Parameters

    - `object`: the object to search for.

    ###### Returns

    Specified by:
      `contains` in interface `Collection<E>`
    Specified by:
      `contains` in interface `List<E>`
    Overrides:
      `contains` in class `AbstractCollection<E>`
    Returns:
      `true` if `object` is an element of this `LinkedList`, `false` otherwise

  - ### get

    public E get(int location)
    Description copied from class: `AbstractList`

    Returns the element at the specified location in this list.

    ###### Parameters

    - `location`: the index of the element to return.

    ###### Returns

    the element at the specified index.

    ###### Throws

    - `IndexOutOfBoundsException`: if `location = size()`
    Specified by:
      `get` in interface `List<E>`
    Overrides:
      `get` in class `AbstractSequentialList<E>`

  - ### getFirst

    public E getFirst()

    Returns the first element in this `LinkedList`.

    ###### Returns

    the first element.

    ###### Throws

    - `NoSuchElementException`: if this `LinkedList` is empty.
    Specified by:
      `getFirst` in interface `Deque<E>`

  - ### getLast

    public E getLast()

    Returns the last element in this `LinkedList`.

    ###### Returns

    the last element

    ###### Throws

    - `NoSuchElementException`: if this `LinkedList` is empty
    Specified by:
      `getLast` in interface `Deque<E>`

  - ### indexOf

    public int indexOf(Object object)
    Description copied from class: `AbstractList`

    Searches this list for the specified object and returns the index of the first occurrence.

    ###### Parameters

    - `object`: the object to search for.

    ###### Returns

    Specified by:
      `indexOf` in interface `List<E>`
    Overrides:
      `indexOf` in class `AbstractList<E>`
    Returns:
      the index of the first occurrence of the object, or -1 if it was not found.

  - ### lastIndexOf

    public int lastIndexOf(Object object)

    Searches this `LinkedList` for the specified object and returns the index of the last occurrence.

    ###### Parameters

    - `object`: the object to search for

    ###### Returns

    Specified by:
      `lastIndexOf` in interface `List<E>`
    Overrides:
      `lastIndexOf` in class `AbstractList<E>`
    Returns:
      the index of the last occurrence of the object, or -1 if it was not found.

  - ### listIterator

    public ListIterator<E> listIterator(int location)

    Returns a ListIterator on the elements of this `LinkedList`. The elements are iterated in the same order that they occur in the `LinkedList`. The iteration starts at the specified location.

    ###### Parameters

    - `location`: the index at which to start the iteration

    ###### Returns

    a ListIterator on the elements of this `LinkedList`

    ###### Throws

    - `IndexOutOfBoundsException`: if `location = size()`

    ###### See also

    - ListIterator
    Specified by:
      `listIterator` in interface `List<E>`
    Specified by:
      `listIterator` in class `AbstractSequentialList<E>`

  - ### remove

    public E remove(int location)

    Removes the object at the specified location from this `LinkedList`.

    ###### Parameters

    - `location`: the index of the object to remove

    ###### Returns

    the removed object

    ###### Throws

    - `IndexOutOfBoundsException`: if `location = size()`
    Specified by:
      `remove` in interface `List<E>`
    Overrides:
      `remove` in class `AbstractSequentialList<E>`

  - ### remove

    public boolean remove(Object object)
    Description copied from class: `AbstractCollection`

    Removes one instance of the specified object from this `Collection` if one is contained (optional). This implementation iterates over this `Collection` and tests for each element `e` returned by the iterator, whether `e` is equal to the given object. If `object != null` then this test is performed using `object.equals(e)`, otherwise using `object == null`. If an element equal to the given object is found, then the `remove` method is called on the iterator and `true` is returned, `false` otherwise. If the iterator does not support removing elements, an `UnsupportedOperationException` is thrown.

    ###### Parameters

    - `object`: the object to remove.

    ###### Returns

    Specified by:
      `remove` in interface `Collection<E>`
    Specified by:
      `remove` in interface `List<E>`
    Overrides:
      `remove` in class `AbstractCollection<E>`
    Returns:

      `true` if this `Collection` is modified, `false` otherwise.

      ###### Throws

      - `UnsupportedOperationException`: if removing from this `Collection` is not supported.

      - `ClassCastException`: if the object passed is not of the correct type.

      - `NullPointerException`: @throws NullPointerException if `object` is `null` and this `Collection` doesn't support `null` elements.

  - ### removeFirst

    public E removeFirst()

    Removes the first object from this `LinkedList`.

    ###### Returns

    the removed object.

    ###### Throws

    - `NoSuchElementException`: if this `LinkedList` is empty.
    Specified by:
      `removeFirst` in interface `Deque<E>`

  - ### removeLast

    public E removeLast()

    Removes the last object from this `LinkedList`.

    ###### Returns

    the removed object.

    ###### Throws

    - `NoSuchElementException`: if this `LinkedList` is empty.
    Specified by:
      `removeLast` in interface `Deque<E>`

  - ### descendingIterator

    public Iterator<E> descendingIterator()

    Returns the iterator in reverse order, from tail to head.

    ###### Returns

    the iterator in reverse order

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#descendingIterator()
    Specified by:
      `descendingIterator` in interface `Deque<E>`

  - ### offerFirst

    public boolean offerFirst(E e)

    Inserts an element at the head of this deque unless it would violate size limit. It is better than the addFirst(E) method in a size-limited deque, because the latter one may fail to add the element only by throwing an exception.

    ###### Parameters

    - `e`: the element

    ###### Returns

    true if the operation succeeds or false if it fails.

    ###### Throws

    - `ClassCastException`: if the class of element can not be added into this deque

    - `NullPointerException`: @throws NullPointerException if the element is null and the deque can not contain null element

    - `IllegalArgumentException`: if the element can not be added due to some property.

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#offerFirst(java.lang.Object)
    Specified by:
      `offerFirst` in interface `Deque<E>`

  - ### offerLast

    public boolean offerLast(E e)

    Inserts an element at the tail of this deque unless it would violate size limit. It is better than the addLast(E) method in a size-limited deque, because the latter one may fail to add the element only by throwing an exception.

    ###### Parameters

    - `e`: the element

    ###### Returns

    true if the operation succeeds or false if it fails

    ###### Throws

    - `ClassCastException`: if the class of element can not be added into this deque

    - `NullPointerException`: @throws NullPointerException if the element is null and the deque can not contain null element

    - `IllegalArgumentException`: if the element can not be added due to some property

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#offerLast(java.lang.Object)
    Specified by:
      `offerLast` in interface `Deque<E>`

  - ### peekFirst

    public E peekFirst()

    Gets but not removes the head element of this deque. This method returns null if the deque is empty.

    ###### Returns

    the head element or null if the deque is empty

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#peekFirst()
    Specified by:
      `peekFirst` in interface `Deque<E>`

  - ### peekLast

    public E peekLast()

    Gets but not removes the tail element of this deque. This method returns null if the deque is empty.

    ###### Returns

    the tail element or null if the deque is empty

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#peekLast()
    Specified by:
      `peekLast` in interface `Deque<E>`

  - ### pollFirst

    public E pollFirst()

    Gets and removes the head element of this deque. This method returns null if the deque is empty.

    ###### Returns

    the head element or null if the deque is empty

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#pollFirst()
    Specified by:
      `pollFirst` in interface `Deque<E>`

  - ### pollLast

    public E pollLast()

    Gets and removes the tail element of this deque. This method returns null if the deque is empty.

    ###### Returns

    the tail element or null if the deque is empty

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#pollLast()
    Specified by:
      `pollLast` in interface `Deque<E>`

  - ### pop

    public E pop()

    Pops the head element of the deque, just same as removeFirst().

    ###### Returns

    the head element

    ###### Throws

    - `NoSuchElementException`: if the deque is empty

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#pop()
    Specified by:
      `pop` in interface `Deque<E>`

  - ### push

    public void push(E e)

    Pushes the element to the deque(at the head of the deque), just same as addFirst(E).

    ###### Parameters

    - `e`: the element

    ###### Throws

    - `IllegalStateException`: if it can not add now due to size limit

    - `ClassCastException`: if the class of element can not be added into this deque

    - `NullPointerException`: @throws NullPointerException if the element is null and the deque can not contain null element

    - `IllegalArgumentException`: if the element can not be added due to some property.

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#push(java.lang.Object)
    Specified by:
      `push` in interface `Deque<E>`

  - ### removeFirstOccurrence

    public boolean removeFirstOccurrence(Object o)

    Removes the first equivalent element of the specified object. If the deque does not contain the element, it is unchanged and returns false.

    ###### Parameters

    - `o`: the element to be removed

    ###### Returns

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#removeFirstOccurrence(java.lang.Object)
    Specified by:
      `removeFirstOccurrence` in interface `Deque<E>`
    Returns:

      true if the operation succeeds or false if the deque does not contain the element.

      ###### Throws

      - `ClassCastException`: if the class of the element is incompatible with the deque

      - `NullPointerException`: @throws NullPointerException if the element is null and the deque can not contain null element

  - ### removeLastOccurrence

    public boolean removeLastOccurrence(Object o)

    Removes the last equivalent element of the specified object. If the deque does not contain the element, it is unchanged and returns false.

    ###### Parameters

    - `o`: the element to be removed

    ###### Returns

    ###### Since

    1.6

    ###### See also

    - java.util.Deque#removeLastOccurrence(java.lang.Object)
    Specified by:
      `removeLastOccurrence` in interface `Deque<E>`
    Returns:

      true if the operation succeeds or false if the deque does not contain the element.

      ###### Throws

      - `ClassCastException`: if the class of the element is incompatible with the deque

      - `NullPointerException`: @throws NullPointerException if the element is null and the deque can not contain null element

  - ### set

    public E set(int location, E object)

    Replaces the element at the specified location in this `LinkedList` with the specified object.

    ###### Parameters

    - `location`: the index at which to put the specified object.

    - `object`: the object to add.

    ###### Returns

    the previous element at the index.

    ###### Throws

    - `ClassCastException`: if the class of an object is inappropriate for this list.

    - `IllegalArgumentException`: if an object cannot be added to this list.

    - `IndexOutOfBoundsException`: if `location = size()`

    Specified by:
      `set` in interface `List<E>`
    Overrides:
      `set` in class `AbstractSequentialList<E>`

  - ### size

    public int size()

    Returns the number of elements in this `LinkedList`.

    ###### Returns

    the number of elements in this `LinkedList`.

    Specified by:
      `size` in interface `Collection<E>`
    Specified by:
      `size` in interface `List<E>`
    Specified by:
      `size` in class `AbstractCollection<E>`
    Returns:
      how many objects this `Collection` contains, or `Integer.MAX_VALUE` if there are more than `Integer.MAX_VALUE` elements in this `Collection`.

  - ### offer

    public boolean offer(E o)
    Description copied from interface: `Queue`

    Inserts the specified element into the queue provided that the condition allows such an operation. The method is generally preferable to `Collection#add`, since the latter might throw an exception if the operation fails.

    ###### Parameters

    - `o`: the specified element to insert into the queue.

    ###### Returns

    Specified by:
      `offer` in interface `Queue<E>`
    Returns:
      `true` if the operation succeeds and `false` if it fails.

  - ### poll

    public E poll()
    Description copied from interface: `Queue`

    Gets and removes the element at the head of the queue, or returns `null` if there is no element in the queue.

    ###### Returns

    Specified by:
      `poll` in interface `Queue<E>`
    Returns:
      the element at the head of the queue or `null` if there is no element in the queue.

  - ### remove

    public E remove()
    Description copied from interface: `Queue`

    Gets and removes the element at the head of the queue. Throws a NoSuchElementException if there is no element in the queue.

    ###### Returns

    the element at the head of the queue.

    ###### Throws

    - `NoSuchElementException`: if there is no element in the queue.
    Specified by:
      `remove` in interface `Queue<E>`

  - ### peek

    public E peek()
    Description copied from interface: `Queue`

    Gets but does not remove the element at the head of the queue.

    ###### Returns

    Specified by:
      `peek` in interface `Queue<E>`
    Returns:
      the element at the head of the queue or `null` if there is no element in the queue.

  - ### element

    public E element()
    Description copied from interface: `Queue`

    Gets but does not remove the element at the head of the queue. Throws a `NoSuchElementException` if there is no element in the queue.

    ###### Returns

    the element at the head of the queue.

    ###### Throws

    - `NoSuchElementException`: if there is no element in the queue.
    Specified by:
      `element` in interface `Queue<E>`

  - ### toArray

    public Object[] toArray()

    Returns a new array containing all elements contained in this `LinkedList`.

    ###### Returns

    an array of the elements from this `LinkedList`.

    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`
    Overrides:
      `toArray` in class `AbstractList<E>`

  - ### toArray

    public <T> T[] toArray(T[] contents)

    Returns an array containing all elements contained in this `LinkedList`. If the specified array is large enough to hold the elements, the specified array is used, otherwise an array of the same type is created. If the specified array is used and is larger than this `LinkedList`, the array element following the collection elements is set to null.

    ###### Parameters

    - `contents`: the array.

    ###### Returns

    an array of the elements from this `LinkedList`.

    ###### Throws

    - `ArrayStoreException`: @throws ArrayStoreException if the type of an element in this `LinkedList` cannot be stored in the type of the specified array.
    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`
    Overrides:
      `toArray` in class `AbstractList<E>`