当前位置:首页 > > 架构师社区
[导读]LinkedList底层是由双向链表实现的。链表好比火车,每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针,还有指向上一个节点的指针。

注:本系列文章中用到的jdk版本均为java8

LinkedList类图如下:

从面试角度分析LinkedList源码

LinkedList底层是由双向链表实现的。链表好比火车,每节车厢包含了车厢和连接下一节车厢的连接点。而双向链表的每个节点不仅有指向下一个节点的指针,还有指向上一个节点的指针。
LinkedList源码中有一个Node静态类,源码如下:

private static class Node<E{
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node 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 first;

/**
  * 尾结点的指针.
  * Invariant: (first == null && last == null) ||
  *            (last.next == null && last.item != null)
  */

transient Node 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 l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

我们来画张图演示一下如何给链表尾部插入元素:

假如链表中没有元素

对应源码中的if语句,如果没有元素则新增的这个节点为链表中唯一的一个元素,既是首节点,又是尾结点,前一个元素的指针和后一个元素的指针都是null。这里注意head节点不是第一个节点,head节点只是标识了这个链表的地址。

从面试角度分析LinkedList源码

假如链表中有元素

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

else
    l.next = newNode;

从面试角度分析LinkedList源码

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

1.2 头部插入元素

linkFirst()源码如下:

private void linkFirst(E e) {
    final Node f = first;
    final Node 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 node(int index) {
    // assert isElementIndex(index);
    // 如果指定下标 < 一半元素数量,则从首结点开始遍历
    // 否则,从尾结点开始遍历
    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

unlink(Node x)源码如下:

unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node 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;
}

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

从面试角度分析LinkedList源码

  1. 假设删除的是第一个元素:则它的prev==NULL,我们需要将他的后一个元素(图中的second)作为第一个元素

  2. 假设删除的是最后一个元素,则它的next==null,我们需要将他的前一个元素(图中的second)作为最后一个元素

  3. 如果是中间的任意元素,则需要将它的前一个元素的next指针指向它的后一个元素,同时将它的后一个元素的prev指针指向它的前一个元素。

三、总结

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

特别推荐一个分享架构+算法的优质内容,还没关注的小伙伴,可以长按关注一下:

从面试角度分析LinkedList源码

从面试角度分析LinkedList源码

从面试角度分析LinkedList源码

长按订阅更多精彩▼

从面试角度分析LinkedList源码

如有收获,点个在看,诚挚感谢

免责声明:本文内容由21ic获得授权后发布,版权归原作者所有,本平台仅提供信息存储服务。文章仅代表作者个人观点,不代表本平台立场,如有问题,请联系我们,谢谢!

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: 驱动电源

在工业自动化蓬勃发展的当下,工业电机作为核心动力设备,其驱动电源的性能直接关系到整个系统的稳定性和可靠性。其中,反电动势抑制与过流保护是驱动电源设计中至关重要的两个环节,集成化方案的设计成为提升电机驱动性能的关键。

关键字: 工业电机 驱动电源

LED 驱动电源作为 LED 照明系统的 “心脏”,其稳定性直接决定了整个照明设备的使用寿命。然而,在实际应用中,LED 驱动电源易损坏的问题却十分常见,不仅增加了维护成本,还影响了用户体验。要解决这一问题,需从设计、生...

关键字: 驱动电源 照明系统 散热

根据LED驱动电源的公式,电感内电流波动大小和电感值成反比,输出纹波和输出电容值成反比。所以加大电感值和输出电容值可以减小纹波。

关键字: LED 设计 驱动电源

电动汽车(EV)作为新能源汽车的重要代表,正逐渐成为全球汽车产业的重要发展方向。电动汽车的核心技术之一是电机驱动控制系统,而绝缘栅双极型晶体管(IGBT)作为电机驱动系统中的关键元件,其性能直接影响到电动汽车的动力性能和...

关键字: 电动汽车 新能源 驱动电源

在现代城市建设中,街道及停车场照明作为基础设施的重要组成部分,其质量和效率直接关系到城市的公共安全、居民生活质量和能源利用效率。随着科技的进步,高亮度白光发光二极管(LED)因其独特的优势逐渐取代传统光源,成为大功率区域...

关键字: 发光二极管 驱动电源 LED

LED通用照明设计工程师会遇到许多挑战,如功率密度、功率因数校正(PFC)、空间受限和可靠性等。

关键字: LED 驱动电源 功率因数校正

在LED照明技术日益普及的今天,LED驱动电源的电磁干扰(EMI)问题成为了一个不可忽视的挑战。电磁干扰不仅会影响LED灯具的正常工作,还可能对周围电子设备造成不利影响,甚至引发系统故障。因此,采取有效的硬件措施来解决L...

关键字: LED照明技术 电磁干扰 驱动电源

开关电源具有效率高的特性,而且开关电源的变压器体积比串联稳压型电源的要小得多,电源电路比较整洁,整机重量也有所下降,所以,现在的LED驱动电源

关键字: LED 驱动电源 开关电源

LED驱动电源是把电源供应转换为特定的电压电流以驱动LED发光的电压转换器,通常情况下:LED驱动电源的输入包括高压工频交流(即市电)、低压直流、高压直流、低压高频交流(如电子变压器的输出)等。

关键字: LED 隧道灯 驱动电源
关闭