Module  java.base
Software package  java.util

Class LinkedList<E>

  • Parameter Type
    E- the type of elements held in this collection
    All implemented interfaces
    Serializable ， Cloneable ， Iterable<E> ， Collection<E> ， Deque<E> ， List<E> ， Queue<E> 
    public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable
    The doubly linked list implementsListandDequeInterface. Implements all optional list operations, and permits all elements (includingnull ）。

    For a doubly linked list, all operations are predictable. An operation that indexes into a list will traverse the list from the beginning or the end, whichever is closer to the specified index.

    Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, thenRequiredSynchronize externally. （StructuremodifyYesaddorDeleteaor multipleelement'sanyOperation;onlySettingselement'sThe value is notStructuremodify。）这通常Throughsame步自butEncapsulationListof某itemsObjectto complete. If such an object does not exist, you should useCollections.synchronizedListThe method “wraps” the list. This is best done at creation time, to prevent accidental unsynchronized access to the list: 

      List list = Collections.synchronizedList(new LinkedList(...));

    This type ofiteratorandlistIteratorThe iterator returned by the method isfail-fast: If the list is structurally modified at any time after the iterator is created, except through the Iterator's ownremoveoraddExcept through the method, the iterator will throwConcurrentModificationException 。 Therefore, in the case of concurrent modification, the iterator fails fast and cleanly, rather than risking arbitrary, non-deterministic behavior at an unspecified time in the future.

    Please note that the fail-fast behavior of iterators cannot be guaranteed, because in general, it is impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw on a best-effort basisConcurrentModificationException 。 Therefore, it is incorrect to write programs that depend on this exception to ensure their correctness:The fail-fast behavior of an iterator should be used only to detect bugs.

    This type isJava Collections Frameworkthe member.

    Starting from the following version:
    1.2
    See also:
    List ， ArrayList ， Serialized Form

    • Constructor Summary

      Constructor  
      Constructor Description
      LinkedList()
      Construct an empty list.
      LinkedList​(Collection<? extends E> c)
      Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

    • Method Summary

      All methods  Instance Methods Specific Methods 
      Variables and types Methods Description
      void add​(int index, E element)
      Inserts the specified element at the specified position in this list.
      boolean add​(E e)
      Appends the specified element to the end of this list.
      boolean addAll​(int index, Collection<? extends E> c)
      Inserts all elements from the specified collection into this list, starting at the specified position.
      boolean addAll​(Collection<? extends E> c)
      Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
      void addFirst​(E e)
      Inserts the specified element at the beginning of this list.
      void addLast​(E e)
      Appends the specified element to the end of this list.
      void clear()
      Remove all elements from this list.
      Object clone()
      Return thisLinkedListshallow copy of.
      boolean contains​(Object o)
      If this list contains the specified element, then returns.true 。
      Iterator<E> descendingIterator()
      Returns an iterator over the elements in this deque in reverse order.
      E element()
      Retrieves, but does not remove, the head (first element) of this list.
      E get​(int index)
      Returns the element at the specified position in this list.
      E getFirst()
      Returns the first element of this list.
      E getLast()
      Returns the last element in this list.
      int indexOf​(Object o)
      Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
      int lastIndexOf​(Object o)
      Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
      ListIterator<E> listIterator​(int index)
      Returns a list iterator over the elements in this list, starting at the specified position in the list (in proper sequence).
      boolean offer​(E e)
      Adds the specified element to the tail (last element) of this list.
      boolean offerFirst​(E e)
      Inserts the specified element at the front of this list.
      boolean offerLast​(E e)
      Inserts the specified element at the end of this list.
      E peek()
      Retrieves, but does not remove, the head (first element) of this list.
      E peekFirst()
      Retrieves, but does not remove, the first element of this list, or returns if this list is empty.null 。
      E peekLast()
      Retrieves but does not remove the last element of this list, or returns null if this list is empty.null 。
      E poll()
      Retrieve and remove the head (first element) of this list.
      E pollFirst()
      Retrieves and removes the first element of this list; if this list is empty, returns.null 。
      E pollLast()
      Retrieves and removes the last element of this list, or returns if this list is empty.null 。
      E pop()
      Pops an element from the stack represented by this list.
      void push​(E e)
      Pushes an element onto the stack represented by this list.
      E remove()
      Retrieve and remove the head (first element) of this list.
      E remove​(int index)
      Removes the element at the specified position in this list.
      boolean remove​(Object o)
      Removes the first occurrence of the specified element from this list, if it is present.
      E removeFirst()
      Removes and returns the first element from this list.
      boolean removeFirstOccurrence​(Object o)
      Removes the first occurrence of the specified element from this list (when traversing the list from head to tail).
      E removeLast()
      Removes and returns the last element from this list.
      boolean removeLastOccurrence​(Object o)
      Removes the last occurrence of the specified element from this list (when traversing the list from head to tail).
      E set​(int index, E element)
      Replaces the element at the specified position in this list with the specified element.
      int size()
      Returns the number of elements in this list.
      Spliterator<E> spliterator()
      Created over the elements in this listlate-bindingandFail-fast Spliterator 。
      Object[] toArray()
      Returns an array containing all elements in this list in proper order (from the first element to the last element).
      <T> T[] toArray​(T[] a)
      Returns an array containing all elements in this list in proper order (from the first element to the last element); The runtime type of the returned array is the runtime type of the specified array.

    • Constructor Details

      • LinkedList

        public LinkedList()
        Construct an empty list.

      • LinkedList

        public LinkedList​(Collection<? extends E> c)
        Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
        Parameter
        c - cthe collection whose elements are to be placed into this list
        Exception
        NullPointerException- if the specified collection is null

    • Method Details

      • getFirst

        public E getFirst()
        Returns the first element of this list.
        Specified by:
        getFirstIn the interfaceDeque<E>
        Result
        the first element in this list
        Exception
        NoSuchElementException- if this list is empty

      • getLast

        public E getLast()
        Returns the last element in this list.
        Specified by:
        getLastIn the interfaceDeque<E>
        Result
        the last element in this list
        Exception
        NoSuchElementException- if this list is empty

      • removeFirst

        public E removeFirst()
        Removes and returns the first element from this list.
        Specified by:
        removeFirst in interface Deque<E>
        Result
        the first element in this list
        Exception
        NoSuchElementException- if this list is empty

      • removeLast

        public E removeLast()
        Removes and returns the last element from this list.
        Specified by:
        removeLastIn the interfaceDeque<E>
        Result
        the last element in this list
        Exception
        NoSuchElementException- if this list is empty

      • addFirst

        public void addFirst​(E e)
        Inserts the specified element at the beginning of this list.
        Specified by:
        addFirst in interface Deque<E>
        Parameter
        e- the element to add

      • addLast

        public void addLast​(E e)
        Appends the specified element to the end of this list.

        This method is equivalent toadd(E) 。

        Specified by:
        addLastinterfaceDeque<E>
        Parameter
        e- the element to add

      • contains

        public boolean contains​(Object o)
        If this list contains the specified element, then returns.true 。 More formally, returntrueIf and only if this list contains at least one elemente, makingObjects.equals(o, e) 。
        Specified by:
        contains in interface Collection<E>
        Specified by:
        containsIn the interfaceDeque<E>
        Specified by:
        containsIn the interfaceList<E>
        Override:
        containsClassAbstractCollection<E>
        Parameter
        o- the element whose presence in this list is to be tested
        Result
        truetrue if this list contains the specified element

      • size

        public int size()
        Returns the number of elements in this list.
        Specified by:
        sizeIn the interfaceCollection<E>
        Specified by:
        sizeIn the interfaceDeque<E>
        Specified by:
        sizeIn the interfaceList<E>
        Result
        the number of elements in this list

      • add

        public boolean add​(E e)
        Appends the specified element to the end of this list.

        This method is equivalent toaddLast(E) 。

        Specified by:
        add in interface Collection<E>
        Specified by:
        addIn the interfaceDeque<E>
        Specified by:
        addIn the interfaceList<E>
        Specified by:
        addIn the interfaceQueue<E>
        Override:
        addIn classAbstractList<E>
        Parameter
        e- the element to be appended to this list
        Result
        true(byCollection.add(E)specified)

      • remove

        public boolean remove​(Object o)
        Removes the first occurrence of the specified element from this list, if it is present. If this list does not contain the element, it will not be changed. More formally, removes the element with the lowest indexithe elements of, such thatObjects.equals(o, get(i))(if such elements exist). If this list contains the specified element, then returns.true(or equivalently, if this list is changed by the call).
        Specified by:
        removeIn the interfaceCollection<E>
        Specified by:
        removeIn the interfaceDeque<E>
        Specified by:
        removeIn the interfaceList<E>
        Override:
        removeIn classAbstractCollection<E>
        Parameter
        o- The element to be removed from this list, if present
        Result
        truetrue if this list contains the specified element

      • addAll

        public boolean addAll​(Collection<? extends E> c)
        Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator. If the specified collection is modified while the operation is in progress, the behavior of this operation is undefined. (Note that this will happen if the specified collection is this list, and it is non-empty.)
        Specified by:
        addAllIn the interfaceCollection<E>
        Specified by:
        addAllIn the interfaceDeque<E>
        Specified by:
        addAllIn the interfaceList<E>
        Override:
        addAllIn classAbstractCollection<E>
        Parameter
        c- The collection containing elements to be added to this list
        Result
        truetrue if this list changed as a result of the call
        Exception
        NullPointerException- if the specified collection is null
        See also:
        AbstractCollection.add(Object)

      • addAll

        public boolean addAll​(int index,
                      Collection<? extends E> c)
        Inserts all elements from the specified collection into this list, starting at the specified position. Shifts the element at the current position (if any) and any subsequent elements to the right (increasing their indices). The new elements will appear in the list in the order returned by the specified collection's iterator.
        Specified by:
        addAll in interface List<E>
        Override:
        addAllIn classAbstractSequentialList<E>
        Parameter
        index- The index at which to insert the first element from the specified collection
        c- The collection containing elements to be added to this list
        Result
        truetrue if this list changed as a result of the call
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index > size() ）
        NullPointerException- if the specified collection is null

      • clear

        public void clear()
        Remove all elements from this list. After this call returns, the list will be empty.
        Specified by:
        clearIn the interfaceCollection<E>
        Specified by:
        clearIn the interfaceList<E>
        Override:
        clearClassAbstractList<E>

      • get

        public E get​(int index)
        Returns the element at the specified position in this list.
        Specified by:
        get in interface List<E>
        Override:
        getClassAbstractSequentialList<E>
        Parameter
        index- the index of the element to return
        Result
        the element at the specified position in this list
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index >= size() ）

      • set

        public E set​(int index,
             E element)
        Replaces the element at the specified position in this list with the specified element.
        Specified by:
        set in interface List<E>
        Override:
        setIn classAbstractSequentialList<E>
        Parameter
        index- the index of the element to replace
        element- the element to be stored at the specified position
        Result
        the element previously at the specified position
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index >= size() ）

      • add

        public void add​(int index,
                E element)
        Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
        Specified by:
        addIn the interfaceList<E>
        Override:
        addClassAbstractSequentialList<E>
        Parameter
        index- the index at which the specified element is to be inserted
        element- the element to be inserted
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index > size() ）

      • remove

        public E remove​(int index)
        Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the elements removed from the list.
        Specified by:
        removeIn the interfaceList<E>
        Override:
        removeIn classAbstractSequentialList<E>
        Parameter
        index- the index of the element to be removed
        Result
        the element previously at the specified position
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index >= size() ）

      • indexOf

        public int indexOf​(Object o)
        Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the lowest indexiFor exampleObjects.equals(o, get(i)), or -1 if there is no such index.
        Specified by:
        indexOfIn the interfaceList<E>
        Override:
        indexOfIn classAbstractList<E>
        Parameter
        o- The element to search for
        Result
        The index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element

      • lastIndexOf

        public int lastIndexOf​(Object o)
        Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element. More formally, returns the highest index.iFor exampleObjects.equals(o, get(i)), or -1 if there is no such index.
        Specified by:
        lastIndexOfIn the interfaceList<E>
        Override:
        lastIndexOfIn classAbstractList<E>
        Parameter
        o- The element to search for
        Result
        The index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element

      • peek

        public E peek()
        Retrieves, but does not remove, the head (first element) of this list.
        Specified by:
        peekIn the interfaceDeque<E>
        Specified by:
        peekIn the interfaceQueue<E>
        Result
        The head of this list, if this list is empty,null
        Starting from the following version:
        1.5

      • element

        public E element()
        Retrieves, but does not remove, the head (first element) of this list.
        Specified by:
        elementIn the interfaceDeque<E>
        Specified by:
        elementIn the interfaceQueue<E>
        Result
        the head of this list
        Exception
        NoSuchElementException- if this list is empty
        Starting from the following version:
        1.5

      • poll

        public E poll()
        Retrieve and remove the head (first element) of this list.
        Specified by:
        pollIn the interfaceDeque<E>
        Specified by:
        poll in interface Queue<E>
        Result
        The head of this list, if this list is empty,null
        Starting from the following version:
        1.5

      • remove

        public E remove()
        Retrieve and remove the head (first element) of this list.
        Specified by:
        removeIn the interfaceDeque<E>
        Specified by:
        removeIn the interfaceQueue<E>
        Result
        the head of this list
        Exception
        NoSuchElementException- if this list is empty
        Starting from the following version:
        1.5

      • offer

        public boolean offer​(E e)
        Adds the specified element to the tail (last element) of this list.
        Specified by:
        offerIn the interfaceDeque<E>
        Specified by:
        offerIn the interfaceQueue<E>
        Parameter
        e- the element to add
        Result
        true(byQueue.offer(E)specified)
        Starting from the following version:
        1.5

      • offerFirst

        public boolean offerFirst​(E e)
        Inserts the specified element at the front of this list.
        Specified by:
        offerFirstIn the interfaceDeque<E>
        Parameter
        e- the element to be inserted
        Result
        true(byDeque.offerFirst(E)specified)
        Starting from the following version:
        1.6

      • offerLast

        public boolean offerLast​(E e)
        Inserts the specified element at the end of this list.
        Specified by:
        offerLastIn the interfaceDeque<E>
        Parameter
        e- the element to be inserted
        Result
        true(byDeque.offerLast(E)specified)
        Starting from the following version:
        1.6

      • peekFirst

        public E peekFirst()
        Retrieves, but does not remove, the first element of this list, or returns if this list is empty.null 。
        Specified by:
        peekFirstIn the interfaceDeque<E>
        Result
        The first element of this list, if this list is empty,null
        Starting from the following version:
        1.6

      • peekLast

        public E peekLast()
        Retrieves but does not remove the last element of this list, or returns null if this list is empty.null 。
        Specified by:
        peekLastIn the interfaceDeque<E>
        Result
        The last element of this list, if this list is empty,null
        Starting from the following version:
        1.6

      • pollFirst

        public E pollFirst()
        Retrieves and removes the first element of this list; if this list is empty, returns.null 。
        Specified by:
        pollFirstIn the interfaceDeque<E>
        Result
        The first element of this list, if this list is empty,null
        Starting from the following version:
        1.6

      • pollLast

        public E pollLast()
        Retrieves and removes the last element of this list, or returns if this list is empty.null 。
        Specified by:
        pollLastIn the interfaceDeque<E>
        Result
        The last element of this list, if this list is empty,null
        Starting from the following version:
        1.6

      • push

        public void push​(E e)
        Pushes an element onto the stack represented by this list. In other words, inserts the element at the front of this list.

        This method is equivalent toaddFirst(E) 。

        Specified by:
        pushIn the interfaceDeque<E>
        Parameter
        e- the element to be pushed
        Starting from the following version:
        1.6

      • pop

        public E pop()
        Pops an element from the stack represented by this list. In other words, removes and returns the first element of this list.

        This method is equivalent toremoveFirst() 。

        Specified by:
        popIn the interfaceDeque<E>
        Result
        the head of this list (the top of the stack represented by this list)
        Exception
        NoSuchElementException- if this list is empty
        Starting from the following version:
        1.6

      • removeFirstOccurrence

        public boolean removeFirstOccurrence​(Object o)
        Removes the first occurrence of the specified element from this list (when traversing the list from head to tail). If the list does not contain the element, it is unchanged.
        Specified by:
        removeFirstOccurrenceIn the interfaceDeque<E>
        Parameter
        o- The element to be removed from this list, if present
        Result
        truetrue if the list contains the specified element
        Starting from the following version:
        1.6

      • removeLastOccurrence

        public boolean removeLastOccurrence​(Object o)
        Removes the last occurrence of the specified element from this list (when traversing the list from head to tail). If the list does not contain the element, it is unchanged.
        Specified by:
        removeLastOccurrenceIn the interfaceDeque<E>
        Parameter
        o- The element to be removed from this list, if present
        Result
        truetrue if the list contains the specified element
        Starting from the following version:
        1.6

      • listIterator

        public ListIterator<E> listIterator​(int index)
        Returns a list iterator over the elements in this list, starting at the specified position in the list (in proper sequence). List.listIterator(int)the total contract isList.listIterator(int) 。

        The list-iterator isfail-fast: If the list is structurally modified at any time after the Iterator is created, except through the list-iterator's ownremoveoraddOther than the methods, the list-iterator will throwConcurrentModificationException 。 Therefore, in the case of concurrent modification, the iterator fails fast and cleanly, rather than risking arbitrary, non-deterministic behavior at an unspecified time in the future.

        Specified by:
        listIteratorIn the interfaceList<E>
        Specified by:
        listIteratorIn classAbstractSequentialList<E>
        Parameter
        index- The index of the first element to be returned from the list-iterator (by callingnext ）
        Result
        A ListIterator of the elements in this list (in proper sequence), starting at the specified position in the list
        Exception
        IndexOutOfBoundsException- if the index is out of range (index < 0 || index > size() ）
        See also:
        List.listIterator(int)

      • descendingIterator

        public Iterator<E> descendingIterator()
        Instructions copied from the interface:Deque
        Returns an iterator over the elements in this deque in reverse order. The elements will be returned in order from last (tail) to first (head).
        Specified by:
        descendingIteratorIn the interfaceDeque<E>
        Result
        An iterator over the elements in this deque in reverse sequential order
        Starting from the following version:
        1.6

      • clone

        public Object clone()
        Return thisLinkedListshallow copy of. (The elements themselves are not cloned.)
        Override:
        cloneClassObject
        Result
        ThisLinkedListA shallow copy of the instance
        See also:
        Cloneable

      • toArray

        public Object[] toArray()
        Returns an array containing all elements in this list in proper order (from the first element to the last element).

        The returned array will be "safe" because this list does not retain references to it. (In other words, this method must allocate a new array). Thus the caller is free to modify the returned array.

        This method acts as a bridge between array-based and collection-based APIs.

        Specified by:
        toArrayIn the interfaceCollection<E>
        Specified by:
        toArrayIn the interfaceList<E>
        Override:
        toArrayIn classAbstractCollection<E>
        Result
        An array containing all of the elements in this list in proper sequence
        See also:
        Arrays.asList(Object[])

      • toArray

        public <T> T[] toArray​(T[] a)
        Returns an array containing all elements in this list in proper order (from the first element to the last element); The runtime type of the returned array is the runtime type of the specified array. If the list fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this list.

        If the list fits into the specified array, and there is spare space (i.e., the array has more elements than the list), then the elements in the array immediately following the end of the list are set tonull 。 （ onlyWhen the caller knows that the list does not contain any null elements, this is useful in determining the length of the list.)

        andtoArray()Like the method, this method acts as a bridge between array-based and collection-based APIs. In addition, this method allows precise control over the runtime type of the output array and, in some cases, can be used to save allocation costs.

        Supposexis a list known to contain only strings. The following code can be used to dump the list into a newly allocated arrayStringin the array: 

          String[] y = x.toArray(new String[0]);
        Please note,toArray(new Object[0])Function andtoArray() 。
        Specified by:
        toArrayIn the interfaceCollection<E>
        Specified by:
        toArrayIn the interfaceList<E>
        Override:
        toArrayIn classAbstractCollection<E>
        Parameter Type
        T- the component type of the array to contain the collection
        Parameter
        a- the array in which the elements of the list are to be stored, if it is large enough; Otherwise, a new array of the same runtime type is allocated for this purpose.
        Result
        an array containing the elements of this list
        Exception
        ArrayStoreException- if the runtime type of the specified array is not a supertype of the runtime type of every element in this list
        NullPointerException- if the specified array is null