Module  java.base
软件包  java.util

Class LinkedList<E>

  • 参数类型
    E - 此集合中保存的元素的类型
    All Implemented Interfaces:
    SerializableCloneableIterable<E>Collection<E>Deque<E>List<E>Queue<E>


    public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable
    双链表实现了ListDeque接口。 实现所有可选列表操作,并允许所有元素(包括null )。

    所有的操作都能像双向列表一样预期。 索引到列表中的操作将从开始或结束遍历列表,以更接近指定的索引为准。

    请注意,此实现不同步。 如果多个线程同时访问链接列表,并且至少有一个线程在结构上修改列表,则必须在外部进行同步。 (结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这通常通过在自然封装列表的对象上进行同步来实现。 如果没有这样的对象存在,列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成,以防止意外的不同步访问列表:

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

    该类的iteratorlistIterator方法返回的迭代器是故障快速的 :如果列表在迭代器创建后的任何时间进行结构修改,除了通过Iterator自己的removeadd方法外,迭代器将抛出一个ConcurrentModificationException 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。

    请注意,迭代器的故障快速行为无法保证,因为一般来说,在不同步并发修改的情况下,无法做出任何硬性保证。 失败快速的迭代器ConcurrentModificationException扔掉ConcurrentModificationException 因此,编写依赖于此异常的程序的正确性将是错误的: 迭代器的故障快速行为应仅用于检测错误。

    这个类是Java Collections Framework的成员。

    从以下版本开始:
    1.2
    另请参见:
    ListArrayListSerialized Form
    • 构造方法摘要

      构造方法  
      Constructor 描述
      LinkedList​()
      构造一个空列表。
      LinkedList​(Collection<? extends E> c)
      构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。
    • 方法摘要

      所有方法  接口方法  具体的方法 
      Modifier and Type 方法 描述
      void add​(int index, E element)
      在此列表中的指定位置插入指定的元素。
      boolean add​(E e)
      将指定的元素追加到此列表的末尾。
      boolean addAll​(int index, Collection<? extends E> c)
      将指定集合中的所有元素插入到此列表中,从指定的位置开始。
      boolean addAll​(Collection<? extends E> c)
      按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。
      void addFirst​(E e)
      在该列表开头插入指定的元素。
      void addLast​(E e)
      将指定的元素追加到此列表的末尾。
      void clear​()
      从列表中删除所有元素。
      Object clone​()
      返回此 LinkedList的浅拷贝。
      boolean contains​(Object o)
      如果此列表包含指定的元素,则返回 true
      Iterator<E> descendingIterator​()
      以相反的顺序返回此deque中的元素的迭代器。
      E element​()
      检索但不删除此列表的头(第一个元素)。
      E get​(int index)
      返回此列表中指定位置的元素。
      E getFirst​()
      返回此列表中的第一个元素。
      E getLast​()
      返回此列表中的最后一个元素。
      int indexOf​(Object o)
      返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1。
      int lastIndexOf​(Object o)
      返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。
      ListIterator<E> listIterator​(int index)
      从列表中的指定位置开始,返回此列表中元素的列表迭代器(按适当的顺序)。
      boolean offer​(E e)
      将指定的元素添加为此列表的尾部(最后一个元素)。
      boolean offerFirst​(E e)
      在此列表的前面插入指定的元素。
      boolean offerLast​(E e)
      在该列表的末尾插入指定的元素。
      E peek​()
      检索但不删除此列表的头(第一个元素)。
      E peekFirst​()
      检索但不删除此列表的第一个元素,如果此列表为空,则返回 null
      E peekLast​()
      检索但不删除此列表的最后一个元素,如果此列表为空,则返回 null
      E poll​()
      检索并删除此列表的头(第一个元素)。
      E pollFirst​()
      检索并删除此列表的第一个元素,如果此列表为空,则返回 null
      E pollLast​()
      检索并删除此列表的最后一个元素,如果此列表为空,则返回 null
      E pop​()
      从此列表表示的堆栈中弹出一个元素。
      void push​(E e)
      将元素推送到由此列表表示的堆栈上。
      E remove​()
      检索并删除此列表的头(第一个元素)。
      E remove​(int index)
      删除该列表中指定位置的元素。
      boolean remove​(Object o)
      从列表中删除指定元素的第一个出现(如果存在)。
      E removeFirst​()
      从此列表中删除并返回第一个元素。
      boolean removeFirstOccurrence​(Object o)
      删除此列表中指定元素的第一个出现(从头到尾遍历列表时)。
      E removeLast​()
      从此列表中删除并返回最后一个元素。
      boolean removeLastOccurrence​(Object o)
      删除此列表中指定元素的最后一次出现(从头到尾遍历列表时)。
      E set​(int index, E element)
      用指定的元素替换此列表中指定位置的元素。
      int size​()
      返回此列表中的元素数。
      Spliterator<E> spliterator​()
      在此列表中的元素上创建late-binding故障快速 Spliterator
      Object[] toArray​()
      以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组。
      <T> T[] toArray​(T[] a)
      以正确的顺序返回一个包含此列表中所有元素的数组(从第一个到最后一个元素); 返回的数组的运行时类型是指定数组的运行时类型。
    • 构造方法详细信息

      • LinkedList

        public LinkedList​()
        构造一个空列表。
      • LinkedList

        public LinkedList​(Collection<? extends E> c)
        构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。
        参数
        c - c元素放入此列表的集合
        异常
        NullPointerException - 如果指定的集合为空
    • 方法详细信息

      • getFirst

        public E getFirst​()
        返回此列表中的第一个元素。
        Specified by:
        getFirst在接口 Deque<E>
        结果
        这个列表中的第一个元素
        异常
        NoSuchElementException - 如果此列表为空
      • getLast

        public E getLast​()
        返回此列表中的最后一个元素。
        Specified by:
        getLast在接口 Deque<E>
        结果
        这个列表中的最后一个元素
        异常
        NoSuchElementException - 如果此列表为空
      • removeFirst

        public E removeFirst​()
        从此列表中删除并返回第一个元素。
        Specified by:
        removeFirst在接口 Deque<E>
        结果
        这个列表中的第一个元素
        异常
        NoSuchElementException - 如果此列表为空
      • removeLast

        public E removeLast​()
        从此列表中删除并返回最后一个元素。
        Specified by:
        removeLast在接口 Deque<E>
        结果
        这个列表中的最后一个元素
        异常
        NoSuchElementException - 如果此列表为空
      • addFirst

        public void addFirst​(E e)
        在该列表开头插入指定的元素。
        Specified by:
        addFirst在接口 Deque<E>
        参数
        e - 要添加的元素
      • addLast

        public void addLast​(E e)
        将指定的元素追加到此列表的末尾。

        此方法相当于add(E)

        Specified by:
        addLast在接口 Deque<E>
        参数
        e - 要添加的元素
      • contains

        public boolean contains​(Object o)
        如果此列表包含指定的元素,则返回true 更正式地说,返回true当且仅当此列表包含至少一个元素e这样Objects.equals(o, e)
        Specified by:
        contains在接口 Collection<E>
        Specified by:
        contains在接口 Deque<E>
        Specified by:
        contains在接口 List<E>
        重写:
        containsAbstractCollection<E>
        参数
        o - 要在此列表中存在的元素要进行测试
        结果
        true如果此列表包含指定的元素
      • remove

        public boolean remove​(Object o)
        从列表中删除指定元素的第一个出现(如果存在)。 如果此列表不包含该元素,则它将保持不变。 更正式地,删除具有最低索引i的元素,使得Objects.equals(o, get(i)) (如果这样的元素存在)。 如果此列表包含指定的元素(或等效地,如果此列表作为调用的结果而更改),则返回true
        Specified by:
        remove接口 Collection<E>
        Specified by:
        remove在接口 Deque<E>
        Specified by:
        remove在接口 List<E>
        重写:
        removeAbstractCollection<E>
        参数
        o - 要从此列表中删除的元素(如果存在)
        结果
        true如果此列表包含指定的元素
      • addAll

        public boolean addAll​(Collection<? extends E> c)
        按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。 如果在操作进行中修改了指定的集合,则此操作的行为是未定义的。 (注意,如果指定的集合是此列表,并且它是非空的,则会发生这种情况。)
        Specified by:
        addAll在接口 Collection<E>
        Specified by:
        addAll在接口 Deque<E>
        Specified by:
        addAll在接口 List<E>
        重写:
        addAllAbstractCollection<E>
        参数
        c - 包含要添加到此列表的元素的集合
        结果
        true如果此列表因呼叫而更改
        异常
        NullPointerException - 如果指定的集合为空
        另请参见:
        AbstractCollection.add(Object)
      • addAll

        public boolean addAll​(int index,
                              Collection<? extends E> c)
        将指定集合中的所有元素插入到此列表中,从指定的位置开始。 将当前位于该位置(如果有的话)的元素和随后的任何元素移动到右边(增加其索引)。 新元素将按照指定集合的迭代器返回的顺序显示在列表中。
        Specified by:
        addAll在接口 List<E>
        重写:
        addAllAbstractSequentialList<E>
        参数
        index - 从中指定集合插入第一个元素的索引
        c - 包含要添加到此列表的元素的集合
        结果
        true如果此列表因呼叫而更改
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index > size()
        NullPointerException - 如果指定的集合为空
      • clear

        public void clear​()
        从列表中删除所有元素。 此呼叫返回后,列表将为空。
        Specified by:
        clear在接口 Collection<E>
        Specified by:
        clear在接口 List<E>
        重写:
        clearAbstractList<E>
      • get

        public E get​(int index)
        返回此列表中指定位置的元素。
        Specified by:
        get在接口 List<E>
        重写:
        getAbstractSequentialList<E>
        参数
        index - 要返回的元素的索引
        结果
        该列表中指定位置的元素
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index >= size()
      • set

        public E set​(int index,
                     E element)
        用指定的元素替换此列表中指定位置的元素。
        Specified by:
        set在接口 List<E>
        重写:
        setAbstractSequentialList<E>
        参数
        index - 要替换的元素的索引
        element - 要存储在指定位置的元素
        结果
        该元素以前在指定的位置
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index >= size()
      • add

        public void add​(int index,
                        E element)
        在此列表中的指定位置插入指定的元素。 将当前位于该位置的元素(如果有)和任何后续元素(向其索引添加一个)移动。
        Specified by:
        add在接口 List<E>
        重写:
        addAbstractSequentialList<E>
        参数
        index - 要在其中插入指定元素的索引
        element - 要插入的元素
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index > size()
      • remove

        public E remove​(int index)
        删除该列表中指定位置的元素。 将任何后续元素移动到左侧(从其索引中减去一个元素)。 返回从列表中删除的元素。
        Specified by:
        remove在接口 List<E>
        重写:
        removeAbstractSequentialList<E>
        参数
        index - 要删除的元素的索引
        结果
        该元素以前在指定的位置
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index >= size()
      • indexOf

        public int indexOf​(Object o)
        返回此列表中指定元素的第一次出现的索引,如果此列表不包含元素,则返回-1。 更正式地,返回最低指数i ,使得Objects.equals(o, get(i)) ,或-1如果没有这样的索引。
        Specified by:
        indexOf在接口 List<E>
        重写:
        indexOfAbstractList<E>
        参数
        o - 要搜索的元素
        结果
        此列表中指定元素的首次出现的索引,如果此列表不包含元素,则为-1
      • lastIndexOf

        public int lastIndexOf​(Object o)
        返回此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则返回-1。 更正式地说,返回满足i这样Objects.equals(o, get(i)) ,或-1,如果没有这样的指标。
        Specified by:
        lastIndexOf在接口 List<E>
        重写:
        lastIndexOfAbstractList<E>
        参数
        o - 要搜索的元素
        结果
        此列表中指定元素的最后一次出现的索引,如果此列表不包含元素,则为-1
      • peek

        public E peek​()
        检索但不删除此列表的头(第一个元素)。
        Specified by:
        peek在接口 Deque<E>
        Specified by:
        peek在接口 Queue<E>
        结果
        该列表的头,或 null如果此列表为空
        从以下版本开始:
        1.5
      • element

        public E element​()
        检索但不删除此列表的头(第一个元素)。
        Specified by:
        element在接口 Deque<E>
        Specified by:
        element在接口 Queue<E>
        结果
        这个名单的头
        异常
        NoSuchElementException - 如果此列表为空
        从以下版本开始:
        1.5
      • poll

        public E poll​()
        检索并删除此列表的头(第一个元素)。
        Specified by:
        poll在接口 Deque<E>
        Specified by:
        poll在接口 Queue<E>
        结果
        该列表的头,或 null如果此列表为空
        从以下版本开始:
        1.5
      • remove

        public E remove​()
        检索并删除此列表的头(第一个元素)。
        Specified by:
        remove在接口 Deque<E>
        Specified by:
        remove在接口 Queue<E>
        结果
        这个名单的头
        异常
        NoSuchElementException - 如果此列表为空
        从以下版本开始:
        1.5
      • offer

        public boolean offer​(E e)
        将指定的元素添加为此列表的尾部(最后一个元素)。
        Specified by:
        offer在接口 Deque<E>
        Specified by:
        offer在接口 Queue<E>
        参数
        e - 要添加的元素
        结果
        true (由 Queue.offer(E)指定)
        从以下版本开始:
        1.5
      • offerFirst

        public boolean offerFirst​(E e)
        在此列表的前面插入指定的元素。
        Specified by:
        offerFirst在接口 Deque<E>
        参数
        e - 要插入的元素
        结果
        true (由 Deque.offerFirst(E)指定)
        从以下版本开始:
        1.6
      • offerLast

        public boolean offerLast​(E e)
        在该列表的末尾插入指定的元素。
        Specified by:
        offerLast在接口 Deque<E>
        参数
        e - 要插入的元素
        结果
        true (由 Deque.offerLast(E)指定)
        从以下版本开始:
        1.6
      • peekFirst

        public E peekFirst​()
        检索但不删除此列表的第一个元素,如果此列表为空,则返回 null
        Specified by:
        peekFirst在接口 Deque<E>
        结果
        该列表的第一个元素,如果此列表为空, null
        从以下版本开始:
        1.6
      • peekLast

        public E peekLast​()
        检索但不删除此列表的最后一个元素,如果此列表为空,则返回 null
        Specified by:
        peekLast在接口 Deque<E>
        结果
        该列表的最后一个元素,如果此列表为空, null
        从以下版本开始:
        1.6
      • pollFirst

        public E pollFirst​()
        检索并删除此列表的第一个元素,如果此列表为空,则返回 null
        Specified by:
        pollFirst在接口 Deque<E>
        结果
        该列表的第一个元素,如果此列表为空, null
        从以下版本开始:
        1.6
      • pollLast

        public E pollLast​()
        检索并删除此列表的最后一个元素,如果此列表为空,则返回 null
        Specified by:
        pollLast在接口 Deque<E>
        结果
        该列表的最后一个元素,如果此列表为空, null
        从以下版本开始:
        1.6
      • push

        public void push​(E e)
        将元素推送到由此列表表示的堆栈上。 换句话说,在该列表的前面插入元素。

        此方法相当于addFirst(E)

        Specified by:
        push在接口 Deque<E>
        参数
        e - 要推的元素
        从以下版本开始:
        1.6
      • pop

        public E pop​()
        从此列表表示的堆栈中弹出一个元素。 换句话说,删除并返回此列表的第一个元素。

        此方法相当于removeFirst()

        Specified by:
        pop在接口 Deque<E>
        结果
        该列表前面的元素(由此列表表示的堆栈的顶部)
        异常
        NoSuchElementException - 如果此列表为空
        从以下版本开始:
        1.6
      • removeFirstOccurrence

        public boolean removeFirstOccurrence​(Object o)
        删除此列表中指定元素的第一个出现(从头到尾遍历列表时)。 如果列表不包含该元素,则它不会更改。
        Specified by:
        removeFirstOccurrence在接口 Deque<E>
        参数
        o - 要从此列表中删除的元素(如果存在)
        结果
        true如果列表包含指定的元素
        从以下版本开始:
        1.6
      • removeLastOccurrence

        public boolean removeLastOccurrence​(Object o)
        删除此列表中指定元素的最后一次出现(从头到尾遍历列表时)。 如果列表不包含该元素,则它不会更改。
        Specified by:
        removeLastOccurrence在接口 Deque<E>
        参数
        o - 要从此列表中删除的元素(如果存在)
        结果
        true如果列表包含指定的元素
        从以下版本开始:
        1.6
      • listIterator

        public ListIterator<E> listIterator​(int index)
        从列表中的指定位置开始,返回此列表中元素的列表迭代器(按适当的顺序)。 遵守List.listIterator(int)的总体合同。

        该列表迭代器是快速失败的 :如果列表在任何时间从结构上修改创建的Iterator后,以任何方式除非通过列表迭代器自身remove或者add方法,列表迭代器将抛出一个ConcurrentModificationException 因此,面对并发修改,迭代器将快速而干净地失败,而不是在未来未确定的时间冒着任意的非确定性行为。

        Specified by:
        listIterator在接口 List<E>
        Specified by:
        listIteratorAbstractSequentialList<E>
        参数
        index - 要从list-iterator返回的第一个元素的索引(通过调用 next
        结果
        一个ListIterator的列表中的元素(按顺序),从列表中的指定位置开始
        异常
        IndexOutOfBoundsException - 如果索引超出范围( index < 0 || index > size()
        另请参见:
        List.listIterator(int)
      • descendingIterator

        public Iterator<E> descendingIterator​()
        描述从接口Deque复制
        以相反的顺序返回此deque中的元素的迭代器。 元素将从最后(尾)到第一(头)的顺序返回。
        Specified by:
        descendingIterator在接口 Deque<E>
        结果
        在这个deque中的元素的反向迭代器
        从以下版本开始:
        1.6
      • clone

        public Object clone​()
        返回此LinkedList的浅拷贝。 (元素本身不被克隆。)
        重写:
        cloneObject
        结果
        这个 LinkedList一个浅拷贝的例子
        另请参见:
        Cloneable
      • toArray

        public Object[] toArray​()
        以正确的顺序(从第一个到最后一个元素)返回一个包含此列表中所有元素的数组。

        返回的数组将是“安全的”,因为该列表不保留对它的引用。 (换句话说,这个方法必须分配一个新的数组)。 因此,调用者可以自由地修改返回的数组。

        此方法充当基于阵列和基于集合的API之间的桥梁。

        Specified by:
        toArray在接口 Collection<E>
        Specified by:
        toArray接口 List<E>
        重写:
        toArrayAbstractCollection<E>
        结果
        一个包含该列表中所有元素的数组的数组
        另请参见:
        Arrays.asList(Object[])
      • toArray

        public <T> T[] toArray​(T[] a)
        以正确的顺序返回一个包含此列表中所有元素的数组(从第一个到最后一个元素); 返回的数组的运行时类型是指定数组的运行时类型。 如果列表适合指定的数组,则返回其中。 否则,将为指定数组的运行时类型和此列表的大小分配一个新数组。

        如果列表适用于指定的数组,并有空余余地(即数组的列表null更多),则紧跟在列表末尾的数组中的元素设置为null (这在调用者知道列表不包含任何空元素的情况下才能确定列表的长度。)

        toArray()方法一样,此方法充当基于阵列和基于集合的API之间的桥梁。 此外,该方法允许精确地控制输出阵列的运行时类型,并且在某些情况下可以用于节省分配成本。

        假设x是一个已知只包含字符串的列表。 以下代码可用于将列表转储到新分配的String数组中:

          String[] y = x.toArray(new String[0]); 
        请注意, toArray(new Object[0])功能与toArray()相同。
        Specified by:
        toArray在接口 Collection<E>
        Specified by:
        toArray在接口 List<E>
        重写:
        toArrayAbstractCollection<E>
        参数类型
        T - 包含集合的数组的运行时类型
        参数
        a - 要存储列表的元素的数组,如果它足够大; 否则,为此目的分配相同运行时类型的新数组。
        结果
        一个包含列表元素的数组
        异常
        ArrayStoreException - 如果指定数组的运行时类型不是此列表中每个元素的运行时类型的超类型
        NullPointerException - 如果指定的数组为空