从面试角度分析LinkedList源码

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

LinkedList类图如下：

LinkedList底层是由双向链表实现的。链表好比火车，每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针，还有指向上一个节点的指针。

在LinkedList源码中有一个Node静态类，源码如下：

 
 
 
 
  
  
  
  
private static class Node { 
  
  
  
  
    E item; 
  
  
  
  
    Node next; 
  
  
  
  
    Node prev; 
  
  
  
  
 
  
  
  
  
    Node(Node prev, E element, Node 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 first; 
  
  
  
  
 
  
  
  
  
/** 
  
  
  
  
  * 尾结点的指针. 
  
  
  
  
  * Invariant: (first == null && last == null) || 
  
  
  
  
  *            (last.next == null && last.item != null) 
  
  
  
  
  */ 
  
  
  
  
transient Node 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 l = last; 
  
  
  
  
    final Node 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 f = first; 
  
  
  
  
    final Node 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 node(int index) { 
  
  
  
  
    // assert isElementIndex(index); 
  
  
  
  
    // 如果指定下标 < 一半元素数量，则从首结点开始遍历 
  
  
  
  
    // 否则，从尾结点开始遍历 
  
  
  
  
    if (index < (size >> 1)) { 
  
  
  
  
        Node x = first; 
  
  
  
  
        for (int i = 0; i < index; i++) 
  
  
  
  
            x = x.next; 
  
  
  
  
        return x; 
  
  
  
  
    } else { 
  
  
  
  
        Node x = last; 
  
  
  
  
        for (int i = size - 1; i > index; i--) 
  
  
  
  
            x = x.prev; 
  
  
  
  
        return x; 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 

unlink(Node x)源码如下：

 
 
 
 
  
  
  
  
E unlink(Node x) { 
  
  
  
  
    // assert x != null; 
  
  
  
  
    final E element = x.item; 
  
  
  
  
    final Node next = x.next; 
  
  
  
  
    final Node 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旅途公众号。

当前题目：从面试角度分析LinkedList源码
本文URL：http://www.csdahua.cn/qtweb/news40/473590.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网