LinkedList类【JDK源码分析】

简介: LinkedList类【JDK源码分析】

前言


2022/11/2

路漫漫其修远兮,吾将上下而求索


本文是根据jdk学习所做笔记

仅供学习交流使用,转载注明出处


推荐

JDK API 1.6 中文版

说明

以下内容是结合很多资料进行编写的

源码为jdk1.8的

斜体样式 为自己的思考

下划线为自己所画的重点

LinkedList类

基本信息

java.util

类 LinkedList< E>

java.lang.Object

继承者 java.util.AbstractCollection< E>

继承者 java.util.AbstractList< E>

继承者 java.util.AbstractSequentialList< E>

继承者 java.util.LinkedList

类型参数:

E - 在此 collection 中保持的元素的类型

所有已实现的接口:

Serializable, Cloneable, Iterable< E>, Collection< E>, Deque< E>, List< E>, Queue< E>


public class LinkedList

extends AbstractSequentialList

implements List, Deque, Cloneable, Serializable


List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。


此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。


所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。

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

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

此类的 iterator 和 listIterator 方法返回的迭代器是快速失败 的:在迭代器创建之后,如果从结构上对列表进行修改,除非通过迭代器自身的 remove 或 add 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒将来不确定的时间任意发生不确定行为的风险。


注意,迭代器的快速失败行为不能得到保证,一般来说,存在不同步的并发修改时,不可能作出任何硬性保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的方式是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。


此类是 Java Collections Framework 的成员。


从以下版本开始:

1.2

另请参见:

List, ArrayList, Vector, 序列化表格

字段摘要

从类 java.util.AbstractList 继承的字段

modCount

构造方法摘要

LinkedList()

构造一个空列表。

LinkedList(Collection<? extends E> c)

构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列。

¥## 方法摘要

boolean add(E e)

将指定元素添加到此列表的结尾。


void add(int index, E element)

在此列表中指定的位置插入指定的元素。


boolean addAll(Collection<? extends E> c)

添加指定 collection 中的所有元素到此列表的结尾,顺序是指定 collection 的迭代器返回这些元素的顺序。


boolean addAll(int index, Collection<? extends E> c)

将指定 collection 中的所有元素从指定位置开始插入此列表。


void addFirst(E e)

将指定元素插入此列表的开头。


void addLast(E e)

将指定元素添加到此列表的结尾。


void clear()

从此列表中移除所有元素。


Object clone()

返回此 LinkedList 的浅表副本。


boolean contains(Object o)

如果此列表包含指定元素,则返回 true。


Iterator descendingIterator()

返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。


E element()

获取但不移除此列表的头(第一个元素)。


E get(int index)

返回此列表中指定位置处的元素。


E getFirst()

返回此列表的第一个元素。


E getLast()

返回此列表的最后一个元素。


int indexOf(Object o)

返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。


int lastIndexOf(Object o)

返回此列表中最后出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。


ListIterator 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()

返回此列表的元素数。


Object[] toArray()

返回以适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组。


T[]

toArray(T[] a)

返回以适当顺序(从第一个元素到最后一个元素)包含此列表中所有元素的数组;返回数组的运行时类型为指定数组的类型。


从类 java.util.AbstractSequentialList 继承的方法

iterator


从类 java.util.AbstractList 继承的方法

equals, hashCode, listIterator, removeRange, subList


从类 java.util.AbstractCollection 继承的方法

containsAll, isEmpty, removeAll, retainAll, toString


从类 java.lang.Object 继承的方法

finalize, getClass, notify, notifyAll, wait, wait, wait


从接口 java.util.List 继承的方法

containsAll, equals, hashCode, isEmpty, iterator, listIterator, removeAll, retainAll, subList


从接口 java.util.Deque 继承的方法

iterator

字段

  transient int size = 0;
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

构造方法详细信息

LinkedList

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


LinkedList

public LinkedList(Collection<? extends E> c)

构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列。


参数:

c - 要将其元素放入此列表的 collection

抛出:

NullPointerException - 如果指定的 collection 为 null

内部类

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    /**
     * Returns a list-iterator of the elements in this list (in proper
     * sequence), starting at the specified position in the list.
     * Obeys the general contract of {@code List.listIterator(int)}.<p>
     *
     * The list-iterator is <i>fail-fast</i>: if the list is structurally
     * modified at any time after the Iterator is created, in any way except
     * through the list-iterator's own {@code remove} or {@code add}
     * methods, the list-iterator will throw a
     * {@code ConcurrentModificationException}.  Thus, in the face of
     * concurrent modification, the iterator fails quickly and cleanly, rather
     * than risking arbitrary, non-deterministic behavior at an undetermined
     * time in the future.
     *
     * @param index index of the first element to be returned from the
     *              list-iterator (by a call to {@code next})
     * @return a ListIterator of the elements in this list (in proper
     *         sequence), starting at the specified position in the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @see List#listIterator(int)
     */
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);//也是快速失败 
    }
    final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

add

public boolean add(E e)

将指定元素添加到此列表的结尾。

此方法等效于 addLast(E)。


指定者:

接口 Collection 中的 add

指定者:

接口 Deque 中的 add

指定者:

接口 List 中的 add

指定者:

接口 Queue 中的 add

覆盖:

类 AbstractList 中的 add

参数:

e - 要添加到此列表的元素

返回:

true(根据 Collection.add(E) 的规定)

    /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;//l,最后结点  lp,l,null (prev, element, next)
        final Node<E> newNode = new Node<>(l, e, null);//新结点 把值e的newNode的prev指向l 
        last = newNode;//最后指针指向新加入的最后结点
        if (l == null)
            first = newNode;//为空是同一个 l=last=null
        else
            l.next = newNode;//l的next指向newNode
        size++;//数量加
        modCount++;//结构变化次数加
    }

remove

public boolean remove(Object o)从此列表中移除首次出现的指定元素(如果存在)。如果列表不包含该元素,则不作更改。更确切地讲,移除具有满足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引 i 的元素(如果存在这样的元素)。如果此列表已包含指定元素(或者此列表由于调用而发生更改),则返回 true。


指定者:

接口 Collection 中的 remove

指定者:

接口 Deque 中的 remove

指定者:

接口 List 中的 remove

覆盖:

类 AbstractCollection 中的 remove

参数:

o - 要从此列表删除的元素,如果存在

返回:

如果此列表包含指定元素,则返回 true

    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * Unlinks non-null node x.
     */
    E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }

总结

关键词:

  • public LinkedList()
  • 构造一个空列表。
  • add
  • remove
  • listIterator
  • 快速失败

最后

开源=为爱发电

相关文章
|
4月前
|
存储 安全 Java
【JDK 源码分析】ConcurrentHashMap 底层结构
【1月更文挑战第27天】【JDK 源码分析】ConcurrentHashMap 底层结构
|
4月前
|
Java
【JDK 源码分析】HashMap 操作方法
【1月更文挑战第27天】【JDK 源码分析】HashMap Put 元素 初始化
|
5月前
|
Java
Integer类【JDK源码分析】
Integer类【JDK源码分析】
22 0
|
5月前
|
存储 网络协议 Java
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
38 0
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)(二)
|
6月前
源码分析系列教程(12) - 手写Map框架(基于JDK1.7)
源码分析系列教程(12) - 手写Map框架(基于JDK1.7)
22 0
|
2月前
|
算法 Java 索引
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
34 0
|
3月前
|
存储 网络协议 Java
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
【Java】BIO源码分析和改造(GraalVM JDK 11.0.19)
15 0
|
4月前
|
安全 Java
【JDK 源码分析】HashMap 线程安全问题分析
【1月更文挑战第27天】【JDK 源码分析】HashMap 线程安全问题分析
|
4月前
|
存储 Java
【JDK 源码分析】HashMap 底层结构
【1月更文挑战第27天】【JDK 源码分析】HashMap 底层结构
|
5月前
JDK8之stream流的使用:归约类方法
JDK8之stream流的使用:归约类方法
23 0