当前位置: 首页 > news >正文

LinkedList底层原理

节点(Node)结构

LinkedList 的核心是一个内部类 Node,每个 Node 对象代表链表中的一个元素,并且每个节点包含三个部分:

  1. 元素值 (item):存储实际的数据。
  2. 前驱节点引用 (prev):指向当前节点前面的节点。
  3. 后继节点引用 (next):指向当前节点后面的节点。
    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 类维护了两个引用,分别是指向链表的头部节点和尾部节点:

  1. 头节点 (first):指向链表的第一个节点。
  2. 尾节点 (last):指向链表的最后一个节点。
  3. 长度(size)
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

链表的基本操作

        插入操作

        插入新节点时,通常需要更新相邻节点的前后指针以及链表的头尾指针。例如,插入到链表尾部的操作addLast():

  1. 创建一个新的 Node 实例。
  2. 将新节点的 prev 指向当前尾部节点。
  3. 如果链表为空,则同时设置 first 和 last 指向新节点;否则,设置当前尾部节点的 next 指向新节点,并更新 last 指向新节点。

源码: 

    public void addLast(E e) {linkLast(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;elsel.next = newNode;size++;modCount++;}

 示例:

public class LinkedListTest {public static void main(String[] args) {LinkedList<String> sites = new LinkedList<>();sites.add("Google");sites.addLast("Wiki");System.out.println(sites);}
}
        删除操作

  1. 找到要删除的节点。
  2. 更新前驱节点的 next 指针和后继节点的 prev 指针。
  3. 如果删除的是头部节点,更新 first;如果是尾部节点,更新 last

部分源码: 

    public boolean remove(Object o) {//处理null值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;}//删除操作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;}
查找操作

查找一个节点通常是从头节点开始遍历链表,直到找到目标节点或到达尾部节点。

源码:  

public int indexOf(Object o) {int index = 0;for (Node<E> x = first; x != null; x = x.next) {if (o == null ? x.item == null : o.equals(x.item))return index;++index;}return -1;
}

基于源码,他有以下特点:

  1. 快速插入和删除:
    • 插入和删除操作的时间复杂度通常为 O(1)。
    • 插入和删除操作只需要修改相邻节点的引用,而不需要移动元素。
    • 这一点与 ArrayList 不同,ArrayList 在插入或删除时可能需要移动大量元素。
  2. 随机访问相对较慢:
    • 随机访问某个位置的元素需要从头或尾开始遍历,时间复杂度为 O(n)。
    • 这是因为链表不像数组那样连续存储数据,无法直接通过索引访问元素。
  3. 允许重复元素
  4. 允许 null
  5. 线程不安全:
    • LinkedList 的基本操作(如 addgetsetremove 等)不是线程安全的。
    • 如果多个线程并发地访问或修改 LinkedList,需要外部同步机制。
  6. 所有指定位置的操作都是从头开始遍历进行的:
    对于基于索引的操作(如 get(int index) 或 set(int index, E element)),遍历会从头部开始直到到达指定的位置。
  7. 有序性:即元素的顺序保持不变,除非显式地重新排序或修改链表。
  8. 实现多种接口:

   LinkedList 实现了 ListDeque(双端队列)、Queue 等接口,因此可以作为队列、堆栈或双端队列使用。

什么时候会使用到这些接口?

使用 List 接口

如果你需要一个有序的列表,那么使用 List 接口。

例如:

  • 维护一个动态的历史记录列表:例如浏览器的历史记录,或者最近打开的文件列表。
  • 实现一个灵活的任务列表:其中任务可能被添加或移除,并且这种操作非常频繁。

使用 Queue 接口

如果你需要一个先进先出的数据结构,那么使用 Queue 接口。

例如:

  • 消息队列:处理来自客户端的消息或事件。
  • 任务队列:例如用于异步处理的作业队列,如批量处理任务、打印队列等。
  • 缓存队列:例如在内存中缓存最近访问的数据项,当队列满时移除最旧的数据项。

使用 Deque 接口

如果你需要一个可以从两端进行操作的数据结构,那么使用 Deque 接口。

例如:

  • 滑动窗口算法:在算法问题中,需要维护一个固定长度的滑动窗口,例如计算滑动窗口内的最大值或最小值。
  • 后进先出(LIFO)操作:虽然 Deque 支持 FIFO 和 LIFO 操作,但如果你需要一个简单的栈,可以使用 Deque 的相关方法。
  • 双端队列队列:例如在实现优先级队列时,你可以使用双端队列来存储不同优先级的元素。

示例代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;public class LinkedListExample {public static void main(String[] args) {// 使用 LinkedList 作为 QueueQueue<String> queue = new LinkedList<>();queue.offer("One");queue.offer("Two");System.out.println("Queue: " + queue);System.out.println("Poll from Queue: " + queue.poll());// 使用 LinkedList 作为 DequeDeque<Integer> deque = new LinkedList<>();deque.addFirst(1);deque.addLast(2);System.out.println("Deque: " + deque);System.out.println("Remove from front of Deque: " + deque.removeFirst());}
}

相关文章:

LinkedList底层原理

节点&#xff08;Node&#xff09;结构 LinkedList 的核心是一个内部类 Node&#xff0c;每个 Node 对象代表链表中的一个元素&#xff0c;并且每个节点包含三个部分&#xff1a; 元素值 (item)&#xff1a;存储实际的数据。前驱节点引用 (prev)&#xff1a;指向当前节点前面…...

CSS技巧专栏:一日一例 11 -纯CSS实现多彩渐变按钮系列特效

CSS技巧专栏:一日一例 11 -纯CSS实现多彩渐变按钮系列特效 本篇,推荐给你几个按钮,先看一下图片 本例图片 案例分析 这是一个系列的按钮,它们具有共同的特点: 底层按钮层,具有一个彩色的渐变边框,上层是依据hover效果需要,可以是渐变,可以时白色。 鼠标hover效果…...

基于微信小程序+SpringBoot+Vue的自助点餐系统(带1w+文档)

基于微信小程序SpringBootVue的自助点餐系统(带1w文档) 基于微信小程序SpringBootVue的自助点餐系统(带1w文档) 基于微信小程序的自助点餐系统前后台分离&#xff0c;让商品订单&#xff0c;用户反馈信息&#xff0c;商品信息等相关信息集中在后台让管理员管理&#xff0c;让用…...

04-Charles中的Map Remote和Map Local介绍

Charles提供了Map Remote和Map Local两个功能。 Map Remote是将指定的网络请求重定向到另一个网址。Map Local是将指定的网络请求重定向到本地文件。 一、Map Remote 假设代码中调用了接口A&#xff0c;但是接口A的响应结果不能满足需求&#xff1b;此时&#xff0c;有另一个…...

R语言优雅的进行广义可加模型泊松回归分析

泊松回归&#xff08;Poisson regression&#xff09;是以结局变量为计数结果时的一种回归分析。泊松回归在我们的生活中应用非常广泛&#xff0c;例如&#xff1a;1分钟内过马路人数&#xff0c;1天内火车站的旅客流动数&#xff0c;1天内的银行取钱人数&#xff0c;一周内的销…...

大模型学习笔记十四:Agent模型微调

文章目录 一、大模型需要Agent技术的原因二、Prompt Engineering可以实现Agent吗&#xff1f;&#xff08;1&#xff09;ReAct原理展示和代码&#xff08;2&#xff09;ModelScope&#xff08;3&#xff09;AutoGPT&#xff08;4&#xff09;ToolLLaMA 三、既然AutoGPT可以满足…...

大疆创新2025校招内推

大疆2025校招-内推 一、我们是谁&#xff1f; 大疆研发软件团队&#xff0c;致力于把大疆的硬件设备和大疆用户紧密连接在一起&#xff0c;我们的使命是“让机器有温度&#xff0c;让数据会说话”。 在消费和手持团队&#xff0c;我们的温度来自于激发用户灵感并助力用户创作…...

搜索引擎项目(四)

SearchEngine 王宇璇/submit - 码云 - 开源中国 (gitee.com) 基于Servlet完成前后端交互 WebServlet("/searcher") public class DocSearcherServlet extends HttpServlet {private static DocSearcher docSearcher new DocSearcher();private ObjectMapper obje…...

声音克隆一键本地化部署 GPT-SoVITS

文章目录 GPT-SoVITS 介绍1:GPT-SoVITS安装2:GPT-SoVITS使用2.1 人声伴奏分离,去混响去延时工具2.2 语音切分工具2.3 语音降噪工具2.4 中文批量离线ASR工具2.5 语音文本校对标注工具GPT-SoVITS 介绍 GPT-SoVITS: 是一个由RVC变声器创始人“花儿不哭”推出的免费开源项目。…...

使用【Easypoi】实现百万数据导出

本文使用easypoi实现百万级数据导出 文章目录 前言一、一般情况下导出二、解决思路三、实现步骤导入依赖重写方法调用实现 结束 前言 下文实现了通过easypoi实现将百万级数据导出 一、一般情况下导出 一般导出流程&#xff08;简单导出&#xff09;&#xff1a; 创建对应的…...

GRL-图强化学习

GRL代码解析 一、agent.py二、drl.py三、env.py四、policy.py五、utils.py 一、agent.py 这个Python文件agent.py实现了一个强化学习&#xff08;Reinforcement Learning, RL&#xff09;的智能体&#xff0c;用于在图环境&#xff08;graph environment&#xff09;中进行学习…...

昇思25天学习打卡营第22天|Pix2Pix实现图像转换

Pix2Pix图像转换学习总结 概述 Pix2Pix是一种基于条件生成对抗网络&#xff08;cGAN&#xff09;的深度学习模型&#xff0c;旨在实现不同图像风格之间的转换&#xff0c;如从语义标签到真实图像、灰度图到彩色图、航拍图到地图等。这一模型由Phillip Isola等人在2017年提出&…...

全感知、全覆盖、全智能的智慧快消开源了。

智慧快消视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。AI安全管理平台&…...

ABC364:D - K-th Nearest(二分)

题目 在一条数线上有 NQNQ 个点 A1,…,AN,B1,…,BQA1​,…,AN​,B1​,…,BQ​ &#xff0c;其中点 AiAi​ 的坐标为 aiai​ &#xff0c;点 BjBj​ 的坐标为 bjbj​ 。 就每个点 j1,2,…,Qj1,2,…,Q 回答下面的问题&#xff1a; 设 XX 是 A1,A2,…,ANA1​,A2​,…,AN​ 中最…...

hive中分区与分桶的区别

过去&#xff0c;在学习hive的过程中学习过分桶与分区。但是&#xff0c;却未曾将分区与分桶做详细比较。今天&#xff0c;回顾skew join时涉及到了分桶这一概念&#xff0c;一时间无法区分出分区与分桶的区别。查阅资料&#xff0c;特地记录下来。 一、Hive分区 1.分区一般是…...

Blender材质-PBR与纹理材质

1.PBR PBR:Physically Based Rendering 基于物理的渲染 BRDF:Bidirection Reflectance Distribution Function 双向散射分散函数 材质着色操作如下图&#xff1a; 2.纹理材质 左上角&#xff1a;编辑器类型中选择&#xff0c;着色器编辑器 新建着色器 -> 新建纹理 -> 新…...

微软的Edge浏览器如何设置兼容模式

微软的Edge浏览器如何设置兼容模式&#xff1f; Microsoft Edge 在浏览部分网站的时候&#xff0c;会被标记为不兼容&#xff0c;会有此网站需要Internet Explorer的提示&#xff0c;虽然可以手动点击在 Microsoft Edge 中继续浏览&#xff0c;但是操作起来相对复杂&#xff0c…...

SpringBoot开启多端口探究(1)

文章目录 前情提要发散探索从management.port开始确定否需要开启额外端口额外端口是如何开启的ManagementContextFactory的故事从哪儿来创建过程 management 相关API如何被注册 小结 前情提要 最近遇到一个需求&#xff0c;在单个服务进程上开启多网络端口&#xff0c;将API的…...

优化算法:2.粒子群算法(PSO)及Python实现

一、定义 粒子群算法&#xff08;Particle Swarm Optimization&#xff0c;PSO&#xff09;是一种模拟鸟群觅食行为的优化算法。想象一群鸟在寻找食物&#xff0c;每只鸟都在尝试找到食物最多的位置。它们通过互相交流信息&#xff0c;逐渐向食物最多的地方聚集。PSO就是基于这…...

ThreadLocal面试三道题

针对ThreadLocal的面试题&#xff0c;我将按照由简单到困难的顺序给出三道题目&#xff0c;并附上参考答案的概要。 1. 简单题&#xff1a;请简述ThreadLocal是什么&#xff0c;以及它的主要作用。 参考答案&#xff1a; ThreadLocal是Java中的一个类&#xff0c;用于提供线…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...