死磕Jdk源码之LinkedList:

本博客目前所有 死磕 Jdk 源码系列都是使用 jdk1.8版本。

简介

双向链表实现了列表和Deque接口。实现所有可选的列表操作，并允许所有元素(包括null)。
所有操作的执行都符合双向链表的预期。索引到列表中的操作将从头或尾遍历列表，以更接近指定索引的操作为准。

特性

  1. LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当做堆栈、队列或双端队列进行使用。
  2. LinkedList实现List接口，能让它进行队列操作。
  3. LinkedList实现Deque接口，即能将LinkedList当做双端队列使用。
  4. LinkedList实现Cloneable，即覆盖了函数clone()，能被克隆。
  5. LinkedList实现了java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
  6. LinkedList中的操作不是线程安全的。

数据结构

LinkedList内部维护一个双向列表

线程安全性

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

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

成员变量

LinkedList有三个个关键的成员变量

还有一个记录集合修改次数的变量，由iterator和listIterator，如果在迭代过程中，modCount的值变更，就会抛出ConcurrentModificationException异常。

  • size

表示LinkedList中的元素个数

  • first

LinkedList的第一个节点

满足要么第一个节点和最后一个节点都为null，要么第一个节点不为null，第一个的前驱节点为空

  • last

LinkedList的最后一个节点

满足要么第一个节点和最后一个节点都为null，要么最后一个节点不为null，第一个的后继节点为空

死磕源码

添加元素

add(E e)

将指定的元素追加到此列表的末尾。

1
2
3
4
5
public boolean add(E e) {
    // 将元素 e 追加到链表末尾
    linkLast(e);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Links e as last element.
 */
void linkLast(E e) {
    // 获取当前 last 节点
    final Node<E> l = last;
    // 创建一个新节点，节点的前驱节点为原 last 节点，节点的后继节点为 null
    final Node<E> newNode = new Node<>(l, e, null);
    // 将当前节点置为末尾绩点
    last = newNode;
    // 如果原 last 节点为 null，就说明链表为空，将 first 设置为新节点
    if (l == null)
        first = newNode;
    // 如果原末尾节点不为 null，将原 last 节点的后继节点指向新节点
    else
        l.next = newNode;
    // 链表大小 +1
    size++;
    // 修改次数 + 1
    modCount++;
}

add(int index, E element)

将指定元素插入到列表中的指定位置。通过改变后续元素的指向。

1
2
3
4
5
6
7
8
9
10
11
public void add(int index, E element) {
    // 检查给定的索引是否合法
    checkPositionIndex(index);

    // 如果索引值等于链表大小，就相当于在尾部追加节点
    if (index == size)
        linkLast(element);
    // 调用 linkBefore ，在指定节点前插入元素 element
    else
        linkBefore(element, node(index));
}

node方法根据索引返回指定位置的节点，其实就是遍历链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 等同于 index < size/2，如果索引在链表的前半部分就从 first 节点往后遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    // 如果 索引在链表的后半部分就从 last 节点往前遍历    
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

在指定节点 succ 前插入 元素 e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 获取被插入节点的前驱节点
    final Node<E> pred = succ.prev;
    // 创建一个新的节点，前驱节点为 succ 节点的前驱节点，后继节点为 succ 节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 节点的前驱节点置为新节点
    succ.prev = newNode;
    // 如果 succ 节点的 前驱节点为null，也就是说原链表为空，新节点就是第一个元素，新节点同时也是 first 节点
    if (pred == null)
        first = newNode;
    // 否则就将原 succ 节点的前驱节点的后继节点置为新节点 
    else
        pred.next = newNode;
    // 链表大小 +1    
    size++;
    // 修改次数 + 1
    modCount++;
}

移除元素

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
    // 如果 o 为 null，就移除第一个元素为 null 的节点
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    // 否则移除第一个 equals o 的元素节点    
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

从链表中移除对应的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    // 获取当前节点的元素 element
    final E element = x.item;
    // 获取当前节点的后继节点 next
    final Node<E> next = x.next;
    // 获取当前节点的前驱节点 prev
    final Node<E> prev = x.prev;

    // 如果 prev 节点为 null，说明是 first 节点，就将 next 节点指向 first
    if (prev == null) {
        first = next;
    }
    // 否则
    else {
        // 将 prev 节点的后继节点指向 next 节点
        prev.next = next;
        // 当前节点的前驱节点置为 null
        x.prev = null;
    }
    // 如果 next 节点为 null，说明是 last 节点，就将 prev 节点指向 last
    if (next == null) {
        last = prev;
    } 
    // 否则
    else {
        /// 将 next 节点的前驱节点指向 prev 节点
        // 当前节点的后继节点置为 null
        next.prev = prev;
        x.next = null;
    }
    // 当前节点元素置为 null
    x.item = null;
    // 链表大小 -1
    size--;
    // 修改次数 + 1
    modCount++;
    // 返回被移除的元素
    return element;
}

removeFirst()

移除链表的 first 节点并返回被移除的元素

1
2
3
4
5
6
7
8
9
10
public E removeFirst() {
    // 获取当前 first 节点
    final Node<E> f = first;
    // 如果 first 节点为 null，也就是链表为空，就抛出 NoSuchElementException 异常
    if (f == null)
        throw new NoSuchElementException();
    // 移除 first 节点
    return unlinkFirst(f);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取 f 节点的元素
    final E element = f.item;
    // 获取 f (原 first)节点的后继节点 next
    final Node<E> next = f.next;
    // 将 f 节点 元素置为 null
    f.item = null;
    // 将 f 节点 后继节点置为 null
    f.next = null; // help GC
    // 将 first 节点指向 f (原 first) 节点的 next 节点
    first = next;
    // 如果 next 节点为 null，说明此时链表为空，last 节点也应该为 null
    if (next == null)
        last = null;
    // 否则，将 next (当前 first)节点的前驱节点置为 null   
    else
        next.prev = null;
    // 链表大小 -1        
    size--;
    // 修改次数 + 1
    modCount++;
    // 返回被移除的元素
    return element;
}

removeLast()

移除链表的 last 节点并返回被移除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Removes and returns the last element from this list.
 *
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeLast() {
     // 获取当前 last 节点
    final Node<E> l = last;
     // 如果 last 节点为 null，也就是链表为空，就抛出 NoSuchElementException 异常
    if (l == null)
        throw new NoSuchElementException();
    // 移除 last 节点    
    return unlinkLast(l);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Unlinks non-null last node l.
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 获取 l 节点的元素
    final E element = l.item;
    // 获取 l (原 last)节点的前驱节点 prev
    final Node<E> prev = l.prev;
    // 将 l 节点 元素置为 null
    l.item = null;
    // 将 l 节点 前驱节点置为 null
    l.prev = null; // help GC
    // 将 last 节点指向 原 last 节点的前驱节点 prev
    last = prev;
    //  如果 prev 为 null，说明链表为空，将 first置为 null
    if (prev == null)
        first = null;
    // 否则，将 prev (当前 last)节点的后继节点置为 null   
    else
        prev.next = null;
    // 链表大小 -1        
    size--;
    // 修改次数 + 1
    modCount++;
    // 返回被移除的元素
    return element;
}

总结

LinkedList插入效率很高，通过索引插入效率较低需要遍历链表，根据索引值选择从 last 或 first 节点开始遍历。最坏结果为需要遍历 size/2 个元素。
LinkedList移除元素效率很高，通过索引移除元素同通过索引插入元素，需要遍历节点。