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 List

    containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, retainAll, 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>