面试官让我把源码捋一遍，捋的我头皮发麻，但还是让我回家等消息了

曾经终败给现在 2021-08-28 12:32 379阅读 0赞

点击上方 [Java后端][Java]，选择 设为星标

优质文章，及时送达

--------------------

**前言：**本文为《今天你面试了吗》系列文章，采用情景对话的方式虚构面试场景，旨在帮助大家梳理常用 Java 技术栈的知识点，日后我会把此系列整理成 PDF 版本，发布给大家。还请大家标星本公众号：Java后端，第一时间接受推送。最后，求个转发、点赞、分享啊，你们的转发和在看是我们最大的鼓励！

昨天复习了一下[ArrayList的使用及原理][ArrayList]，复习着就睡着了。今天一觉醒来，hr又通知我有空去聊聊技术。去的路上，我一直在想，今天会问些什么问题，集合？多线程？还是底层原理......真是越想越激动。心想昨天晚上复习了一晚，还怕这？想着想着就到了，尽管还是那个熟悉的面试官，但那张英俊的面孔折射出要把我面趴下的自信。他先开口了：咋眼圈都是黑的？这么重视？

**我：**对啊，昨天复习了一下基础知识，看了一下集合相关的内容。

**面试官：**好，不错，那今天就聊聊集合吧，你先讲讲 ArrayList 的原理和用法吧。这个接口用的比较多。

**我：**我心想，昨天把这个知识点整理了出来，现在终于派上用场了：[ArrayList的使用及原理，面试必问的知识点][ArrayList]，我把这篇博文的内容大侃一通。

**面试官：**还可以，看来没少下功夫，那咱们聊聊LinkedList吧

**我心想：**还是这个套路，无论是在面试还是在平时应用中，都经常将LinkedList与ArrayList进行比较，因为他们虽然都是List主力军，但因其结构的不同，其应用场景也不太相同。

**我：**好，来吧

**面试官：**你说说LinkedList的继承关系吧

### **我：**这个接口用的老熟了，LinkedList的继承关系是这样的：    ###

![format_png][]

### **面试官：**行吧，有没有读过 LinkedList 的源码？ ###

**我：**这基础中的基础，肯定看过啊

**面试官：**行，我不单独问了，你就从头把 LinkedList 的用法和原理给我捋一遍吧

**我：**好吧。。。调整一下心态，我开始了讲解：

LinkedList有两个**构造函数**：① 无参；②参数为集合。

举个栗子：

//默认创建一个LinkedList
    LinkedList<String> l1 = new LinkedList<>();
    //创建一个将其他类型集合中的数据化为己用的LinkedList
    LinkedList<String> l2 = new LinkedList<>(new HashSet<>());

在了解LinkedList的源码之前，我们先看看LinkedList的**属性**：

transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         * (first.prev == null && first.item != null)
         */
    transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         * (last.next == null && last.item != null)
         */
     transient Node<E> last;

transient关键词的用处在于**该类的对象序列化时，被transient修饰的属性并不参与序列化**，详情可以参考之前的文章：[《你真的有好好了解过序列化吗：Java序列化实现的原理》。][Java 1]可以看到，LinkedList主要是**由若干节点连接而成**，有两个终端节点，一个在起始位置，另一个在终点位置，并且还有一个属性**size记录整个LinkedList中的节点数**。

至于Node节点，我们来观察它的结构。

#### **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节点中有定义了前一个节点和后一个节点，即一个节点既可以找到向前和向后方向的结点，所以可以初步判断，**LinkedList内部维护了一个双向链表**。其中，item变量保存的是当前节点的值，通过next变量指向前一个节点，通过prev变量指向后一个节点。

接下来我们来看定义ArrayList的**两种**构造函数。

#### **LinkedList无参构造函数** ####

public LinkedList() {}

你没看错，LinkedList的无参构造函数就是**什么操作都没有**，因为其类的定义属性中已经包含了LinkedList初始化时需要的一切——终端节点、节点个数。这也就意味着，**LinkedList类的重点在于节点的构成以及节点之间的操作**。

#### LinkedList有参构造函数——入参类型为集合类 ####

/**
         * Constructs a list containing the elements of the specified
         * collection, in the order they are returned by the collection's
         * iterator.
         * ......
         */
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }

暂且不去看addAll()方法的内部实现，仅通过注释可以知道，在通过集合类来构造LinkedList的过程中，是会通过集合类中通用的**iterator来进行遍历**，然后挨个加入到LinkedList中。

### **怎么使用LinkedList？** ###

我们已经知道了如何去定义一个LinkedList，而且上文也提到过LinkedList中节点之间的操作是重点，接下来我们来介绍下LinkedList中常用的方法：get、add、addAll等。

#### **get(int index)** ####

ArrayList的底层是Object数组，所以ArrayList进行随机读取的速度很快，而LinkedList的底层结构决定了它在随机读取数据上比不上ArrayList。

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

可以看到，在获取元素之前会先对index进行checkElementIndex()**元素下标检查，然后再通过**node()取出相关节点，再获取到该节点中存储的数据。

checkElementIndex()
    
    
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    private boolean isElementIndex(int index) {
      return index >= 0 && index < size;
    }

在检查下标的时候，需要通过**size**来进行判断。

##### **node()** #####

Node<E> node(int 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;
            }
        }

在这里可以看到，node()方法中会**先对传入的索引参数index与LinkedList长度size/2进行比较**。如果index>=size/2，那么说明节点在LinkedList的后半段，从后往前找会更加省时；如果index<size/2，说明节点在LinkedList的前半段，从第一个节点顺序遍历，会更加容易找。

但如果这个数越靠近中间，那么get()方法遍历的时间也越长，效率也越低。而且随着LinkedList中的节点数量越来越大，get()的执行性能也会迅速下降。所以在使用LinkedList时，可以使用getFirst()、getLast()方法，直接调用类中的first和last变量。

#### **add(E e)** ####

ArrayList在将元素添加至数组中间位置的时候，需要将位置后的所有元素向后移动一位。LinkedList虽然没有随机存取的特性，但增删节点的操作比ArrayList轻松很多。我们来看看LinkedList的添加操作：

public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
    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++;
        }

从源码中可以看出LinkedList在添加元素时，会用节点的形式将数据包装起来，并利用其前后节点定义该节点，最后再根据LinkedList的last末尾节点的状态来决定此节点的位置。如果LinkedList集合为空，则该节点被设置为LinkedList对象的首节点；如果LinkedList集合不为空，则该节点被设为LinkedList对象的尾节点。

分三种情况来了解add()的节点添加情景：

1.  假如我们要向**空LinkedList**菜单集合中添加"小笼包"，则这个节点既是首节点，也是尾节点：  
    
    
    ![format_png 1][]
2.  假如我们要向**非空LinkedList**菜单集合中添加“奶黄包”，则这个节点就是尾节点last，且下一个节点next为null。  
    
    
    ![format_png 2][]
3.  加入通过add(1, “叉烧包”)这种方式将元素添加到LinkedList中，则需要找到这个下标代表的元素，并将这个元素以及该元素后的节点作为"叉烧包"节点的前后节点。

public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }

从源码中我们可以看到，在进行添加操作之前，会将传入的索引进行范围检查后，再**比较索引与当前LinkedList对象的size的大小，选择节点插入的位置**。

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

如果**索引index等于size**，则说明该节点需要放在LinkedList对象的末尾。如果**索引index不等于size**，则需要调用node()方法找到索引对应的节点，与元素一起作为调用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++;
        }

可以看到，这个过程与add(int index)的没有本区区别，都是通过建立一个新的Node节点，并且指定其prev和next来实现，**不同点在于需要调用node()来指定插入的位置，这里需要遍历链表才能获得**，也是比较耗时的一个过程。

![format_png 3][]

可以看到，在ArrayList中插入数据可能有的数组扩容和数据元素移动造成的开销，在LinkedList都不需要，所以**相比ArrayList，LinkedList的插入效率比较高**。除了add()之外，比较常用的添加方法还有addFirst()和addLast()。

### **remove(Object o)和remove(int index)** ###

在上文我们介绍了LinkedList增加节点的方法，是通过链表上节点的prev和next变量来进行节点之间的连接。所以LinkedList移除节点也是在prev和next变量中来调节点与点之间的关系。

remove(Object o)
    
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

从源码中我们可以看出，LinkedList也可以添加值为null的节点，但其实除了要判断值为null之外，两个代码块的操作是一样的，需要将所有节点遍历一遍直到确认值为入参o是否在LinkedList链表中。如果找到了，则通过unlink()方法将值为o的节点移除链表。

E unlink(Node<E> x) {
            
            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;
        }

在unlink()方法中可以看到，**在将该节点x的前节点的后指针指向x的后节点，将x的后节点的前指针指向x的前节点**，并且将x的值设为null，便于GC回收（有兴趣的读者可以了解下JVM的垃圾回收机制）。

上面这段可能有点拗口，举个栗子，假如需要将LinkedList的菜单对象中的"叉烧包"移除：

![format_png 4][]

那么需要将"小笼包"的next指针指向"奶黄包"，“奶黄包"的prev指针指向"小笼包”，并且将"叉烧包"的prev、item、next属性都设置为null。这样就可以完全移除"叉烧包"节点了。

#### **remove(int index)** ####

让我们再来看看依据索引来找到节点位置并移除节点的方法：

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

在remove(int index)方法中可以看到我们方法体中出现的方法都是上文我们提到过的，所以在此也不做赘述，简单说明下此方法的原理：先对形参索引index进行检查范围的判断之后，先通过node()方法获取在LinkedList中此索引位置的节点，然后再通过unlink()方法对此节点进行移除处理。

其实相比ArrayList，LinkedList在对节点增加、移除方面的性能要好一点，但是因为可能在寻找节点的过程中需要遍历链表才能找到所需节点，所以在获取元素方面，ArrayList还是略胜一筹。关于移除的方法，常用的还有removeFirst()、removeLast()等方法。

### **LinkedList遍历** ###

在此主要对LinkedList的三种常用的遍历方式进行介绍：

*  普通for循环
 *  增强for循环
 *  Iterator迭代器

与此同时，还会通过对LinkedList的遍历来简单介绍这三种遍历方式的性能问题。

#### **普通for循环** ####

普通for循环就是简单地将LinkedList上的每个元素都遍历出来。

public static void listForNormal(LinkedList<Integer> list){
      // 记录开始时间
      long start = System.currentTimeMillis();
      int size = list.size();
      for(int i=0;i<size;i++){
        list.get(i);
      }
      //记录用时
      long interval = System.currentTimeMillis() - start;
      System.out.println("listForNormal："+interval+" ms");
    }

#### **增强for循环遍历LinkedList** ####

所谓增强for循环遍历就是利用Java提供的语法糖，将LinkedList看成是数组，对LinkedList中的元素进行遍历。

public static void listByStrengThenFor(LinkedList<Integer> list){
        // 记录开始时间
        long start = System.currentTimeMillis();
        for (Integer i : list) { }
        // 记录用时
        long interval = System.currentTimeMillis() - start;
        System.out.println("listByStrengThenFor：" + interval + " ms");
    }

#### **迭代器遍历LinkedList** ####

既使用集合类通用的Iterator类中的迭代器进行遍历，Iterator的实现是基于迭代器模式的。

public static void listByIterator(LinkedList<Integer> list){
      // 记录开始时间
      long start = System.currentTimeMillis();
      int size = list.size();
      for(Iterator iter = list.iterator(); iter.hasNext();){
        iter.next();
      }
      //记录用时
      long interval = System.currentTimeMillis() - start;
      System.out.println("listForNormal："+interval+" ms");
    }

当我们依次调用这三种遍历方法后，其执行结果为：

listByNormalFor：1046 ms
    listByStrengThenFor：6 ms
    listByIterator：3 ms

可以看到，普通for循环的执行时间远大于普通遍历方式中使用get()方法来参与遍历过程，get()方法在上文中已经有介绍了，那么为什么增强for循环的执行时间跟迭代器遍历的执行时间相差不大呢？

我们将增强for循环LinkedList进行反编译：

private static void listByIterator(LinkedList<Integer> var0) {
        long var1 = System.currentTimeMillis();
        Iterator var3 = var0.iterator();
        while(var3.hasNext()) {
          var3.next();
        }
        long var5 = System.currentTimeMillis() - var1;
        System.out.println("listByIterator:" + var5 + " ms");
    }

可以看到，**增强for循环的内部实现依然是通过Iterator迭代器来进行遍历的**。

突然面试官打断了我。

**面试官：行了，**不错，看你讲的口干舌燥。今天的面试先到这里了，回家等消息吧。

**我：**好的。。说实话，**捋的我头皮发麻。。**

**参考资料：**

Java集合 LinkedList的原理及使用

https://www.cnblogs.com/LiaHon/p/11107245.html

***Java后端：****可能会有看官觉得，了解ArrayList和LinkedList好像用处不大，不妨做下Leetcode 的这道题，它会让你感受ArrayList和LinkedList的底层结构不同，带来的效果也会不一样：面试题62. 圆圈中最后剩下的数字。https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/*

--------------------

\-END-

如果看到这里，说明你喜欢这篇文章，请**转发****、点赞**。同时标星（置顶）本公众号可以第一时间接受到博文推送。

**《今天你面试了吗》**

***1. ***[今天你面试了吗？- Spring篇][- Spring]

***2. ***[今天你面试了吗？- MyBatis篇][- MyBatis]

***3.*** [今天你面试了吗？- ArrayList篇][- ArrayList]

![format_png 5][]

[Java]: https://blog.csdn.net/qq_37217713/article/details/101445094
[ArrayList]: https://blog.csdn.net/qq_37217713/article/details/105259955
[format_png]: /images/20210730/bc46a0ad52be466a83bca5bb69100eda.png
[Java 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e5421f979dd37205cec371412d700792bee2e992220d1b095666a524d24a05d9ff9792c1d&idx=2&mid=2247492514&scene=21&sn=c007bc36d1a6b427581937870ae8aa97#wechat_redirect
[format_png 1]: /images/20210730/d29fb20e3c7e4df18217800659e63208.png
[format_png 2]: /images/20210730/33410642de314cdcb3a43de0d76c587b.png
[format_png 3]: /images/20210730/5d9b70664c9a4351b8adf2a83a1cac16.png
[format_png 4]: /images/20210730/99c7cc74d6444334a94c3d9788955db7.png
[- Spring]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e53a9f979dabf9f42435d6ab47cc02b3e94c0c5d310f8c269159d42dc3ea4fb460add8573&idx=1&mid=2247492650&scene=21&sn=1f1fcba0db35b3803f7af4cffa90015a#wechat_redirect
[- MyBatis]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e531af979da0c58571617da71ac081b91896ee4deb999b62b0c0044de66969bdb4f6c797e&idx=1&mid=2247492761&scene=21&sn=a60e11ad0b4597cb219d22f59ad999c7#wechat_redirect
[- ArrayList]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e53b0f979daa616552ab01a47f1738a4d36f2ac027fd9b29c4066e80638beace10767c010&idx=2&mid=2247492659&scene=21&sn=6c124bdc98658c0d5c74c5f40cccc8d8#wechat_redirect
[format_png 5]: /images/20210730/c67be36ce2a1432c84148dcd7d093247.png