乐趣区

关于java:从面试角度分析LinkedList源码

jiezi

注：本系列文章中用到的 jdk 版本均为java8

LinkedList类图如下：

LinkedList底层是由双向链表实现的。链表好比火车，每节车厢蕴含了车厢和连贯下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针，还有指向上一个节点的指针。
在 LinkedList 源码中有一个 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;
    }
}

一个 Node 节点蕴含三个局部，别离是

  • item：数据
  • next：下一个节点的指针
  • prev：上一个节点的指针

LinkedList的次要变量如下：

// 汇合中的元素数量
transient int size = 0;

/**
  * 首节点的指针.
  * Invariant: (first == null && last == null) ||
  *            (first.prev == null && first.item != null)
  */
transient Node<E> first;

/**
  * 尾结点的指针.
  * Invariant: (first == null && last == null) ||
  *            (last.next == null && last.item != null)
  */
transient Node<E> last;

一 增加元素

LinkedList反对想任意节点地位增加元素，不仅提供了汇合罕用的 add() 办法，还提供了 addFirst() 和addLast()，add()办法默认调用 addLast() 办法，也就是默认是往链表尾部插入元素的。

add()办法源码：

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

1.1 尾部插入元素

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

咱们来画张图演示一下如何给链表尾部插入元素：

如果链表中没有元素

对应源码中的 if 语句，如果没有元素则新增的这个节点为链表中惟一的一个元素，既是首节点，又是尾结点，前一个元素的指针和后一个元素的指针都是 null。这里留神head 节点不是第一个节点，head节点只是标识了这个链表的地址。

如果链表中有元素

对应源码中 else 语句。先将新增的元素当成Last 节点，而后将原来的 Last 节点的 next 指向新节点。

else
    l.next = newNode;

一图胜前言，画个图是不是什么都明确了。

1.2 头部插入元素

linkFirst()源码如下：

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

还是依据下面的图来解读一下源码，先将第一个节点赋值给两头变量 f，将新节点newNode 赋值给 first 节点。如果链表没有元素，则 Last 节点和 First 节点都是新插入的节点 newNode，否则，将原来的First 节点的头指针指向新节点。

二 删除元素

LinkedList提供的删除办法有依据 索引 和元素 删除，除此之外还提供删除第一个元素和最初一个元素的办法，这里咱们只剖析一下依据索引删除的办法。

public E remove(int index) {checkElementIndex(index);
    return unlink(node(index));
}

checkElementIndex(index)办法就是用来判断传输的索引值是否非法，不非法则抛出数组越界异样。重点来看一下 unlink(node(index)) 办法是如何删除元素的。

node(index)办法源码：

node(index)办法就是依据索引获取该索引地位的节点

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

unlink(Node<E> x)源码如下：

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

画张图剖析一下删除是如何进行的：

  1. 假如删除的是第一个元素：则它的prev==NULL，咱们须要将他的后一个元素（图中的 second）作为第一个元素
  2. 假如删除的是最初一个元素，则它的next==null，咱们须要将他的前一个元素（途中的 second）作为最初一个元素
  3. 如果是两头的任意元素 ，则须要将它的前一个元素的next 指针指向它的后一个元素，同时将它的后一个元素的 prev 指针指向它的前一个元素。

三 总结

LinkedList底层是由双向链表实现的，因为是链表实现的，不仅要存放数据，还要寄存指针，所以内存开销要比 ArrayList 大，删除元素不须要挪动其余元素，只须要扭转指针的指向，因而删除效率更高，同时它没有实现 RandomAccess 接口，因而应用迭代器遍历要比 for 循环更加高效。LinkedList也反对插入反复值和空值，同样也是线程不平安的。

点关注、不迷路

如果感觉文章不错，欢送关注、点赞、珍藏，你们的反对是我创作的能源，感激大家。

如果文章写的有问题，请不要吝惜文笔，欢送留言指出，我会及时核查批改。

如果你还想看到更多别的货色，能够微信搜寻「Java 旅途」进行关注。「Java 旅途」目前曾经整顿各种中间件的应用教程及各类 Java 相干的面试题。扫描下方二维码进行关注就能够失去这些材料。

退出移动版