开发者社区> J3> 正文

九张图,探究 LinkedList 集合源码

简介: List 集合体系下的一个常用实现类,底层为双向链表结构,通过创建节点改变节点的前驱指针和后驱指针实现集合元素的动态改变。
+关注继续查看


1、LinkedList 简介


一个由 Node 节点组成的双向链表集合,可以存放任意元素包括 null 。


看其内部重要源代码(存储元素的结构):

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 元素个数
    transient int size = 0;
    // 头节点
    transient Node<E> first;
    // 尾节点
    transient Node<E> last;
    
    // 节点结构
    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;
        }
    }
    
    // ...
    
}


存储元素时,内部效果如图:


image.png


都说,LinkedList 集合增删快、查询慢,那这是什么依据,其内部又是如何增删元素的,这些就都是我所要分析的点,往下看吧!


2、属性分析


代码就不贴了,上面已经贴过其所有的属性了,属性不多。


  • size:链表集合中元素个数。
  • first:头结点,头插法时指向刚添加进来的元素,初始值为 null。
  • last:尾节点,头插法时指向第一个插入的元素,尾插法时指向刚插入的元素,初始值为 null。
  • Node:内部类,定义节点结构的,其内部包括三个属性:值、前驱指针、后驱指针。


注意的是,属性都被 transient 关键字修饰,说明 LinkedList 内部实现了自己的一套序列化逻辑,提高内存利用率,减少 null 值的空间占用。


3、构造器


源码:

/**
 * Constructs an empty list.
 */
public LinkedList() {
}


空构造器,说明没有默认长度,当然也不需要有默认长度,有元素就创建节点,没有就不创建。


4、头插法


顾名思义就是每次添加元素的时候都在其头部添加元素,源码如下:

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
        // 不是第一个节点,那将开始头节点指向的节点per引用指向新创建的节点
        f.prev = newNode;
    // 元素个数加一
    size++;
    // 修改次数加一
    modCount++;
}


第一次看代码可能是有点晕,毕竟是关于地址指向的问题,下面我就来分析分析。

头插法插入元素分为两种情况:


  1. 插入的元素为第一个元素
  2. 插入的元素不是第一个元素


具体分析如下:


1、插入第一个元素


初始状态,LinkedList 集合属性状态:


image.png


初始状态,头尾指针都是指向 null

下面,我根据头插法代码往集合中加入第一个元素,来程序运行的效果图:


微信图片_20220426231728.png


结合运行效果图,当使用头插法插入第一个元素结束后,头尾指针都会指向第一个添加的元素。


2、插入的不是第一个元素


那当添加的不是第一个元素,结合上图加入第二个元素,程序运行效果图如下:


微信图片_20220426231759.png


当加入第二个元素时,头节点指针指向最新添加的元素,且 first 的 next 指向前一个元素,而前一个元素的 per 指针指向 first 节点。


如此往复的通过头插法添加元素我们发现,first 永远会指向最新添加的元素,并且最新元素和前一个元素互相指引形成一个双向链表。


5、尾插法


和头插法正好相反,每次添加元素的时候都是在其尾部添加元素,源码如下:


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


也是和头插法类似,添加数据时,插入的情况有两种:


  1. 尾插法插入的元素是第一个元素。
  2. 尾插法插入的元素不是第一个元素。


具体分析:


1、插入第一个元素


通过尾插法,插入第一个元素效果图如下:


微信图片_20220426231912.png


我们可以发现,尾插法插入第一个元素时过程虽然和头插法不太一样,但最终的结果确一样,头尾指针都指向第一个元素。


2、插入不是第一个元素


那当添加的不是第一个元素,结合上图加入第二个元素,程序运行效果图如下:


微信图片_20220426231939.png


和头插法不同的是,尾插法每次添加元素都是 last 节点移动,并指向最新添加的元素。


6、移除元素


移除方法有很多重载,我就挑几个经常使用的移除方法分析。


源码一如下:

public E remove() {
    // 移除头结点指向的元素
    return removeFirst();
}

public E removeFirst() {
    // 定义中间变量 f
    final Node<E> f = first;
    // 如果头指针为 null 说明集合中就没有元素,抛错
    if (f == null)
        throw new NoSuchElementException();
    // 真正移除第一个元素
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取移除的元素值
    final E element = f.item;
    // 获取头指针的下一个元素节点
    final Node<E> next = f.next;
    // 清空要移除的元素值,利于内存回收
    f.item = null;
    f.next = null; // help GC
    // 将头指针往后移动一位
    first = next;
    // 如果集合为空,last 和 first 指向 null
    if (next == null)
        last = null;
    else
        // 如果集合中还有元素,那 first 节点 per 指针为 null
        next.prev = null;
    // 元素个数减一
    size--;
    // 修改次数加一
    modCount++;
    // 返回移除元素值
    return element;
}


remove 不带参数的移除方法就是移除集合中 first 节点指向的元素,并且 first 顺延指向下一个元素。


结合上节插入元素的链表结构,移除的大致效果图如下:


微信图片_20220426232037.png


主要功能还是 unlinkFirst 方法,将 first 头指针指向下一个元素,并将要移除的元素置空。


源码二如下:


public E remove(int index) {
    // 检查下标,如果下标不在 size 范围内,报错
    checkElementIndex(index);
    // 获取下标指定的节点,并开始移除
    return unlink(node(index));
}
// 找到下标对应的节点
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 判断下标更靠近头结点还是尾节点
    if (index < (size >> 1)) {
        // 靠近头结点
        // 遍历,找到下标为 index 的节点返回
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        // 靠近尾节点
        // 遍历,找到下标为 index 的节点返回
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return 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 {
        // 不是头结点
        // 前驱节点的 next 指向要移除节点的后驱节点
        prev.next = next;
        // 移除节点的 per 置空
        x.prev = null;
    }

    if (next == null) {
         // 移除的是尾结点,尾结点向前指一位
        last = prev;
    } else {
        // 不是尾结点
        // 将要移除的后驱节点 per 指向要移除节点的 前驱节点
        next.prev = prev;
        // 移除节点的 next 置空
        x.next = null;
    }
    // 移除节点值置空
    x.item = null;
    // 大小减一
    size--;
    // 修改次数加一
    modCount++;
    // 返回移除元素的值
    return element;
}


结合代码,根据下标移除元素的逻辑并不是很复杂,我总结出如下实现步骤:


  1. 检查下标是否在 size 范围内
  2. 根据下标,找到移除的节点
  3. 将节点移除链表,并将链表的前驱指针和后驱指针链接正确


大体上就是这三步,难点应该就是第三步,节点移除,指针指向问题,下面我再来画个移除图,便于理解。


微信图片_20220426232201.png


源码三如下:

public boolean remove(Object o) {
    // 是否移除 null 值
    if (o == null) {
        // 移除第一个碰到的 null 元素
        for (Node<E> x = first; x != null; x = x.next) {
            // 遍历,找到第一个为 null 值得 节点
            if (x.item == null) {
                // 调用 源码二 分析的 unLink 方法,移除节点
                unlink(x);
                return true;
            }
        }
    } else {
        // 移除第一个碰到的 o 元素
        for (Node<E> x = first; x != null; x = x.next) {
            // 比较节点值是否和要移除的节点值相等
            if (o.equals(x.item)) {
                 // 调用 源码二 分析的 unLink 方法,移除节点
                unlink(x);
                return true;
            }
        }
    }
     // 没找到要移除的值,返回 false
    return false;
}


根据值移除元素,底层的实现逻辑就可以看出来,LinkedList 是可以存储 null 值的。


而且移除思路也是先变量一遍链表找到要移除的元素,再调用移除节点的方法进行移除(该方法在上面讲过),成功移除返回true,反之 false。


7、添加方法


上面分析了头插法和尾插法,那我们就来看看 LinkedList 集合是如何添加元素的了,看源码:


public boolean add(E e) {
    // 默认尾插法添加元素
    linkLast(e);
    return true;
}


前面分析了尾插法,现在看到 add 源码其底层就是通过调用尾插法的方法来添加元素,这也是集合元素有序性的原因。


通常我们也会调用下面方法,在指定的下标处添加元素,方法源码如下:


public void add(int index, E element) {
    // 检查下标是否在 size 范围内
    checkPositionIndex(index);
    // 如果就添加在 尾部,那直接使用尾插法
    if (index == size)
        linkLast(element);
    else
        // 不在尾部那就插在 index 下标指向的 node 节点之前
        linkBefore(element, node(index));
}
// 元素,插在 succ 节点之前
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 定义中间遍历,获取 succ 节点的 per 指向的节点
    final Node<E> pred = succ.prev;
    // 创建要插入的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将 succ 的 per 指向 新创建的 节点
    succ.prev = newNode;
    // 是否是插在头结点前
    if (pred == null)
        // 是,那就把 first 指针指向新创建的节点
        first = newNode;
    else
        // 否,将开始 succ 节点 per 指向的前驱节点的 next 指向 新创建的 节点
        pred.next = newNode;
    // 元素个数加一
    size++;
    // 修改次数加一
    modCount++;
}


结合源码,在指定下标处添加元素,首先会检查下标是否在 size 范围内,然后会根据下标获取到对应位置的元素节点,最后才是插入元素。

linkBefore 方法看字面意思就知道,在指定节点之前插入元素,下面就根据该方法画出对应的运行效果图:


微信图片_20220426232336.png


指定下标插入元素的重要步骤就是搞清楚 next 及 per 指针的指向问题。例如本次案例就是先将 e 节点的 per 指向 e3 、next 指向 e2 节点,然后再把 e3 的 next 和 e2 的 per 指向 e 节点即完成一次元素的插入。


8、清空方法


LinkedList 清空方法源码如下:

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    // 从头结点开始循环遍历集合
    for (Node<E> x = first; x != null; ) {
        // 中间变量,定义下一个元素节点 
        Node<E> next = x.next;
        // 将当前节点置空
        x.item = null;
        x.next = null;
        x.prev = null;
        // 继续操作下一个节点
        x = next;
    }
    // 头尾指针指向 null 表示集合为空
    first = last = null;
    // size 大小
    size = 0;
    // 修改次数加一
    modCount++;
}


清空方法很简单,就是从头结点挨个遍历置空,最后将头尾指针指向 null 并修改 size 大小即可。


9、源码分析总结


经过了很长的源码分析篇幅,基本上吧 LinkedList 中比较基础的方法都过了一遍,那我针对这些源码概括一下 LinkedList 的几个特性:


  1. 底层使用 Node 节点形式存储数据
  2. first 、last 两个节点指针分别指向链表的两头
  3. first 、last 都指向 null 时表示为空集合
  4. 添加元素时,头插法和尾插法的时间复杂度都是O(1)
  5. 删除元素时,时间复杂度是O(1)
  6. 访问元素时,如果不是头尾节点,时间复杂度是O(n)
  7. 内部没有初始容量,所以不会有扩容现象
  8. 内部没有锁机制,是一个线程不安全的集合


好了,今天的内容到这里就结束了,关注我,我们下期见。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
27723 0
【Java入门提高篇】Day21 Java容器类详解(四)ArrayList源码分析
 今天要介绍的是List接口中最常用的实现类——ArrayList,本篇的源码分析基于JDK8,如果有不一致的地方,可先切换到JDK8后再进行操作。   本篇的内容主要包括这几块:   1.
1092 0
ArrayList源码解析(基于Java8)
首先:执行List list1 = new ArrayList(); 在堆内存开辟了一块空间,既然是new出来的,那我们直接从构造函数入手 Object[]数组,也就是说该数组可以放任何对象(所有对象都继承自父类Object) 继续,执行list1.
961 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
19980 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23523 0
LinkedList源码浅析
LinkedList使用频率相较`ArrayList`不高,但也值得探讨一下。适合集合高频次修改时采用。
64 0
ArrayList源码分析(基于JDK1.6)
不积跬步,无以至千里;不积小流,无以成江海。从基础做起,一点点积累,加油!     《Java集合类》中讲述了ArrayList的基础使用,本文将深入剖析ArrayList的内部结构及实现原理,以便更好的、更高效的使用它。
512 0
❤️用武侠小说的形式来阅读LinkedList的源码,绝了!(1)
❤️用武侠小说的形式来阅读LinkedList的源码,绝了!
38 0
Redis 源码分析列表对象(z_list)
Redis 源码分析列表对象(z_list)
14 0
+关注
J3
不必遗憾。若是美好,叫做精彩。若是糟糕,叫做经历。
67
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载