JDK8：LinkedList源码分析

╰+哭是因爲堅強的太久メ 2023-06-06 03:47 22阅读 0赞

### 目录 ###

*  1.数据结构
 *  2.属性
 *  3.Node类
 *   *  结构图
     *  源码
     *  有参构造图解
 *  4.辅助方法
 *   *  （1）void linkFirst(E e)
     *   *  源码
         *  图解
     *  （2）void linkLast(E e)
     *   *  源码
         *  图解
     *  （3）void linkBefore(E e, Node< E> succ)
     *   *  源码
         *  图解
     *  （4）E unlinkFirst(Node< E> f)
     *   *  源码
         *  图解
     *  （5）E unlinkLast(Node< E> l)
     *   *  源码
         *  图解
     *  （6）E unlink(Node x)
     *   *  源码
         *  图解
     *  （7）Node< E> node(int index)
     *   *  源码

# 1.数据结构 #

LinkedList的底层数据结构是一个双向链表，但与大部分教材中的双向链表有些不同。  
![在这里插入图片描述][20191010145936364.PNG]  
详细分析可参见这篇文章：[linkedList中的双向链表JDK1.8][linkedList_JDK1.8]

# 2.属性 #

//记录LinkedList中节点的个数
    		transient int size = 0;
    		
    	    //记录第一个节点
    	    transient Node<E> first;
    
    	    //记录最后一个节点
    	    transient Node<E> last;

# 3.Node类 #

LinkedList的数据结构是一个双向链表，而链表都是由节点组成的，Node类就是描述节点的类。

## 结构图 ##

![在这里插入图片描述][20191010161443364.PNG]

## 源码 ##

private static class Node<E> {
         
    		//如上图所示
            E item;
            Node<E> next;
            Node<E> prev;
    		//有参构造，创建一个节点，比如是x，且x的prev指向prev这个节点，
    		//x的next指向next这个节点，x的item是element
            Node(Node<E> prev, E element, Node<E> next) {
        
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

## 有参构造图解 ##

在链表中插入节点的过程就是新节点与链表中节点建立链接的过程，假设要在第一个节点与第二节点之间新增一个节点。

第一步：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]  
注意：上面那个节点用虚线，代表还没有创建，准备创建。

第二步：

当我们在创建Node类时，将上图中的m和n作为初始化参数，即这样写  
Node< E> newNode = new Node<>(m, e, n); ，那么我们一次性就建立了两条链接。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 1]  
**注意**：源码中增加节点就是用的这个逻辑。之后只用再建立两条链接，这个新节点就成功插入了，到这里已经明白了大半。

# 4.辅助方法 #

void linkFirst(E e)、 void linkLast(E e)、void linkBefore(E e, Node< E> succ)、E unlinkFirst(Node< E> f)、E unlinkLast(Node< E> l)、E unlink(Node< E> x)、和Node< E> node(int index) 这七个方法是实现LinkedList核心功能的基础。

例如：

public void addFirst(E e) {
        
            linkFirst(e);
        }

public E removeFirst() {
        
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }

## （1）void linkFirst(E e) ##

方法名要做到见名知意，那个这个方法的功能是：链接到第一个

### 源码 ###

private void linkFirst(E e) {
        
    		//用f记录第一个节点
            final Node<E> f = first;
            //创建一个新的节点，且调用的是有参构造，如图一
            final Node<E> newNode = new Node<>(null, e, f);
            //fist是用来记录第一个节点的，所以要变化，如图二
            first = newNode;
            if (f == null)
            	//若f为null，代表之前链表为空，
            	//那么新增一个节点后，该节点也是最后一个节点
                last = newNode;
            else
            	//图三
                f.prev = newNode;
            //节点个数加1
            size++;
            modCount++;
        }

### 图解 ###

**数无形时少直觉**我们直接上图说明。

图一：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 2]  
图二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 3]  
图三：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 4]

## （2）void linkLast(E e) ##

链接到最后

### 源码 ###

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;
            //节点个数加1
            size++;
            modCount++;
        }

### 图解 ###

图一：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 5]  
图二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 6]  
图三：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 7]

## （3）void linkBefore(E e, Node< E> succ) ##

在succ节点前插入一个节点

### 源码 ###

void linkBefore(E e, Node<E> succ) {
        
            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;
            //节点个数加1
            size++;
            modCount++;
        }

### 图解 ###

图一：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 8]图二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 9]图三：  
![在这里插入图片描述][20191011104228219.PNG]  
**注意**：可以看出这个方法是在链表中间插入新节点的基础。

## （4）E unlinkFirst(Node< E> f) ##

解除第一个节点的链接

### 源码 ###

private E unlinkFirst(Node<E> f) {
        
            //如图一所示
            final E element = f.item;
            final Node<E> next = f.next;
            //这两行代码是方便垃圾回收器回收这个节点
            //图二
            f.item = null;
            f.next = null;
            //图三
            //first属性是用来记录链表第一个节点的，
            //当第一个节点删除后，first也要移动。
            first = next;
            if (next == null)
                last = null;
            else
            	//图四
                next.prev = null;
            //节点个数减1
            size--;
            modCount++;
            return element;
        }

### 图解 ###

图一：  
![在这里插入图片描述][20191011143940768.PNG]  
图二：  
![在这里插入图片描述][20191011143954496.PNG]  
图三：  
![在这里插入图片描述][20191011144005730.PNG]  
图四：  
![在这里插入图片描述][2019101114402927.PNG]

## （5）E unlinkLast(Node< E> l) ##

解除最后一个节点的链接

### 源码 ###

private E unlinkLast(Node<E> l) {
        
    		//下面两行代码，如图一所示
            final E element = l.item;
            final Node<E> prev = l.prev;
            //下面三行代码，如图二
            l.item = null;
            l.prev = null;
            //last属性同理first属性
            last = prev;
            if (prev == null)
                first = null;
            else
            	//图三
                prev.next = null;
            size--;
            modCount++;
            return element;
        }

### 图解 ###

图一：  
![在这里插入图片描述][20191011145340862.PNG]  
图二：  
![在这里插入图片描述][20191011145513867.PNG]  
图三：  
![在这里插入图片描述][20191011145526569.PNG]

## （6）E unlink(Node x) ##

解决链表中间节点的链接

### 源码 ###

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

### 图解 ###

图一：  
![在这里插入图片描述][2019101115135720.PNG]  
图二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 10]  
图三：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 11]

## （7）Node< E> node(int index) ##

定位方法，给出下标，帮你在链表找到这个节点

### 源码 ###

Node<E> node(int index) {
        
            //“>> 1”相当于除以2
            //这是一个优化，说明JDK底层不会从头到尾遍历的，
            //而是用二分的思想，判断更靠近第一个节点first还是last
            if (index < (size >> 1)) {
        
            	//靠近第一个节点first，就从first开始往后遍历
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
        
            	//更靠近最后一个节点last，从last开始往前遍历
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

[20191010145936364.PNG]: /images/20230601/a30e89a63bac4483b5248a591d4ede74.png
[linkedList_JDK1.8]: https://blog.csdn.net/dabusiGin/article/details/102463865
[20191010161443364.PNG]: /images/20230601/d97830d017e84f3bb717a72dab068c74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70]: /images/20230601/96376150b6fb4b1483fb1e70bcdb0f97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 1]: /images/20230601/7935a077c7614e3cb57eeea31d15e3f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 2]: /images/20230601/db9119c31d2641e7b7c1a0b666761d99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 3]: /images/20230601/9252a0f820cc421a98f7539be7227242.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 4]: /images/20230601/0bff02a1cf994b5993ca3084e97714aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 5]: /images/20230601/dd19041ad84240c684682a540e1e3df3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 6]: /images/20230601/58eb90376b7b42e09fb8f150aa4a7aeb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 7]: /images/20230601/f6e5036cb80141e88418bae70d56a122.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 8]: /images/20230601/aabd8d9c0a444200a3aa947d714ec822.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 9]: /images/20230601/67220a858726432ab2d6cf4c66962be4.png
[20191011104228219.PNG]: /images/20230601/e971efb2680f438e8bd24c8d0b5ba9b1.png
[20191011143940768.PNG]: /images/20230601/0819ffff05f34cd0bc6c205ae228dd70.png
[20191011143954496.PNG]: /images/20230601/450838f25d6b4f13b0bf030184f7f006.png
[20191011144005730.PNG]: /images/20230601/9de75754c8d94e81a9762473fd85192c.png
[2019101114402927.PNG]: /images/20230601/364493e950034a29b75b8fc8d98a4cb0.png
[20191011145340862.PNG]: /images/20230601/5ecb11cb6bdb43fc9627146488651d18.png
[20191011145513867.PNG]: /images/20230601/07856cce8ecc4166adea36ea1e046969.png
[20191011145526569.PNG]: /images/20230601/c614bf093eef43948f14ec5db858960a.png
[2019101115135720.PNG]: /images/20230601/0be6645be3f143dcb32c1003c43ec304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 10]: /images/20230601/7ffbce7f78594ed5a6750f7d214768b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhYnVzaUdpbg_size_16_color_FFFFFF_t_70 11]: /images/20230601/10646f4a5d4c4d5bbc531f47e9830daa.png