链表与LinkedList

Ne0inhk

— 11 min read
链表与LinkedList

前言

来啦来啦~ 今天和大家分享链表与LinkedList的内容,结构差不多,如果大家有了顺序表的基础接受到这一部分会更加容易,我们还是集合框架出发,开始吧

一、java集合框架

  • Java 集合框架是 Java 中用于存储和操作一组对象的体系，核心分为 Collection（单列集合）和Map（双列集合）

核心接口与分类

  • Collection（单列集合）
    • 是所有单列集合的根接口，定义了集合的基本操作（增删改查、遍历等）。
    • 子接口：List（有序可重复）、Set（无序不可重复）、Queue（队列）。
  • Map（双列集合）
    • 存储键值对（Key-Value），Key 唯一、Value 可重复。
    • 子接口：SortedMap（键有序）。
  • 咱今天就接着看LinkedList.

LinkedList

  1. 实现的接口
  • 实现了List接口（具备列表的增删改查能力）；
  • 实现了Deque接口（同时具备双端队列的特性，可作为栈、队列使用）。
  1. 核心特性
  • 结构：基于双向链表，每个节点存储前驱、后继节点的引用，无容量限制；
  • 访问效率：随机访问（通过索引get(i)）效率低（时间复杂度O(n)），需遍历链表；
  • 增删效率：在链表两端 / 已知节点附近增删元素效率高（时间复杂度O(1)）；
  • 线程不安全：多线程环境下需手动同步。

在上面的图中可以看到linkedList实现的很多接口,这也是他功能的核心部分.为了节奏的连贯性 ,我们先给出来~ 一会熟悉了基本的方法在回来看会好很多~

核心接口

List 接口

这是 LinkedList 作为列表的核心接口，它继承自 Collection 接口，定义了有序集合的基础行为。

  • 核心约定：
    元素有序可重复，支持通过索引访问如 get(int index)、set(int index, E element)；
    支持增删改查的全量列表操作，例如 add(E e)、remove(int index)、contains(Object o) 等。
  • 对 LinkedList 的影响：
    LinkedList 必须实现索引相关的方法，但由于其底层是双向链表，索引访问需要遍历链表（时间复杂度 O(n)），这也是它和 ArrayList（数组实现，索引访问 O(1)）的核心区别。

Deque 接口(后序学到栈与队列会详细说明)

这是 LinkedList 区别于 ArrayList 的关键接口，它继承自 Queue 接口（Queue 又继承自 Collection），是双端队列的核心接口。

  • 核心约定：
    允许在队列两端进行元素的插入、删除和获取操作，同时兼容队列和栈的行为：
    队列行为：遵循先进先出（FIFO），如 offer(E e)（队尾入队）、poll()（队首出队）；
    双端操作：支持队首 / 队尾双向操作，如 addFirst(E e)（队首添加）、addLast(E e)（队尾添加）、getFirst()（获取队首）、getLast()（获取队尾）；
    栈行为：遵循后进先出（LIFO），可通过 push(E e)（等效于 addFirst，入栈）、pop()（等效于 removeFirst，出栈） 实现栈功能。
  • 对 LinkedList 的影响：
    由于 LinkedList 是双向链表，天然支持首尾节点的 O(1) 时间复杂度操作，因此它是 Deque 接口的最优实现之一（比数组实现的 ArrayDeque 更适合频繁的首尾操作，且无容量限制）。

Cloneable 接口

  • 这是一个标记接口（无任何方法），用于表示该类的实例可以通过 clone() 方法实现浅拷贝。
  • 对 LinkedList 的影响：
    LinkedList 重写了 clone() 方法，调用后会创建一个新的 LinkedList 实例，新实例中的节点是新对象，但节点存储的元素是原对象的引用（即浅拷贝），若元素是可变对象，修改原对象会影响拷贝对象。

Serializable 接口

  • 同样是标记接口，用于表示类的实例可以进行序列化（将对象转化为字节流）和反序列化（字节流恢复为对象）。
  • 对 LinkedList 的影响：
    允许 LinkedList 对象在网络传输、文件持久化等场景中使用，底层会序列化链表的节点结构和元素（需保证元素也实现 Serializable，否则会抛出序列化异常）。

Iterable 接口（间接实现，通过 Collection 继承）

  • 所有集合类的顶层接口之一，定义了迭代遍历的能力。
  • 核心约定：
    实现 iterator() 方法，返回一个 Iterator 迭代器，支持对集合元素的遍历（如 hasNext()、next()、remove()）。
  • 对 LinkedList 的影响：
    LinkedList 可通过迭代器、增强 for 循环（底层依赖迭代器）遍历元素，且由于其链表结构，迭代器遍历的时间复杂度为 O(n)，但比随机索引遍历更高效。

二、链表

  • 在数据结构中，链表是用非连续的存储单元存储元素的线性表，而 Java 中的LinkedList就是顺序表的具体实现，下面从数据结构方面介绍：

数据结构中的链表

  • 节点（Node）
    链表的基本存储单元，通常包含两部分数据：
  • 数据域：存储实际的业务数据（如整数、字符串、自定义对象）；
  • 指针域：存储下一个（或上一个）节点的内存地址 / 引用，用于建立节点间的关联。
  • 头节点 / 头指针
    • 头指针：指向链表第一个节点的引用，是访问整个链表的入口；
    • 头节点（可选）：在第一个数据节点前额外添加的空节点，作用是统一链表首尾的操作逻辑（避免头节点为空的边界判断）。
  • 尾节点
    链表的最后一个节点，其指针域通常指向null（单向链表）或头节点（循环链表）。

三、常用代码手动实现

需要知道的一般的链表分为有头无头结点? 单项双向? 有无尾结点?不过大差不差.我们手动实现的为无头结点单项的链表~
熟悉了这个,其他类型的也就水到渠成!

在这里插入图片描述
  • 这一部分的逻辑是较为简单的,小伙伴们如果是第一次接触,非常建议大家上手实现一下~
    我就都分成一个一个小的代码块了 大家在学习的时候也可以分成基本成员变量,成员方法,**辅助方法(在成员方法中被调用的小方法)**进行学习

基本成员变量

staticclass listNode{publicint val;public listNode next;//构造方法实例化节点publiclistNode(int val){this.val = val;}}//定义listNode的头结点public listNode head;

基本方法

public listNode createList(){ listNode Node0=newlistNode(11); listNode Node1=newlistNode(11); listNode Node2=newlistNode(11); listNode Node3=newlistNode(11); listNode Node4=newlistNode(11);Node0.next =Node1;Node1.next =Node2;Node2.next =Node3;Node3.next =Node4; head =Node0;return head;}//头插法publicvoidaddFirst(int data){ listNode node =newlistNode(data); node.next = head; head =node;}//尾插法publicvoidaddLast(int data){ listNode node =newlistNode(data);//链表为空直接插入if(head ==null){ head = node;return;}//找到最后一个cur listNode cur = head;while(cur.next !=null){ cur = cur.next;} cur.next = node;}//任意位置插⼊,第⼀个数据节点为0号下标publicvoidaddIndex(int index,int data){//检查indexif(index <0|| index >size()){System.out.println("index不合法");}//头插入if(index ==1){addLast(data);}//尾插入if(index ==size()){addLast(data);}//中间插入 listNode cur =findIndex(index); listNode node =newlistNode(data); node.next = cur.next; cur.next = node;}public listNode findIndex(int index){ listNode cur = head;int count =0;while(count != index-1){ cur = cur.next; count++;}return cur;}//查找是否包含关键字key是否在单链表当中publicbooleancontains(int key){ listNode cur = head;while(cur !=null){if(cur.val == key){returntrue;} cur = cur.next;}returnfalse;}//删除第⼀次出现关键字为key的节点publicvoidremove(int key){// 空链表情况if(head ==null){System.out.println("空链表异常");return;}//删除第一个元素if(head.val == key){ head = head.next;return;}//处理中间部分//找到del之前的ret listNode ret =search(key);if(ret ==null){System.out.println("没有要删除元素");return;} listNode del = ret.next; ret.next = del.next;}public listNode search(int val){ listNode cur = head;while(cur.next !=null){if(cur.next.val == val){return cur;} cur = cur.next;}returnnull;}//删除所有值为key的节点publicvoidremoveAllKey(int key){//第一空链表情况if(head ==null){System.out.println("空链表异常");} listNode prev = head; listNode cur = head.next;//处理中间部分while(cur !=null){if(cur.val == key){ prev.next = cur.next;}else{ prev = cur; cur = cur.next;} cur = cur.next;}//最后处理头节点if(head.val == key){ head = head.next;}}//得到单链表的⻓度publicintsize(){int count =0; listNode cur = head;while(cur !=null){ count++; cur = cur.next;}return count;}publicvoidclear(){ listNode cur = head;while(cur !=null){ listNode Crn= cur.next;//在删除节点之前保存之后的节点//cur.val = null; //引用类型处理方法 cur.next =Crn; cur =null; cur =Crn;} head =null;}publicvoiddisplay(){ listNode cur = head;while(cur !=null){System.out.print(cur.val+" "); cur = cur.next;}System.out.println();}}

四、LinkedList使用

我们看一下java官方包中的方法

构造方法

就是两个简单的构造方法

1.无参构造器 LinkedList()

publicLinkedList(){}

无参构造器的实现非常简洁，仅初始化一个空的双向链表：
链表的 头指针（first）和尾指针（last） 默认都为 null；
链表的元素个数（size）初始化为 0；
没有预先分配任何节点或内存，链表处于完全空的状态。

2.带集合参数的LinkedList(Collection<? extends E> c)

publicLinkedList(Collection<?extendsE> c){this();// 先调用无参构造器初始化空链表addAll(c);// 将集合c中的元素批量添加到链表中}
  • 调用无参构造器：先创建一个空的双向链表；
  • 调用 addAll 方法：将传入的 Collection 集合中的元素按迭代顺序批量添加到链表尾部
  • Collection：表示这个参数必须是一个实现了 Collection 接口的对象
  • <? extends E>：表示这个集合的元素类型必须是 E 或 E 的子类
List<Integer> list1 =newLinkedList();List<Integer> list2 =newArrayList();//使用ArrayList构建LinkedListLinkedList<Integer> list3 =newLinkedList<>(list2);// List实现了Collection Integer是Integer或者子类

官方常用方法

在这里插入图片描述

在java官方是这样的双向链表

在这里插入图片描述
  • 需要注意的就是每个方法的返回类型+方法名+形参
  • 一定要动手操作一下

五、LinkedList的遍历

直接打印

System.out.println(list);

for循环

for(int i =0; i <list.size();i ++){System.out.print(list.get(i)+" ");}System.out.println(" ");for(Integer x: list){System.out.print(x +" ");}

迭代器

介绍

在 Java 集合框架中，迭代器（Iterator） 是用于遍历集合元素的统一接口，它提供了一种不依赖集合底层结构的遍历方式，核心作用是 “解耦集合与遍历逻辑”。

方法

  • 接口位置：java.util.Iterator
  • 核心方法：
    • boolean hasNext()：判断是否还有下一个元素（无元素时返回false）。
    • E next()：返回下一个元素（无元素时抛出NoSuchElementException）。
//迭代器 Iterator<Integer> iterator = list.iterator();while(iterator.hasNext()){System.out.print(iterator.next()+" ");}System.out.println(" ");ListIterator<Integer> iterator1 = list.listIterator(list.size());while(iterator1.hasPrevious()){System.out.print(iterator1.previous()+" ");}

总结

  • 到这里我的分享就先结束了~,希望对你有帮助
  • 我是dylan 下次见~
    • 无限进步

Read more

【OpenClaw从入门到精通】第10篇：OpenClaw生产环境部署全攻略：性能优化+安全加固+监控运维（2026实测版）

【OpenClaw从入门到精通】第10篇：OpenClaw生产环境部署全攻略：性能优化+安全加固+监控运维（2026实测版）

摘要：本文聚焦OpenClaw从测试环境走向生产环境的核心痛点，围绕“性能优化、安全加固、监控运维”三大维度展开实操讲解。先明确生产环境硬件/系统选型标准，再通过硬件层资源管控、模型调度策略、缓存优化等手段提升响应速度（实测响应效率提升50%+）；接着从网络、权限、数据三层构建安全防护体系，集成火山引擎安全方案拦截高危操作；最后落地TenacitOS可视化监控与Prometheus告警体系，配套完整故障排查清单和虚拟实战案例。全文所有配置、代码均经实测验证，兼顾新手入门实操性和进阶读者的生产级部署需求，帮助开发者真正实现OpenClaw从“能用”到“放心用”的跨越。 优质专栏欢迎订阅！ 【DeepSeek深度应用】【Python高阶开发：AI自动化与数据工程实战】【YOLOv11工业级实战】 【机器视觉：C# + HALCON】【大模型微调实战：平民级微调技术全解】 【人工智能之深度学习】【AI 赋能：Python 人工智能应用实战】【数字孪生与仿真技术实战指南】 【AI工程化落地与YOLOv8/v9实战】【C#工业上位机高级应用：高并发通信+性能优化】 【Java生产级避坑指南：

By Ne0inhk
ARM Linux 驱动开发篇--- Linux 并发与竞争实验（互斥体实现 LED 设备互斥访问）--- Ubuntu20.04互斥体实验

ARM Linux 驱动开发篇--- Linux 并发与竞争实验（互斥体实现 LED 设备互斥访问）--- Ubuntu20.04互斥体实验

🎬 渡水无言：个人主页渡水无言 ❄专栏传送门： 《linux专栏》《嵌入式linux驱动开发》《linux系统移植专栏》 ❄专栏传送门： 《freertos专栏》《STM32 HAL库专栏》 ⭐️流水不争先，争的是滔滔不绝  📚博主简介：第二十届中国研究生电子设计竞赛全国二等奖 |国家奖学金 | 省级三好学生 | 省级优秀毕业生获得者 | ZEEKLOG新星杯TOP18 | 半导纵横专栏博主 | 211在读研究生 在这里主要分享自己学习的linux嵌入式领域知识；有分享错误或者不足的地方欢迎大佬指导，也欢迎各位大佬互相三连 目录 前言  一、实验基础说明 1.1、互斥体简介 1.2 本次实验设计思路 二、硬件原理分析（看过之前博客的可以忽略） 三、实验程序编写 3.1 互斥体 LED 驱动代码（mutex.c） 3.2.1、设备结构体定义（28-39

By Ne0inhk
Flutter for OpenHarmony：swagger_dart_code_generator 接口代码自动化生成的救星（OpenAPI/Swagger） 深度解析与鸿蒙适配指南

Flutter for OpenHarmony：swagger_dart_code_generator 接口代码自动化生成的救星（OpenAPI/Swagger） 深度解析与鸿蒙适配指南

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 后端工程师扔给你一个 Swagger (OpenAPI) 文档地址，你会怎么做？ 1. 对着文档，手写 Dart Model 类（容易写错字段类型）。 2. 手写 Retrofit/Dio 的 API 接口定义（容易拼错 URL）。 3. 当后端修改了字段名，你对着报错修半天。 这是重复劳动的地狱。 swagger_dart_code_generator 可以将 Swagger (JSON/YAML) 文件直接转换为高质量的 Dart 代码，包括： * Model 类：支持 json_serializable，带 fromJson/

By Ne0inhk
Linux 开发别再卡壳！makefile/git/gdb 全流程实操 + 作业解析，新手看完直接用----《Hello Linux!》(5)

Linux 开发别再卡壳！makefile/git/gdb 全流程实操 + 作业解析，新手看完直接用----《Hello Linux!》(5)

文章目录 * 前言 * make/makefile * 文件的三个时间 * Linux第一个小程序－进度条 * 回车和换行 * 缓冲区 * 程序的代码展示 * git指令 * 关于gitee * Linux调试器-gdb使用 * 作业部分 前言 做 Linux 开发时，你是不是也遇到过这些 “卡脖子” 时刻？写 makefile 时，明明语法没错却报错，最后发现是依赖方法行没加 Tab；想提交代码到 gitee，记不清 git add/commit/push 的 “三板斧”，还得反复搜教程；用 gdb 调试程序，输了命令没反应，才想起编译时没加-g生成 debug 版本；甚至连写个进度条，都搞不懂\r和\n的区别，导致进度条乱跳…… 其实这些问题，

By Ne0inhk