LinkedList

jdk1.8 LinkedList源码全分析

LinkedList

jsbintask关注

52019.03.26 16:19:45字数 1,124阅读 2,297

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

前言

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

LinkedList

LinkedList

 

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

LinkedList结构

类关系

 

LinkedList

LinkedList


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

 

类成员

 

LinkedList

LinkedList


LinkedList内部有两个引用,一个first,一个last,分别用于指向链表的头和尾,另外有一个size,用于标识这个链表的长度,而它的接的引用类型是Node,这是他的一个内部类:

LinkedList

LinkedList


很容易理解,item用于保存数据,而prve用于指向当前节点的前一个节点,next用于指向当前节点的下一个节点。

 

源码解析

add(E e)方法

public boolean add(E e) {
    linkLast(e);
    return true;
}

这个方法直接调用linkLast:

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

LinkedList

 

接着,第二次调用该方法,加入新节点E2。首先,将last引用赋值给l,接着new了一个新节点E2,并且E2的prve指向l,接着将新节点E2赋值为last。现在结构如下:

 

LinkedList

LinkedList


接着判断l==null? 所以走的else语句,将l的next引用指向新节点E2,现在数据结构如下:

LinkedList

LinkedList

 

接着size+1,modCount+1,退出该方法,局部变量l销毁,所以现在数据结构如下:

 

LinkedList

LinkedList


这样就完成了链表新节点的构建。

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

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
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

LinkedList

 

接着,将succ的prev赋值给pred,并且构造新节点E4,E4的prev和next分别为pred和suc,同时将新节点E4赋值为succ的prev引用,则现在结构如下:

 

LinkedList

LinkedList


接着,将新节点赋值给pred节点的next引用,结构如下:

LinkedList

LinkedList

 

最后,size+1,modCount+1,推出方法,本地变量succ,pred销毁,最后结构如下:

 

LinkedList

LinkedList


这样新节点E4就插入在了第二个E2节点前面。新链表构建完成。从这个过程中我们可以知道,这里并没有大量移动移动以前的元素,所以效率非常高!

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

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

直接调用node方法:

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)移除指定节点

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

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同时是双向队列的实现。
 
上一篇:坏掉的项链(洛谷P1203题题解,C++语言描述)


下一篇:算法刷题【2】反向链表