链表与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

腾讯扔出“王炸”｜微信变身AI超级入口：Qclaw免费内测，三步上手攻略

腾讯扔出“王炸”｜微信变身AI超级入口：Qclaw免费内测，三步上手攻略

文章目录 * 使用教程 过去，大家总觉得AI工具有门槛——要配置环境、学习指令、切换应用，繁琐得像换一台新电脑。 但现在，Qclaw把这一切彻底打破。 从下载到使用，只需三步，全程不超过3分钟。 没有复杂的设置，没有技术门槛，真正做到了“傻瓜式操作，专业级体验”。 第一步：下载安装 前往 Qclaw 官网（https://claw.guanjia.qq.com/），根据你的系统（Mac / Windows）下载安装包，一键安装，无需任何开发环境配置，耗时不到2分钟。 第二步：扫码绑定 打开电脑端 Qclaw，用微信扫描界面上的二维码，30秒内即可完成绑定。 从此，你的微信就成了Qclaw的“远程遥控器”。 第三步：发送指令 在微信里直接对Qclaw说你想做的事——无论是处理文档、操作电脑，还是执行某个具体任务，

By Ne0inhk
AI 开发必用的4个skills组合，用来流畅掌控AI开发流程 ，灵活控制AI（opencode skills）

AI 开发必用的4个skills组合，用来流畅掌控AI开发流程 ，灵活控制AI（opencode skills）

skills 一种技能增强器。 skills 可以理解为升级版的提示词，它的文件记录了某个skill（技能）的元信息，就是描述这个skills的名称等信息， 另外它的文件中还记录了skills的技能实现步骤。 以下4个skills在AI项目开发中，我认为必不可缺一。 这4个skills的引入，可更为方便我们去介入AI，控制AI，给AI制定边界。 我会用一个音乐机器人项目开发来介绍这4个skills，如何介入AI开发流程，如何行云流水的控制AI。 指令式 控制AI 开发流程的主控调度器：有4个SIKLLS 在我的项目中.opencode目录中存在4个skills， 4个skills技能结合和.opencode目录同级的AGNETS.md文档，AGNETS.md是主控配置文件， 是AI 开发流程的主控调度器，负责协调三个专业技能包（毒蛇产品经理、UI设计师、全栈开发工程师、ui-ux-pro-max） ui-ux-pro-max技能包，我120%的推荐，减少了不少UI配色的塑料感，可在文末看我此次，用技能包开发的UI界面，做一个效果对比。 skills技能指令： 我

By Ne0inhk
clawdbot无痛升级openclaw，飞书变个人AI助理保姆级教程

clawdbot无痛升级openclaw，飞书变个人AI助理保姆级教程

大家好， 我是阿星👋！ 上期我们已经教大家如何用本机+clawdbot在飞书上部署个人助理。clawdbot接入飞书阿里云，立即拥有24小时AI助理贾维斯 但是clawdbot又改名为OpenClaw了旧的已经不维护了。 新版还加了webui功能可以可视化进行配置。所以我们肯定是要升级的。 而且新版还可以比较方便安装一下下面功能，还能做功能拓展： 在新版，你可以优先勾选以下几个最实用的技能 所以，如果你想实现下面这些功能，可以跟着下面步骤升级到2026.2.9 * 📝 apple-notes / ⏰ apple-reminders : 这样你可以直接在飞书里跟机器人说“帮我记个笔记”或者“下午三点提醒我开会”。 * 🐙 github : 勾选这个可以让你通过机器人查询仓库动态或管理 Issue。 * 📸 camsnap : 很酷的功能，可以让机器人调用你 MacBook 的摄像头拍照并传给你（适合远程监控）。 * 📨 imsg : 允许机器人帮你收发 iMessage 短信。 * 🧩 clawhub : 核心组件，建议保留。 第一步：清理旧门户

By Ne0inhk
人工智能：计算机视觉高级应用与前沿发展

人工智能：计算机视觉高级应用与前沿发展

计算机视觉高级应用与前沿发展 学习目标 💡 理解计算机视觉的前沿技术和发展趋势 💡 掌握高级计算机视觉应用（如人脸识别、图像分割、图像生成） 💡 学会使用前沿计算机视觉模型（如ViT、Swin Transformer、CLIP） 💡 理解计算机视觉在多模态融合、零样本学习、少样本学习中的应用 💡 通过实战项目，开发一个高级人脸识别应用 重点内容 * 计算机视觉前沿技术和发展趋势 * 高级计算机视觉应用（人脸识别、图像分割、图像生成） * 前沿计算机视觉模型（ViT、Swin Transformer、CLIP） * 多模态融合、零样本学习、少样本学习 * 实战项目：高级人脸识别应用开发 一、计算机视觉前沿技术和发展趋势 1.1 多模态融合 1.1.1 多模态融合的基本概念 多模态融合是将不同模态的数据（如文本、图像、音频）结合起来，进行处理和分析的过程。它可以提高模型的性能和准确性。 1.

By Ne0inhk