LinkedList与链表-云帆数科

一.ArrayList 的特性1. 访问效率高基于数组实现支持随机访问通过索引 get(int index)时间复杂度为 O(1)这是 ArrayList 对比 LinkedList 最核心的优势LinkedList 随机访问是 O(n)。2. 增删效率分场景尾部增删add (E e)/remove (size-1)效率高时间复杂度 O(1)无扩容时中间 / 头部增删add (int index, E e)/remove (int index)需要移动后续元素时间复杂度 O(n)效率低原因数组元素在内存中是连续存储的中间插入 / 删除会导致后续元素整体移位。3. 线程不安全ArrayList 是非线程安全的集合多线程环境下同时读写会导致数据错乱如 ConcurrentModificationException解决方案使用 Collections.synchronizedList(new ArrayList()) 包装成线程安全版本用 CopyOnWriteArrayList并发包下写操作时复制数组读写分离适合读多写少场景。4. 空值与重复元素允许存储 null 值可以通过 add(null) 添加允许存储重复元素如 add(“a”); add(“a”) 是合法的。5. Cloneable 与浅拷贝1.ArrayList 实现了 Cloneable 接口调用 clone() 方法会返回一个新的 ArrayList 实例但同样是浅拷贝2.新 ArrayList 的数组是新对象但数组中的元素引用类型仅复制引用地址示例如果 ArrayList 中存自定义类对象修改原对象会影响克隆后的 ArrayList 元素。二.链表链表的概念和结构链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的。一.链表的种类链表的种类有8种其中的主要分类可以是1.带头和不带头带头节点的实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 头结点不存储实际数据publicLinkedList(){headnewNode(-1);// 初始化头结点}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}// 删除节点publicvoiddelete(intdata){Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}不带头的链表实现classNode{intdata;Nodenext;publicNode(intdata){this.datadata;this.nextnull;}}classLinkedList{Nodehead;// 直接指向第一个有效节点publicLinkedList(){headnull;// 初始化为空}// 添加节点publicvoidadd(intdata){NodenewNodenewNode(data);if(headnull){headnewNode;}else{Nodecurrenthead;while(current.next!null){currentcurrent.next;}current.nextnewNode;}}// 删除节点publicvoiddelete(intdata){if(headnull)return;if(head.datadata){headhead.next;return;}Nodecurrenthead;while(current.next!null){if(current.next.datadata){current.nextcurrent.next.next;return;}currentcurrent.next;}}}关键区别初始化带头结点的链表初始化时创建一个虚拟头节点不带头结点的链表直接初始化为null。插入/删除操作带头结点的链表无需单独处理头节点为空的情况不带头结点的链表需要额外判断头节点是否为空。代码复杂度不带头结点的链表在操作头节点时需要更多边界条件判断带头结点的链表逻辑更统一。2.单向和双向// 单向链表节点classSinglyNode{intdata;SinglyNodenext;}// 双向链表节点classDoublyNode{intdata;DoublyNodenext;DoublyNodeprev;}复杂度对比操作单向链表双向链表插入/删除头部O1O1插入/删除尾部OnO(1)插入/删除中间部O(n)O(1)逆向遍历不支持O(n)3.循环和非循环循环的代码实现片段classNode{intdata;Nodenext;Node(intdata){this.datadata;}}非循环的代码实现片段// 创建循环链表NodeheadnewNode(1);head.nextnewNode(2);head.next.nexthead;// 尾节点指向头节点NodeheadnewNode(1);head.nextnewNode(2);// 尾节点默认next为null循环链表的尾节点指向头节点形成一个闭环结构。这种设计允许从任意节点出发遍历整个链表适用于需要循环访问的场景。非循环链表的尾节点指向null表示链表结束。遍历时需从头节点开始到达尾节点时终止结构简单且直观。二.链表中的重要方法方法作用void addFirst(int data)在头部插入数据void addLast(int data)在尾部插入数据void addIndex(int index,int data)在index位置处插入数据boolean contains(int key)判断key元素是否在链表中void remove(int key)移除链表中的第一次出现的key元素void removeAllKey(int key)移除所有的出现的key元素int size()访问数组的长度void display()打印链表的val值void clear()将链表的元素清空

企业数字化 ERP 产品动态

相关推荐

【OpenSpec 实操】把模糊需求一步步细化成可执行规范

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 18:50:34

skill-icons 技能图标速成指南：3 个 URL 参数把 GitHub 文字墙变成图标墙

skill-icons 技能图标速成指南：3 个 URL 参数把 GitHub 文字墙变成图标墙【免费下载链接】skill-icons Showcase your skills on your Github readme or resum with ease ✨ 项目地址: https://gitcode.com/gh_mirrors/sk/skill-icons 简历改好了&#xff0… · 2026/11/3 18:49:29

【系统设计（1）】系统设计入门方法论

Linux安全加固手册实战：16页清单落地与避坑指南

简介：面向Linux系统管理员、运维工程师及安全初学者的一份安全加固实践指南，聚焦操作系统层面的基线配置与风险收敛，帮助读者在服务器上线前后系统性地排查安全隐患。内容围绕安装阶段的安全设置、用户帐号与密码安全策略、密码shadowing机制… · 2026/11/3 19:37:26

Linux安全加固手册实战：用户、网络与文件系统配置避坑指南

简介：这份《LINUX安全加固手册》面向系统管理员、运维工程师及信息安全初学者，聚焦Linux主机从安装到网络服务的安全配置实践，帮助读者建立系统化的加固思路。手册以PDF形式呈现，压缩包内共1个文件，体积约40KB&#xf… · 2026/11/3 19:37:26

TortoiseGit新手入门：图形化Git操作从安装到提交推送

简介：这份资源是面向 Windows 平台 Git 初学者的 TortoiseGit 图文使用教程，以 docx 文档形式系统梳理了从环境搭建到日常协作的完整流程，帮助不熟悉命令行的用户借助右键菜单快速上手版本控制。压缩包内共 1 个 docx 文件，约 1.1… · 2026/11/3 19:37:26

TortoiseGit 使用教程：Windows 右键菜单玩转 Git 操作

简介：这份资源是面向 Windows 平台 Git 初学者的 TortoiseGit 图文使用教程，以 docx 文档形式系统梳理了从环境搭建到日常版本控制的完整流程，帮助不熟悉命令行的用户借助右键菜单快速上手 Git。压缩包内共 1 个 docx 文件，约 1.1… · 2026/11/3 19:37:26

GameBryo 2.5 引擎手册实战指南：从环境搭建到资源管线避坑

简介：GameBryo 帮助手册 PDF 版本面向游戏开发初学者与有经验的引擎使用者，针对网络上相关资料稀缺、多以 CHM 格式存在而不便移动阅读的问题，整理成便于随时查阅的 PDF 文档。资源包内共 1 个 PDF 文件，大小约 56.69MB&#xff0… · 2026/11/3 19:37:26