关于java:深入剖析LinkedList源码

简介

LinkedList和ArrayList数据结构是齐全不一样的，ArrayList 底层是数组的构造，而 LinkedList 的底层则是链表的构造，它能够进行高效的插入和移除的操作，它基于的是一个双向链表的构造。

LinkedList的整体结构图

从图中也能看出，LinkedList 有好多的Node，并且还有first和last这两个变量保留头部和尾部节点的信息；还有就是它不是一个循环的双向链表，因为它前后都是null，这个也是咱们须要留神的中央。

继承体系

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{...}

通过继承体系，咱们能够看到 LinkedList 不仅实现了List接口，还实现了Queue和Deque接口，所以它既能作为 List 应用，也能作为双端队列应用，当然也能够作为栈应用。

源码剖析

次要属性

// 元素个数transient int size = 0;// 链表首节点transient Node<E> first;// 链表尾节点transient Node<E> last;

Node节点

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

构造方法

public LinkedList() {}public LinkedList(Collection<? extends E> c) {    this();    //将汇合C中的所有的元素都插入到链表中    addAll(c);}

增加元素

作为一个双端队列，增加元素次要有两种，一种是在队列尾部增加元素，一种是在队列首部增加元素，这两种模式在LinkedList中次要是通过上面两个办法来实现的。

// 从队列首增加元素private void linkFirst(E e) {    // 首节点    final Node<E> f = first;    // 创立新节点，新节点的next是首节点    final Node<E> newNode = new Node<>(null, e, f);    // 让新节点作为新的首节点    first = newNode;    // 判断是不是第一个增加的元素    // 如果是就把last也置为新节点    // 否则把原首节点的prev指针置为新节点    if (f == null)        last = newNode;    else        f.prev = newNode;    // 元素个数加1    size++;    // 批改次数加1，阐明这是一个反对fail-fast的汇合    modCount++;}// 从队列尾增加元素void linkLast(E e) {    // 队列尾节点    final Node<E> l = last;    // 创立新节点，新节点的prev是尾节点    final Node<E> newNode = new Node<>(l, e, null);    // 让新节点成为新的尾节点    last = newNode;    // 判断是不是第一个增加的元素    // 如果是就把first也置为新节点    // 否则把原尾节点的next指针置为新节点    if (l == null)        first = newNode;    else        l.next = newNode;    // 元素个数加1    size++;    // 批改次数加1    modCount++;}public void addFirst(E e) {    linkFirst(e);}public void addLast(E e) {    linkLast(e);}// 作为无界队列，增加元素总是会胜利的public boolean offerFirst(E e) {    addFirst(e);    return true;}public boolean offerLast(E e) {    addLast(e);    return true;}

下面是作为双端队列来看，它的增加元素分为首尾增加元素，作为List，是要反对在两头增加元素的，次要是通过上面这个办法实现的。

// 在节点succ之前增加元素void linkBefore(E e, Node<E> succ) {    // succ是待增加节点的后继节点    // 找到待增加节点的前置节点    final Node<E> pred = succ.prev;    // 在其前置节点和后继节点之间创立一个新节点    final Node<E> newNode = new Node<>(pred, e, succ);    // 批改后继节点的前置指针指向新节点    succ.prev = newNode;    // 判断前置节点是否为空    // 如果为空，阐明是第一个增加的元素，批改first指针    // 否则批改前置节点的next为新节点    if (pred == null)        first = newNode;    else        pred.next = newNode;    // 批改元素个数    size++;    // 批改次数加1    modCount++;}// 寻找index地位的节点Node<E> node(int index) {    // 因为是双链表    // 所以依据index是在前半段还是后半段决定从前遍历还是从后遍历    // 这样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;    }}// 在指定index地位处增加元素public void add(int index, E element) {    // 判断是否越界    checkPositionIndex(index);    // 如果index是在队列尾节点之后的一个地位    // 把新节点间接增加到尾节点之后    // 否则调用linkBefore()办法在两头增加节点    if (index == size)        linkLast(element);    else        linkBefore(element, node(index));}

在两头增加元素的办法也很简略，典型的双链表在两头增加元素的办法。

增加元素的三种形式大抵如下图所示：

在队列首尾增加元素很高效，工夫复杂度为O(1)。

在两头增加元素比拟低效，首先要先找到插入地位的节点，再批改前后节点的指针，工夫复杂度为O(n)。

删除元素

作为双端队列，删除元素也有两种形式，一种是队列首删除元素，一种是队列尾删除元素。

作为List，又要反对两头删除元素，所以删除元素一个有三个办法，别离如下。

// 删除首节点private E unlinkFirst(Node<E> f) {    // 首节点的元素值    final E element = f.item;    // 首节点的next指针    final Node<E> next = f.next;    // 增加首节点的内容，帮助GC    f.item = null;    f.next = null; // help GC    // 把首节点的next作为新的首节点    first = next;    // 如果只有一个元素，删除了，把last也置为空    // 否则把next的前置指针置为空    if (next == null)        last = null;    else        next.prev = null;    // 元素个数减1    size--;    // 批改次数加1    modCount++;    // 返回删除的元素    return element;}// 删除尾节点private E unlinkLast(Node<E> l) {    // 尾节点的元素值    final E element = l.item;    // 尾节点的前置指针    final Node<E> prev = l.prev;    // 清空尾节点的内容，帮助GC    l.item = null;    l.prev = null; // help GC    // 让前置节点成为新的尾节点    last = prev;    // 如果只有一个元素，删除了把first置为空    // 否则把前置节点的next置为空    if (prev == null)        first = null;    else        prev.next = null;    // 元素个数减1    size--;    // 批改次数加1    modCount++;    // 返回删除的元素    return element;}// 删除指定节点xE unlink(Node<E> x) {    // x的元素值    final E element = x.item;    // x的前置节点    final Node<E> next = x.next;    // x的后置节点    final Node<E> prev = x.prev;    // 如果前置节点为空    // 阐明是首节点，让first指向x的后置节点    // 否则批改前置节点的next为x的后置节点    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    // 如果后置节点为空    // 阐明是尾节点，让last指向x的前置节点    // 否则批改后置节点的prev为x的前置节点    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    // 清空x的元素值，帮助GC    x.item = null;    // 元素个数减1    size--;    // 批改次数加1    modCount++;    // 返回删除的元素    return element;}// remove的时候如果没有元素抛出异样public E removeFirst() {    final Node<E> f = first;    if (f == null)        throw new NoSuchElementException();    return unlinkFirst(f);}// remove的时候如果没有元素抛出异样public E removeLast() {    final Node<E> l = last;    if (l == null)        throw new NoSuchElementException();    return unlinkLast(l);}// poll的时候如果没有元素返回nullpublic E pollFirst() {    final Node<E> f = first;    return (f == null) ? null : unlinkFirst(f);}// poll的时候如果没有元素返回nullpublic E pollLast() {    final Node<E> l = last;    return (l == null) ? null : unlinkLast(l);}// 删除两头节点public E remove(int index) {    // 查看是否越界    checkElementIndex(index);    // 删除指定index地位的节点    return unlink(node(index));}

删除元素的三种办法都是典型的双链表删除元素的办法，大抵流程如下图所示。

[

在队列首尾删除元素很高效，工夫复杂度为O(1)。

在两头删除元素比拟低效，首先要找到删除地位的节点，再批改前后指针，工夫复杂度为O(n)。

栈

后面咱们说了，LinkedList是双端队列，还记得双端队列能够作为栈应用吗？

package org.example.test;import java.util.LinkedList;/** * 利用LinkedList来模仿栈 * 栈的特点：先进后出 */public class Test12 {    private LinkedList<String> linkList = new LinkedList<String>();    // 压栈    public void push(String str){        linkList.addFirst(str);    }    // 出栈    public String pop(){        return linkList.removeFirst();    }    // 查看    public String peek(){        return linkList.peek();    }    // 判断是否为空    public boolean isEmpty(){        return linkList.isEmpty();    }}class Test13 {    public static void main(String[] args) {        // 测试栈        Test12 test12 = new Test12();        test12.push("我是第1个进去的");        test12.push("我是第2个进去的");        test12.push("我是第3个进去的");        test12.push("我是第4个进去的");        test12.push("我是第5个进去的");        // 取出        while (!test12.isEmpty()){            String pop = test12.pop();            System.out.println(pop);        }        // 打印后果        /*我是第5个进去的        我是第4个进去的        我是第3个进去的        我是第2个进去的        我是第1个进去的*/    }}

栈的个性是LIFO(Last In First Out)，所以作为栈应用也很简略，增加删除元素都只操作队列首节点即可。

总结

（1）LinkedList是一个以双链表实现的List，因而不存在容量有余的问题，所以没有扩容的办法。

（2）LinkedList还是一个双端队列，具备队列、双端队列、栈的个性。

（3）LinkedList在队列首尾增加、删除元素十分高效，工夫复杂度为O(1)。

（4）LinkedList在两头增加、删除元素比拟低效，工夫复杂度为O(n)。

（5）LinkedList不反对随机拜访，所以拜访非队列首尾的元素比拟低效。

（6）LinkedList在性能上等于ArrayList + ArrayDeque。

（7）LinkedList是非线程平安的。

（8）LinkedList能存储null值。

经典面试题

谈谈ArrayList和LinkedList的区别。

实质的区别来源于两者的底层实现：ArrayList的底层是数组，LinkedList的底层是双向链表。

数组领有O(1)的查问效率，能够通过下标间接定位元素；链表在查问元素的时候只能通过遍历的形式查问，效率比数组低。

数组增删元素的效率比拟低，通常要随同拷贝数组的操作；链表增删元素的效率很高，只须要调整对应地位的指针即可。

以上是数组和链表的艰深比照，在日常的应用中，两者都能很好地在本人的实用场景发挥作用。

咱们经常用ArrayList代替数组，因为封装了许多易用的api，而且它外部实现了主动扩容机制，因为它外部保护了一个以后容量的指针size，间接往ArrayList中增加元素的工夫复杂度是O(1)的，应用十分不便。

而LinkedList经常被用作Queue队列的实现类，因为底层是双向链表，可能轻松地提供先入先出的操作。

能够分两局部答：一个是数组与链表底层实现的不同，另一个是答ArrayList和LinkedList的实现细节。