关于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;
}
// 删除指定节点 x
E 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 的时候如果没有元素返回 null
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// poll 的时候如果没有元素返回 null
public 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 的实现细节。