jdk1.8 LinkedList源码全分析

本文原创地址,我的博客https://jsbintask.cn/2019/03/26/jdk/jdk8-linkedlist/(食用效果最佳),转载请注明出处!

前言

LinkedList内部是一个链表的实现,一个节点除了保持自身的数据外,还持有前,后两个节点的引用。所以就数据存储上来说,它相比使用数组作为底层数据结构的ArrayList来说,会更加耗费空间。但也正因为这个特性,它删除,插入节点很快!LinkedList没有任何同步手段,所以多线程环境须慎重考虑,可以使用Collections.synchronizedList(new LinkedList(...));保证线程安全。
LinkedList

友情链接:jdk1.8 ArrayList源码全分析

LinkedList结构

类关系

LinkedList
这里我们需要注意的是,相比于ArrayList,它额外实现了双端队列接口Deque,这个接口主要是声明了队头,队尾的一系列方法。

类成员

LinkedList
LinkedList内部有两个引用,一个first,一个last,分别用于指向链表的头和尾,另外有一个size,用于标识这个链表的长度,而它的接的引用类型是Node,这是他的一个内部类:
LinkedList
很容易理解,item用于保存数据,而prve用于指向当前节点的前一个节点,next用于指向当前节点的下一个节点。

源码解析

add(E e)方法

1
2
3
4
public boolean add(E e) {
linkLast(e);
return true;
}

这个方法直接调用linkLast:

1
2
3
4
5
6
7
8
9
10
11
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

我们用作图来解释下这个方法的执行过程,一开始,first和last都为null,此时链表什么都没有,当第一次调用该方法后,first和last均指向了第一个新加的节点E1:
LinkedList
接着,第二次调用该方法,加入新节点E2。首先,将last引用赋值给l,接着new了一个新节点E2,并且E2的prve指向l,接着将新节点E2赋值为last。现在结构如下:
LinkedList
接着判断l==null? 所以走的else语句,将l的next引用指向新节点E2,现在数据结构如下:
LinkedList
接着size+1,modCount+1,退出该方法,局部变量l销毁,所以现在数据结构如下:
LinkedList
这样就完成了链表新节点的构建。

add(int index, E element) 这个方法是在指定位置插入新元素

1
2
3
4
5
6
7
8
public void add(int index, E element) {
checkPositionIndex(index);

if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
  1. index位置检查(不能小于0,大于size)
  2. 如果index==size,直接在链表最后插入,相当于调用add(E e)方法
  3. 小于size,首先调用node方法将index位置的节点找出,接着调用linkBefore
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
    first = newNode;
    else
    pred.next = newNode;
    size++;
    modCount++;
    }

我们同样作图分析,假设现在链表中有三个节点,调用node方法后找到的第二个节点E2,则进入方法后,结构如下:
LinkedList
接着,将succ的prev赋值给pred,并且构造新节点E4,E4的prev和next分别为pred和suc,同时将新节点E4赋值为succ的prev引用,则现在结构如下:
LinkedList
接着,将新节点赋值给pred节点的next引用,结构如下:
LinkedList
最后,size+1,modCount+1,推出方法,本地变量succ,pred销毁,最后结构如下:
LinkedList
这样新节点E4就插入在了第二个E2节点前面。新链表构建完成。从这个过程中我们可以知道,这里并没有大量移动移动以前的元素,所以效率非常高!

E get(int index)获取指定节点数据

1
2
3
4
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}

直接调用node方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

  1. 判断index在链表的哪边。
  2. 遍历查找index或者size-index次,找出对应节点。
    这里我们知道,相比于数组的直接索引获取,遍历获取节点效率并不高。

E remove(int index)移除指定节点

1
2
3
4
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
  1. 检查index位置
  2. 调用node方法获取节点,接着调用unlink(E e)
    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
    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;
    }

这个方法就不做分析了,其原理就是将当前节点X的前一个节点P的next直接指向X的下一个节点D,这样X就不再关联任何引用,等待垃圾回收即可。
这里我们同样知道,相比于ArrayList的copy数组覆盖原来节点,效率同样更高!

到现在,我们关于链表的核心方法,增删改都分析完毕,最后介绍下它实现的队列Deque的各个方法:
LinkedList

  • add(E e):队尾插入新节点,如果队列空间不足,抛出异常;LinkedList没有空间限制,所以可以无限添加。
  • offer(E e):队尾插入新节点,空间不足,返回false,在LinkedList中和add方法同样效果。
  • remove():移除队头节点,如果队列为空(没有节点,first为null),抛出异常。LinkedList中就是first节点(链表头)
  • poll():同remove,不同点:队列为空,返回null
  • element():查询队头节点(不移除),如果队列为空,抛出异常。
  • peek():同element,不同点:队列为空,返回null。

总结

  1. LinkedList内部使用链表实现,相比于ArrayList更加耗费空间。
  2. LinkedList插入,删除节点不用大量copy原来元素,效率更高。
  3. LinkedList查找元素使用遍历,效率一般。
  4. LinkedList同时是双向队列的实现。

关注我,这里只有干货!

×

谢谢你支持我分享知识

扫码支持
扫码打赏,心意已收

打开微信扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 前言
  2. 2. LinkedList结构
    1. 2.1. 类关系
    2. 2.2. 类成员
  3. 3. 源码解析
    1. 3.1. add(E e)方法
    2. 3.2. add(int index, E element) 这个方法是在指定位置插入新元素
    3. 3.3. E get(int index)获取指定节点数据
    4. 3.4. E remove(int index)移除指定节点
  4. 4. 总结
欢迎扫描左方二维码跟作者交流.