# 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`
  Modifier and Type
  Field
  Description
  `protected int`
  `modCount`
  A counter for changes to the list.

- ## 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`
  Modifier and Type
  Method
  Description
  `Iterator<E>`
  `iterator()`
  Returns an iterator on the elements of this list.

  ### Methods inherited from class AbstractList

  `equals, hashCode, listIterator, removeRange, subList`
  Modifier and Type
  Method
  Description
  `boolean`
  `equals(Object object)`
  Compares the specified object to this list and return true if they are equal.
  `int`
  `hashCode()`
  Returns the hash code of this list.
  `ListIterator<E>`
  `listIterator()`
  Returns a ListIterator on the elements of this list.
  `protected void`
  `removeRange(int start, int end)`
  Removes the objects in the specified range from the start to the end index minus one.
  `List<E>`
  `subList(int start, int end)`
  Returns a part of consecutive elements of this list as a view.

  ### Methods inherited from class AbstractCollection

  `containsAll, isEmpty, removeAll, retainAll, toString`
  Modifier and Type
  Method
  Description
  `boolean`
  `containsAll(Collection<?> collection)`
  Tests whether this `Collection` contains all objects contained in the specified `Collection`.
  `boolean`
  `isEmpty()`
  Returns if this `Collection` contains no elements.
  `boolean`
  `removeAll(Collection<?> collection)`
  Removes all occurrences in this `Collection` of each object in the specified `Collection` (optional).
  `boolean`
  `retainAll(Collection<?> collection)`
  Removes all objects from this `Collection` that are not also found in the `Collection` passed (optional).
  `String`
  `toString()`
  Returns the string representation of this `Collection`.

  ### Methods inherited from class Object

  `clone, getClass, notify, notifyAll, wait, wait, wait`
  Modifier and Type
  Method
  Description
  `protected Object`
  `clone()`
  `final Class`
  `getClass()`
  Returns the runtime class of an object.
  `final void`
  `notify()`
  Wakes up a single thread that is waiting on this object's monitor.
  `final void`
  `notifyAll()`
  Wakes up all threads that are waiting on this object's monitor.
  `final void`
  `wait()`
  Causes current thread to wait until another thread invokes the method or the method for this object.
  `final void`
  `wait(long timeout)`
  Causes current thread to wait until either another thread invokes the method or the method for this object, or a specified amount of time has elapsed.
  `final void`
  `wait(long timeout, int nanos)`
  Causes current thread to wait until another thread invokes the method or the method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

  ### Methods inherited from interface List

  `containsAll, isEmpty, removeAll, retainAll`
  Modifier and Type
  Method
  Description
  `boolean`
  `containsAll(Collection<?> collection)`
  Tests whether this `List` contains all objects contained in the specified collection.
  `boolean`
  `isEmpty()`
  Returns whether this `List` contains no elements.
  `boolean`
  `removeAll(Collection<?> collection)`
  Removes all occurrences in this `List` of each object in the specified collection.
  `boolean`
  `retainAll(Collection<?> collection)`
  Removes all objects from this `List` that are not contained in the specified collection.

- ## 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.
    Specified by:
      `add` in interface `List<E>`
    Overrides:
      `add` in class `AbstractSequentialList<E>`
    Parameters:
      `location` - the index at which to insert.
      `object` - the object to add.
    Throws:
      `IndexOutOfBoundsException` - if `location < 0 || >= size()`

  - ### add

    public boolean add(E object)
    Adds the specified object at the end of this `LinkedList`.
    Specified by:
      `add` in interface `Collection<E>`
    Specified by:
      `add` in interface `List<E>`
    Overrides:
      `add` in class `AbstractList<E>`
    Parameters:
      `object` - the object to add.
    Returns:
      always true

  - ### 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.
    Specified by:
      `addAll` in interface `List<E>`
    Overrides:
      `addAll` in class `AbstractSequentialList<E>`
    Parameters:
      `location` - the index at which to insert.
      `collection` - the collection of objects
    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 < 0 || > size()`

  - ### addAll

    public boolean addAll(Collection<? extends E> collection)
    Adds the objects in the specified Collection to this `LinkedList`.
    Specified by:
      `addAll` in interface `Collection<E>`
    Specified by:
      `addAll` in interface `List<E>`
    Overrides:
      `addAll` in class `AbstractCollection<E>`
    Parameters:
      `collection` - the collection of objects.
    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`.
    Specified by:
      `addFirst` in interface `Deque<E>`
    Parameters:
      `object` - the object to add.

  - ### addLast

    public void addLast(E object)
    Adds the specified object at the end of this `LinkedList`.
    Specified by:
      `addLast` in interface `Deque<E>`
    Parameters:
      `object` - the object to add.

  - ### clear

    public void clear()
    Removes all elements from this `LinkedList`, leaving it empty.
    Specified by:
      `clear` in interface `Collection<E>`
    Specified by:
      `clear` in interface `List<E>`
    Overrides:
      `clear` in class `AbstractList<E>`
    See Also:
      - `List.isEmpty()`
      - `size`

  - ### contains

    public boolean contains(Object object)
    Searches this `LinkedList` for the specified object.
    Specified by:
      `contains` in interface `Collection<E>`
    Specified by:
      `contains` in interface `List<E>`
    Overrides:
      `contains` in class `AbstractCollection<E>`
    Parameters:
      `object` - the object to search for.
    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.
    Specified by:
      `get` in interface `List<E>`
    Overrides:
      `get` in class `AbstractSequentialList<E>`
    Parameters:
      `location` - the index of the element to return.
    Returns:
      the element at the specified index.

  - ### getFirst

    public E getFirst()
    Returns the first element in this `LinkedList`.
    Specified by:
      `getFirst` in interface `Deque<E>`
    Returns:
      the first element.
    Throws:
      `NoSuchElementException` - if this `LinkedList` is empty.

  - ### getLast

    public E getLast()
    Returns the last element in this `LinkedList`.
    Specified by:
      `getLast` in interface `Deque<E>`
    Returns:
      the last element
    Throws:
      `NoSuchElementException` - if this `LinkedList` is empty

  - ### 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.
    Specified by:
      `indexOf` in interface `List<E>`
    Overrides:
      `indexOf` in class `AbstractList<E>`
    Parameters:
      `object` - the object to search for.
    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.
    Specified by:
      `lastIndexOf` in interface `List<E>`
    Overrides:
      `lastIndexOf` in class `AbstractList<E>`
    Parameters:
      `object` - the object to search for
    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.
    Specified by:
      `listIterator` in interface `List<E>`
    Specified by:
      `listIterator` in class `AbstractSequentialList<E>`
    Parameters:
      `location` - the index at which to start the iteration
    Returns:
      a ListIterator on the elements of this `LinkedList`
    Throws:
      `IndexOutOfBoundsException` - if `location < 0 || >= size()`
    See Also:
      - `ListIterator`

  - ### remove

    public E remove(int location)
    Removes the object at the specified location from this `LinkedList`.
    Specified by:
      `remove` in interface `List<E>`
    Overrides:
      `remove` in class `AbstractSequentialList<E>`
    Parameters:
      `location` - the index of the object to remove
    Returns:
      the removed object
    Throws:
      `IndexOutOfBoundsException` - if `location < 0 || >= size()`

  - ### 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.
    Specified by:
      `remove` in interface `Collection<E>`
    Specified by:
      `remove` in interface `List<E>`
    Overrides:
      `remove` in class `AbstractCollection<E>`
    Parameters:
      `object` - the object to remove.
    Returns:
      `true` if this `Collection` is modified, `false` otherwise.

  - ### removeFirst

    public E removeFirst()
    Removes the first object from this `LinkedList`.
    Specified by:
      `removeFirst` in interface `Deque<E>`
    Returns:
      the removed object.
    Throws:
      `NoSuchElementException` - if this `LinkedList` is empty.

  - ### removeLast

    public E removeLast()
    Removes the last object from this `LinkedList`.
    Specified by:
      `removeLast` in interface `Deque<E>`
    Returns:
      the removed object.
    Throws:
      `NoSuchElementException` - if this `LinkedList` is empty.

  - ### descendingIterator

    public Iterator<E> descendingIterator()
    Returns the iterator in reverse order, from tail to head.
    Specified by:
      `descendingIterator` in interface `Deque<E>`
    Returns:
      the iterator in reverse order
    Since:
      1.6
    See Also:
      - `Deque.descendingIterator()`

  - ### 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.
    Specified by:
      `offerFirst` in interface `Deque<E>`
    Parameters:
      `e` - the element
    Returns:
      true if the operation succeeds or false if it fails.
    Since:
      1.6
    See Also:
      - `Deque.offerFirst(java.lang.Object)`

  - ### 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.
    Specified by:
      `offerLast` in interface `Deque<E>`
    Parameters:
      `e` - the element
    Returns:
      true if the operation succeeds or false if it fails
    Since:
      1.6
    See Also:
      - `Deque.offerLast(java.lang.Object)`

  - ### peekFirst

    public E peekFirst()
    Gets but not removes the head element of this deque. This method returns null if the deque is empty.
    Specified by:
      `peekFirst` in interface `Deque<E>`
    Returns:
      the head element or null if the deque is empty
    Since:
      1.6
    See Also:
      - `Deque.peekFirst()`

  - ### peekLast

    public E peekLast()
    Gets but not removes the tail element of this deque. This method returns null if the deque is empty.
    Specified by:
      `peekLast` in interface `Deque<E>`
    Returns:
      the tail element or null if the deque is empty
    Since:
      1.6
    See Also:
      - `Deque.peekLast()`

  - ### pollFirst

    public E pollFirst()
    Gets and removes the head element of this deque. This method returns null if the deque is empty.
    Specified by:
      `pollFirst` in interface `Deque<E>`
    Returns:
      the head element or null if the deque is empty
    Since:
      1.6
    See Also:
      - `Deque.pollFirst()`

  - ### pollLast

    public E pollLast()
    Gets and removes the tail element of this deque. This method returns null if the deque is empty.
    Specified by:
      `pollLast` in interface `Deque<E>`
    Returns:
      the tail element or null if the deque is empty
    Since:
      1.6
    See Also:
      - `Deque.pollLast()`

  - ### pop

    public E pop()
    Pops the head element of the deque, just same as removeFirst().
    Specified by:
      `pop` in interface `Deque<E>`
    Returns:
      the head element
    Since:
      1.6
    See Also:
      - `Deque.pop()`

  - ### push

    public void push(E e)
    Pushes the element to the deque(at the head of the deque), just same as addFirst(E).
    Specified by:
      `push` in interface `Deque<E>`
    Parameters:
      `e` - the element
    Since:
      1.6
    See Also:
      - `Deque.push(java.lang.Object)`

  - ### 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.
    Specified by:
      `removeFirstOccurrence` in interface `Deque<E>`
    Parameters:
      `o` - the element to be removed
    Returns:
      true if the operation succeeds or false if the deque does not contain the element.
    Since:
      1.6
    See Also:
      - `Deque.removeFirstOccurrence(java.lang.Object)`

  - ### 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.
    Specified by:
      `removeLastOccurrence` in interface `Deque<E>`
    Parameters:
      `o` - the element to be removed
    Returns:
      true if the operation succeeds or false if the deque does not contain the element.
    Since:
      1.6
    See Also:
      - `Deque.removeLastOccurrence(java.lang.Object)`

  - ### set

    public E set(int location, E object)
    Replaces the element at the specified location in this `LinkedList` with the specified object.
    Specified by:
      `set` in interface `List<E>`
    Overrides:
      `set` in class `AbstractSequentialList<E>`
    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 < 0 || >= size()`

  - ### size

    public int size()
    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:
      the number of elements in this `LinkedList`.

  - ### 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(E)`, since the latter might throw an exception if the operation fails.
    Specified by:
      `offer` in interface `Queue<E>`
    Parameters:
      `o` - the specified element to insert into the queue.
    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.
    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.
    Specified by:
      `remove` in interface `Queue<E>`
    Returns:
      the element at the head of the queue.

  - ### peek

    public E peek()
    Description copied from interface: `Queue`
    Gets but does not remove the element at the head of the queue.
    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.
    Specified by:
      `element` in interface `Queue<E>`
    Returns:
      the element at the head of the queue.

  - ### toArray

    public Object[] toArray()
    Returns a new array containing all elements contained in this `LinkedList`.
    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`
    Overrides:
      `toArray` in class `AbstractList<E>`
    Returns:
      an array of the elements from this `LinkedList`.

  - ### 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.
    Specified by:
      `toArray` in interface `Collection<E>`
    Specified by:
      `toArray` in interface `List<E>`
    Overrides:
      `toArray` in class `AbstractList<E>`
    Parameters:
      `contents` - the array.
    Returns:
      an array of the elements from this `LinkedList`.
    Throws:
      `ArrayStoreException` - if the type of an element in this `LinkedList` cannot be stored in the type of the specified array.