从面试角度分析LinkedList源码

迈不过友情╰ 2021-09-18 06:22 386阅读 0赞

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

`LinkedList`类图如下：

![5dacde439dd17565a774b4c858a124ae.png][]

`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`节点只是标识了这个链表的地址。

![7f1776836482c8dabba6c52507c7ed6f.png][]

**假如链表中有元素**

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

else
        l.next = newNode;

![23b5cd775841f8c62ae3b82e9b47d017.png][]

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

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

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

![eee4845226f79adfa80f65eb634f3fe5.png][]

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

### 三 总结 ###

`LinkedList`底层是由双向链表实现的，由于是链表实现的，不仅要存放数据，还要存放指针，所以内存开销要比`ArrayList`大，删除元素不需要移动其他元素，只需要改变指针的指向，因此删除效率更高，同时它没有实现`RandomAccess`接口，因此使用迭代器遍历要比for循环更加高效。`LinkedList`也支持插入重复值和空值，同样也是线程不安全的。

点关注、不迷路

如果觉得文章不错，欢迎关注、点赞、收藏，你们的支持是我创作的动力，感谢大家。

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

[5dacde439dd17565a774b4c858a124ae.png]: /images/20210918/3193bdfdd7fa4df391286d90c31063d6.png
[7f1776836482c8dabba6c52507c7ed6f.png]: /images/20210918/857ec05bb5ac4bfda516d2bd432695cc.png
[23b5cd775841f8c62ae3b82e9b47d017.png]: /images/20210918/e753ce6865444b3faa200e34817d94b6.png
[eee4845226f79adfa80f65eb634f3fe5.png]: /images/20210918/b283e440b61640718ce323ac011d3a20.png