LinkedList 分析

LinkedList 简介

LinkedList 是一个基于双向链表实现的集合类,经常被拿来和 ArrayList 做比较。关于 LinkedListArrayList的详细对比,我们 Java 集合常见面试题总结(上)有详细介绍到。

双向链表

双向链表

不过,我们在项目中一般是不会使用到 LinkedList 的,需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替,并且,性能通常会更好!就连 LinkedList 的作者约书亚 · 布洛克(Josh Bloch)自己都说从来不会使用 LinkedList

另外,不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了,LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1),其他情况增删元素的平均时间复杂度都是 O(n) 。

LinkedList 插入和删除元素的时间复杂度?

  • 头部插入/删除:只需要修改头结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
  • 尾部插入/删除:只需要修改尾结点的指针即可完成插入/删除操作,因此时间复杂度为 O(1)。
  • 指定位置插入/删除:需要先移动到指定位置,再修改指定节点的指针完成插入/删除,不过由于有头尾指针,可以从较近的指针出发,因此需要遍历平均 n/4 个元素,时间复杂度为 O(n)。

LinkedList 为什么不能实现 RandomAccess 接口?

RandomAccess 是一个标记接口,用来表明实现该接口的类支持随机访问(即可以通过索引快速访问元素)。由于 LinkedList 底层数据结构是链表,内存地址不连续,只能通过指针来定位,不支持随机快速访问,所以不能实现 RandomAccess 接口。

LinkedList 源码分析

这里以 JDK1.8 为例,分析一下 LinkedList 的底层核心源码。

LinkedList 的类定义如下:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
  //...
}

LinkedList 继承了 AbstractSequentialList ,而 AbstractSequentialList 又继承于 AbstractList

阅读过 ArrayList 的源码我们就知道,ArrayList 同样继承了 AbstractList , 所以 LinkedList 会有大部分方法和 ArrayList 相似。

LinkedList 实现了以下接口:

  • List : 表明它是一个列表,支持添加、删除、查找等操作,并且可以通过下标进行访问。
  • Deque :继承自 Queue 接口,具有双端队列的特性,支持从两端插入和删除元素,方便实现栈和队列等数据结构。需要注意,Deque 的发音为 "deck" [dɛk],这个大部分人都会读错。
  • Cloneable :表明它具有拷贝能力,可以进行深拷贝或浅拷贝操作。
  • Serializable : 表明它可以进行序列化操作,也就是可以将对象转换为字节流进行持久化存储或网络传输,非常方便。
  • LinkedList 类图

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

    初始化

    LinkedList 中有一个无参构造函数和一个有参构造函数。

    // 创建一个空的链表对象
    public LinkedList() {
    }
    
    // 接收一个集合类型作为参数,会创建一个与传入集合相同元素的链表对象
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    插入元素

    LinkedList 除了实现了 List 接口相关方法,还实现了 Deque 接口的很多方法,所以我们有很多种方式插入元素。

    我们这里以 List 接口中相关的插入方法为例进行源码讲解,对应的是add() 方法。

    add() 方法有两个版本:

  • add(E e):用于在 LinkedList 的尾部插入元素,即将新元素作为链表的最后一个元素,时间复杂度为 O(1)。
  • add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置,再修改指定节点的指针完成插入/删除,因此需要移动平均 n/2 个元素,时间复杂度为 O(n)。
  • // 在链表尾部插入元素
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    // 在链表指定位置插入元素
    public void add(int index, E element) {
        // 下标越界检查
        checkPositionIndex(index);

        // 判断 index 是不是链表尾部位置
        if (index == size)
            // 如果是就直接调用 linkLast 方法将元素节点插入链表尾部即可
            linkLast(element);
        else
            // 如果不是则调用 linkBefore 方法将其插入指定元素之前
            linkBefore(element, node(index));
    }

    // 将元素节点插入到链表尾部
    void linkLast(E e) {
        // 将最后一个元素赋值(引用传递)给节点 l
        final Node<E> l = last;
        // 创建节点,并指定节点前驱为链表尾节点 last,后继引用为空
        final Node<E> newNode = new Node<>(l, e, null);
        // 将 last 引用指向新节点
        last = newNode;
        // 判断尾节点是否为空
        // 如果 l 是null 意味着这是第一次添加元素
        if (l == null)
            // 如果是第一次添加,将first赋值为新节点,此时链表只有一个元素
            first = newNode;
        else
            // 如果不是第一次添加,将新节点赋值给l(添加前的最后一个元素)的next
            l.next = newNode;
        size++;
        modCount++;
    }

    // 在指定元素之前插入元素
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;断言 succ不为 null
        // 定义一个节点元素保存 succ 的 prev 引用,也就是它的前一节点信息
        final Node<E> pred = succ.prev;
        // 初始化节点,并指明前驱和后继节点
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 将 succ 节点前驱引用 prev 指向新节点
        succ.prev = newNode;
        // 判断前驱节点是否为空,为空表示 succ 是第一个节点
        if (pred == null)
            // 新节点成为第一个节点
            first = newNode;
        else
            // succ 节点前驱的后继引用指向新节点
            pred.next = newNode;
        size++;
        modCount++;
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/906255.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MybatisPlus入门(六)MybatisPlus-null值处理

一、MybatisPlus-null值处理 1.1&#xff09;问题引入&#xff1a; 在查询中遇到如下情况&#xff0c;有部分筛选条件没有值&#xff0c;如商品价格有最大值和最小值&#xff0c;商品价格部分时候没有值。 1.2&#xff09;解决办法&#xff1a; 步骤一&#xff1a;新建查询实…

基于树莓派的安保巡逻机器人--(一、快速人脸录入与精准人脸识别)

目录 零、前言 一、人脸检测 二、人脸识别 1、采集人脸 2、训练人脸识别模型 3、人脸识别应用 零、前言 随着智能安防需求的增长&#xff0c;基于人工智能和物联网的安保系统逐渐成为趋势。树莓派因其低成本、高扩展性等特点&#xff0c;成为很多AI项目的理想平台。本文将为大…

网络编程项目之UDP聊天室

项目要求 利用UDP协议&#xff0c;实现一套聊天室软件。服务器端记录客户端的地址&#xff0c;客户端发送消息后&#xff0c;服务器群发给各个客户端软件。 问题思考 客户端会不会知道其它客户端地址&#xff1f; UDP客户端不会直接互连&#xff0c;所以不会获知其它客户端地址…

Java-String类

字符串这个词我想同学们并不陌生&#xff0c;但Java语言中的字符串和我们之前所学习的C语言字符串&#xff0c;差别可谓是非常之大&#xff0c;因为在C语言当中&#xff0c;想要表示一个字符串&#xff0c;就只能使用字符数组或字符指针&#xff0c;但是这种" 对数据进行细…

大学生网上面试注意事项,试试白瓜面试

在数字化时代&#xff0c;大学生网上面试已成为求职过程中的一个关键环节。为了在这个虚拟舞台上留下深刻印象&#xff0c;以下是一些针对大学生网上面试的注意事项&#xff0c;同时&#xff0c;我们将探讨如何利用“白瓜面试”这一AI面试助手来提升你的面试表现。 大学生网上…

SpringBoot【实用篇】- 热部署

文章目录 目标:1.手动启动热部署2.自动启动热部署4.禁用热部署 目标: 手动启动热部署自动启动热部署热部署范围配置关闭热部署 1.手动启动热部署 当我们没有热部署的时候&#xff0c;我们必须在代码修改完后再重启程序&#xff0c;程序才会同步你修改的信息。如果我们想快速查…

【源码+文档】基于SpringBoot+Vue旅游网站系统【提供源码+答辩PPT+参考文档+项目部署】

作者简介&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流。✌ 主要内容&#xff1a;&#x1f31f;Java项目、Python项目、前端项目、PHP、ASP.NET、人工智能…

ES(2)(仅供自己参考)

Java代码的索引库&#xff1a; package cn.itcast.hotel;import lombok.AccessLevel; import org.apache.http.HttpHost; import org.elasticsearch.action.admin.indices.delete.DeleteIndexRequest; import org.elasticsearch.client.RequestOptions; import org.elasticsea…

《ToDesk云电脑vs青椒云性能测试,谁更能实现游戏自由?》

ToDesk云电脑vs青椒云性能测试 【前言】【使用云电脑的意义】【实测软件】【性能参数对比】1. 硬件配置2.游戏兼容性3. 延迟、流畅度与画面清晰度4. 用户体验5. 价格对比6. 附加功能 【游戏性能测试】《游戏一 黑悟空》《游戏二 赛博朋克 2077》《游戏三 CS反恐精英》 【本文小…

HarmonyOS开发5.0 net 启动界面设置

第一步、创建我们界面 第二步&#xff0c; 在EntryAbility中配置启动页面&#xff0c;在entry/src/main/ets/entryability/EntryAbility.ets中配置启动页面 配置如下 至此大功告成

python--函数详解二

一、作用域&#xff1a; 一个标识符的可见范围&#xff0c;这就是标识符的作用域&#xff0c;一般说的是变量的作用域 1.1、全局作用域 运行结果 在整个程序运行环境中可见。可以被多个函数重复多次使用 1.2、局部作用域 运行结果 这里调用a&#xff0c;显示未定义&#xff…

Etsy又被封号了!这次我终于搞懂了原因...

你是否真的了解在Etsy开店有哪些红线不能踩&#xff1f;你是否真的知道Etsy被封号后如何解决&#xff1f;本文我将探讨Etsy账号被封的常见原因&#xff0c;以及卖家可以采取的应对策略&#xff0c;以期减轻对跨境业务的伤害程度&#xff0c;感兴趣的商家速速码住&#xff0c;不…

大舍传媒:海外发稿的卓越选择——老挝新闻网报道及海外媒体发布服务

大舍传媒&#xff1a;海外发稿的卓越选择——老挝新闻网报道及海外媒体发布服务 在当今全球化的时代&#xff0c;信息的传播速度和范围至关重要。对于企业、组织和个人而言&#xff0c;能够在海外媒体上发布稿件&#xff0c;实现有效的宣传和推广&#xff0c;无疑是提升知名度…

如何找到网上爆款内容,快速复制扩大品牌声量

社媒内容爆款复制是现代营销中的一个重要策略&#xff0c;它对于提升品牌声量、曝光度和知名度具有显著效果。 首先什么是爆款&#xff1f; 爆款内容指的是在社交媒体或其他在线平台上迅速获得大量关注、分享和讨论的内容。 准确、及时找到这部分品牌相关的爆款内容&#xf…

在元神操作系统启动时自动执行任务脚本

1. 背景 本文主要介绍让元神操作系统启动时自动执行任务脚本的方法&#xff0c;适用于无人化任务执行目的。将任务脚本及相关的应用程序准备好之后&#xff0c;把装有元神操作系统的U盘插入目标电脑&#xff0c;然后打开电脑电源就会自动完成所设置的任务。 2. 方法 &#x…

Pandas JSON学习

1.JSON简介 JSON&#xff08;JavaScript Object Notation&#xff0c;JavaScript 对象表示法&#xff09;&#xff0c;是存储和交换文本信息的语法&#xff0c;类似 XML。JSON 比 XML 更小、更快&#xff0c;更易解析&#xff0c;Pandas 可以很方便的处理 JSON 数据。 [{"…

扫描电镜的超低温冷冻制样及传输技术(Cryo-SEM)

扫描电镜的超低温冷冻制样及传输技术(Cryo-SEM) 扫描电镜&#xff08;Scanning Electron Microscope&#xff0c;简称SEM&#xff09;是一种利用聚焦电子束扫描样品表面&#xff0c;通过检测二次电子或反射电子等信号来获取样品表面形貌信息的显微观察技术&#xff1b;然而&…

微服务设计模式 - 特性标志(Feature Flags)

微服务设计模式 - 特性标志&#xff08;Feature Flags&#xff09; 定义 特性标志&#xff08;Feature Flags&#xff09;&#xff0c;又称特性开关&#xff08;Feature Toggles&#xff09;&#xff0c;是一种常见的云计算设计模式&#xff0c;允许开发人员通过配置动态地打开…

Mac “屏幕保护程序启动或显示器关闭后需要密码“无效

屏幕保护程序启动或显示器关闭后需要密码只能选择“立即”的解决方法&#xff1a; 在 iPhone mirror中设置&#xff0c;每次询问权限。 参考&#xff1a;https://support.apple.com/en-us/120421

强势文化与弱势文化的交响:赋能认知

强势文化如同历史长河中的巨浪&#xff0c;以磅礴之力推动着社会的进步与变迁&#xff0c;其影响力深远而广泛&#xff0c;不仅塑造了民族的精神风貌&#xff0c;也深刻影响着个体的认知框架与行为模式。而弱势文化&#xff0c;则如细流涓涓&#xff0c;虽不显眼却蕴含着独特的…