首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LinkedList 源码解析

LinkedList 源码解析

原创
作者头像
HLee
修改于 2021-09-24 07:09:00
修改于 2021-09-24 07:09:00
38900
代码可运行
举报
文章被收录于专栏:房东的猫房东的猫
运行总次数:0
代码可运行

简介

LinkedList 是 Java 集合框架中一个重要的实现,其底层采用的双向链表结构。和 ArrayList 一样,LinkedList 也支持空值和重复值。由于 LinkedList 基于链表实现,存储元素过程中,无需像 ArrayList 那样进行扩容。但有得必有失,LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面,LinkedList 在链表头部和尾部插入效率比较高,但在指定位置进行插入时,效率一般。原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为O(N)。最后,LinkedList 是非线程安全的集合类,并发环境下,多个线程同时操作 LinkedList,会引发不可预知的错误。

LinkedList底层采用双向链表结构存储数据,允许重复数据和null值,长度没有限制:

每个节点用内部类Node表示:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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(前继节点)。数组内存地址必须连续,而链表就没有这个限制了,Node可以分布于各个内存地址,它们之间的关系通过prev和next维护。

LinkedList类关系图:

可以看到LinkedList类并没有实现RandomAccess接口,额外实现了Deque接口,所以包含一些队列方法。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Queue<T> queue = new LinkedList<>();
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
LinkedList包含如下成员变量:

// 元素个数,默认为0
transient int size = 0;

// 表示第一个节点,第一个节点必须满足(first == null && last == null) || (first.prev == null && first.item != null)
transient Node<E> first;

// 表示最后一个节点,最后一个节点必须满足(first == null && last == null) || (last.next == null && last.item != null)
transient Node<E> last;

方法解析

构造函数

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
空参构造函数:
public LinkedList() {
}

空参构造函数,默认size为0,每次添加新元素都要创建Node节点。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
有参构造函数:
LinkedList(Collection<? extends E> c)public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    // 循环创建节点,设置prev,next指向
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

该构造函数用于创建LinkedList,并往里添加指定集合元素。

get(int index)

LinkedList 底层基于链表结构,无法向 ArrayList 那样随机访问指定位置的元素。LinkedList 查找过程要稍麻烦一些,需要从链表头结点(或尾节点)向后查找,时间复杂度为O(N)。相关源码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 采用二分法遍历每个Node节点,直到找到index位置的节点
Node<E> node(int index) {
    
    /*
     * 则从头节点开始查找,否则从尾节点查找
     * 查找位置 index 如果小于节点数量的一半,
     */    
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 循环向后查找,直至 i == index
        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下标Node,然后获取其item属性值,节点查找需要遍历。主要是通过遍历的方式定位目标位置的节点。获取到节点后,取出节点存储的值返回即可。这里面有个小优化,即通过比较 index 与节点数量 size/2 的大小,决定从头结点还是尾节点进行查找。

set(int index, E element)

set(int index, E element)设置指定下标节点的item为指定值:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public E set(int index, E element) {
    // 下标合法性检查
    checkElementIndex(index);
    // 获取index下标节点
    Node<E> x = node(index);
    // 获取旧值
    E oldVal = x.item;
    // 设置新值
    x.item = element;
    // 返回旧值
    return oldVal;
}

// 采用二分法遍历每个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;
    }
}

可以看到,set方法也需要通过遍历查找目标节点。

插入

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/** 在链表尾部插入元素 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/** 在链表指定位置插入元素 */
public void add(int index, E element) {
    checkPositionIndex(index);

    // 判断 index 是不是链表尾部位置,如果是,直接将元素节点插入链表尾部即可
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/** 将元素节点插入到链表尾部 */
void linkLast(E e) {
    final Node<E> l = last;
    // 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空
    final Node<E> newNode = new Node<>(l, e, null);
    // 将 last 引用指向新节点
    last = newNode;
    // 判断尾节点是否为空,为空表示当前链表还没有节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;    // 让原尾节点后继引用 next 指向新的尾节点
    size++;
    modCount++;
}

/** 将元素节点插入到 succ 之前的位置 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    // 1. 初始化节点,并指明前驱和后继节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 2. 将 succ 节点前驱引用 prev 指向新节点
    succ.prev = newNode;
    // 判断尾节点是否为空,为空表示当前链表还没有节点    
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;   // 3. succ 节点前驱的后继引用指向新节点
    size++;
    modCount++;
}

代码较为简单,无非就是设置节点的prev和next关系。可以看到,除了头插和尾插外,在链表别的位置插入新节点,涉及到节点遍历操作,所以我们常说的链表插入速度快,指的是插入节点改变前后节点的引用过程很快。

核心逻辑在 linkBefore 和 linkLast 中。这里以 linkBefore 为例,它的逻辑流程如下:

  1. 创建新节点,并指明新节点的前驱和后继
  2. 将 succ 的前驱引用指向新节点
  3. 如果 succ 的前驱不为空,则将 succ 前驱的后继引用指向新节点

删除

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;
}

public E remove(int index) {
    checkElementIndex(index);
    // 通过 node 方法定位节点,并调用 unlink 将节点从链表中移除
    return unlink(node(index));
}

/** 将某个节点从链表中移除 */
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;
    
    // prev 为空,表明删除的是头节点
    if (prev == null) {
        first = next;
    } else {
        // 将 x 的前驱的后继指向 x 的后继
        prev.next = next;
        // 将 x 的前驱引用置空,断开与前驱的链接
        x.prev = null;
    }

    // next 为空,表明删除的是尾节点
    if (next == null) {
        last = prev;
    } else {
        // 将 x 的后继的前驱指向 x 的前驱
        next.prev = prev;
        // 将 x 的后继引用置空,断开与后继的链接
        x.next = null;
    }

    // 将 item 置空,方便 GC 回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

和插入操作一样,删除操作方法也是对底层方法的一层保证,核心逻辑在底层 unlink 方法中。所以长驱直入,直接分析 unlink 方法吧。unlink 方法的逻辑如下(假设删除的节点既不是头节点,也不是尾节点):

  1. 将待删除节点 x 的前驱的后继指向 x 的后继
  2. 将待删除节点 x 的前驱引用置空,断开与前驱的链接
  3. 将待删除节点 x 的后继的前驱指向 x 的前驱
  4. 将待删除节点 x 的后继引用置空,断开与后继的链接

遍历

链表的遍历过程也很简单,和上面查找过程类似,我们从头节点往后遍历就行了。但对于 LinkedList 的遍历还是需要注意一些,不然可能会导致代码效率低下。通常情况下,我们会使用 foreach 遍历 LinkedList,而 foreach 最终转换成迭代器形式。所以分析 LinkedList 的遍历的核心就是它的迭代器实现,相关代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    /** 构造方法将 next 引用指向指定位置的节点 */
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;    // 调用 next 方法后,next 引用都会指向他的后继节点
        nextIndex++;
        return lastReturned.item;
    }
    
    // 省略部分方法
}

我们都知道 LinkedList 不擅长随机位置访问,如果大家用随机访问的方式遍历 LinkedList,效率会很差。比如下面的代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
List<Integet> list = new LinkedList<>();
list.add(1)
list.add(2)
......
for (int i = 0; i < list.size(); i++) {
    Integet item = list.get(i);
    // do something
}

当链表中存储的元素很多时,上面的遍历方式对于效率来说就是灾难。原因在于,通过上面的方式每获取一个元素,LinkedList 都需要从头节点(或尾节点)进行遍历,效率不可谓不低。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
深度解析LinkedList
LinkedList是Java集合框架中List接口的实现之一,它以双向链表的形式存储元素。与传统的数组相比,链表具有更高的灵活性,特别适用于频繁的插入和删除操作。让我们从底层实现开始深入了解这个强大的数据结构。
修己xj
2023/12/26
2870
深度解析LinkedList
LinkedList 源码分析(JDK 1.8)
LinkedList 是 Java 集合框架中一个重要的实现,其底层采用的双向链表结构。和 ArrayList 一样,LinkedList 也支持空值和重复值。由于 LinkedList 基于链表实现,存储元素过程中,无需像 ArrayList 那样进行扩容。但有得必有失,LinkedList 存储元素的节点需要额外的空间存储前驱和后继的引用。另一方面,LinkedList 在链表头部和尾部插入效率比较高,但在指定位置进行插入时,效率一般。原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为O(N)。最后,LinkedList 是非线程安全的集合类,并发环境下,多个线程同时操作 LinkedList,会引发不可预知的错误。
田小波
2018/04/26
6950
LinkedList 源码分析(JDK 1.8)
LinkedList源码解析
LinkedList是一个实现了List接口和Deque接口的双端链表。LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实现了Deque接口,使得LinkedList类也具有队列的特性; LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以调用静态类Collections类中的synchronizedList方法:
黑洞代码
2021/01/28
9600
LinkedList源码解析
LinkedList源码学习
LinkedList 继承 抽象SequentialList、实现list接口,双端队列Deque以及克隆,因此具备列表、队列、双端队列的特性,可克隆。
路行的亚洲
2020/07/16
5410
Java LinkedList 简单源码分析节选
这个项目是从20年末就立好的 flag,经过几年的学习,回过头再去看很多知识点又有新的理解。所以趁着找实习的准备,结合以前的学习储备,创建一个主要针对应届生和初学者的 Java 开源知识项目,专注 Java 后端面试题 + 解析 + 重点知识详解 + 精选文章的开源项目,希望它能伴随你我一直进步!
BWH_Steven
2021/03/15
3340
LinkedList源码分析
LinkedList底层的链表结构使它支持高效的插入和删除操作,另外它实现了Deque接口,使得LinkedList类也具有队列的特性;
Vincent-yuan
2021/09/08
3910
走进 JDK 之 LinkedList
如果你了解链表的基本结构的话,LinkedList 的源码其实还是比较容易理解的。LinkedList 是基于双向链表实现的,与 ArrayList 不同的是,它在内存中不占用连续的内存空间,相连元素之间通过 “链” 来链接。对于单链表,每个节点有一个 后继指针 指向下一个节点。对于双向链表来说,除了后继指针外,它还要一个 前驱指针 指向前一个节点。那么,双向链表有什么好处呢?既然有了前驱指针,在遍历的时候就可以向前遍历,在下面的源码分析中可以看到,这是单链表所不具备的功能。
路遥TM
2021/08/31
2820
LinkedList源码解析(JDK1.8)
1 package java.util; 2 3 import java.util.function.Consumer; 4 5 /** 6 * LinkedList是List和Deque接口的双向链表的实现。实现了所有可选List操作,并允许包括null值。 7 * LinkedList既然是通过双向链表去实现的,那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效,而随机访问效率比较低。 8 * 内部方法,注释会描述为节点的操作(
武培轩
2018/04/18
9780
深入LinkedList,CopyOnWriteArrayList底层原理与源码解析
链表没有长度限制,他的内存地址不需要分配固定长度进行存储,只需要记录下一个节点的存储地址即可完成整个链表的连续。
用户8639654
2021/07/23
3150
LinkedList源码分析(基于Java8)内部结构构造方法添加2检索3删除4迭代器5 例子6总结
LinkedList是一个实现了List接口和Deque接口的双端链表 有关索引的操作可能从链表头开始遍历到链表尾部,也可能从尾部遍历到链表头部,这取决于看索引更靠近哪一端。 LinkedList不是线程安全的,如果想使LinkedList变成线程安全的,可以使用如下方式: List list=Collections.synchronizedList(new LinkedList(...)); iterator()和listIterator()返回的迭代器都遵循fail-fast机制。 从上图可以看出Lin
JavaEdge
2018/05/16
1K0
LinkedList 源码分析
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
希希里之海
2019/09/05
4500
六张图详解LinkedList 源码解析
LinkedList 底层基于链表实现,增删不需要移动数据,所以效率很高。但是查询和修改数据的效率低,不能像数组那样根据下标快速的定位到数据,需要一个一个遍历数据。
用户10384376
2023/02/26
2510
六张图详解LinkedList 源码解析
死磕Java之聊聊LinkedList源码(基于JDK1.8)
我们主要看研究一下下面的几个方法,LinkedList其他方法都是通过调用这几个方法来实现功能,包括LinkedList的双端队列的方法也是。
haifeiWu
2018/09/11
4210
死磕Java之聊聊LinkedList源码(基于JDK1.8)
LinkedList内部原理解析Header源码分析Footer
Header List 集合中,之前分析了 ArrayList ,还剩下了 LinkedList 没有分析过。那么趁着今天有空,就把 LinkedList 的内部原理来讲讲吧。 LinkedList
俞其荣
2018/05/21
6740
集合系列 List(四):LinkedList
从类继承结构图可以看到,LinkedList 不仅实现了 List 接口,还实现了 Deque 双向队列接口。
陈树义
2019/08/27
3550
集合系列 List(四):LinkedList
深入剖析LinkedList:揭秘底层原理
https://cloud.tencent.com/developer/article/2465647?shareByChannel=link
忆愿
2024/11/23
2050
深入剖析LinkedList:揭秘底层原理
LinkedList源码详解
LinkList概述 LinkedList 是 List 接口链表的实现。基于双向链表实现的方式使得 LinkedList 在插入和删除时更优于 ArrayList,而随机访问则比 ArrayList
秋白
2018/05/24
4710
(39) 剖析LinkedList / 计算机程序的思维逻辑
上节我们介绍了ArrayList,ArrayList随机访问效率很高,但插入和删除性能比较低,我们提到了同样实现了List接口的LinkedList,它的特点与ArrayList几乎正好相反,本节我们就来详细介绍LinkedList。 除了实现了List接口外,LinkedList还实现了Deque和Queue接口,可以按照队列、栈和双端队列的方式进行操作,本节会介绍这些用法,同时介绍其实现原理。 我们先来看它的用法。 用法 构造方法 LinkedList的构造方法与ArrayList类似,有两个,一个
swiftma
2018/01/31
8390
(39)  剖析LinkedList / 计算机程序的思维逻辑
【数据结构】线性表 ⑥ ( 双循环链表 | 双循环链表插入操作 | 双循环链表删除操作 | LinkedList 双循环链表源码分析 )
双循环链表 中 , 需要对 插入 / 删除 / 遍历 操作 进行特殊处理 , 因为需要调节 前驱指针 和 后继指针 两个指针 ;
韩曙亮
2023/10/11
4060
【数据结构】线性表 ⑥ ( 双循环链表 | 双循环链表插入操作 | 双循环链表删除操作 | LinkedList 双循环链表源码分析 )
Java集合:LinkedList详解
本文就LinkedList的几个主要方法展开介绍,并结合几个图片来介绍几个重要操作。
Java架构师必看
2021/05/18
5670
Java集合:LinkedList详解
相关推荐
深度解析LinkedList
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档