链表与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，今天 AI 热榜还有什么值得看？我把 5 个重点方向讲清楚了

除了 OpenClaw，今天 AI 热榜还有什么值得看？我把 5 个重点方向讲清楚了

🔥 个人主页：杨利杰YJlio❄️ 个人专栏：《Sysinternals实战教程》《Windows PowerShell 实战》《WINDOWS教程》《IOS教程》《微信助手》《锤子助手》《Python》《Kali Linux》《那些年未解决的Windows疑难杂症》🌟 让复杂的事情更简单，让重复的工作自动化 除了 OpenClaw，今天 AI 热榜还有什么值得看？我把 5 个重点方向讲清楚了 * 除了 OpenClaw，今天 AI 热榜还有什么值得看？我把 5 个重点方向讲清楚了 * 1. 我先说结论：今天这波 AI 热榜，最重要的不是“谁最火”，而是“风向变了” * 2. GoogleCloudPlatform / generative-ai：平台生态正在成为真正的护城河 * 3. MiroFish：群体智能和多智能体，开始从概念走向更具体的产品叙事

By Ne0inhk

QtCreator接入外部AI大模型

文章目录 * 一、概要 * 二、安装Qt5.14.2，配置高版本QtCreator * 三、下载AI插件 * 四、配置插件 * 4.1、AI大模型设置 * 4.2、自动补全配置 * 自动补全基础设置 * 模型参数设置 * 上下文设置 * 提示词设置 * Quick Refactor Settings（快速重构设置） * Ollama Settings（Ollama设置） * 4.3、聊天助手配置 * Chat Settings（聊天设置） * General Parameters（基础参数） * Advanced Parameters（高级参数） * Context Settings（上下文设置） * Ollama Settings（Ollama设置） * Chat Settings（聊天设置）

By Ne0inhk
别再手动写代码了！Claude Skills 实战，让 AI 帮你干 80% 的活！

别再手动写代码了！Claude Skills 实战，让 AI 帮你干 80% 的活！

📋 目录 1. 什么是 Claude Skills 2. 快速安装 Skills 3. 已安装的 Skills 清单 4. Skills 使用方式详解 5. 实战案例：使用 Frontend Design Skill 创建网站 6. Skill 管理最佳实践 7. 高级技巧 8. 常见问题排查 什么是 Claude Skills Claude Skills 是模块化的能力包，包含指令、元数据和可选资源（脚本、模板），让 Claude 在需要时自动加载和使用。 核心特点 * 自动触发 - 无需手动调用，Claude 会根据你的需求自动识别并使用合适的 Skill * 渐进式加载

By Ne0inhk
打造你的专属 AI 旅行管家：基于 OpenAgents 的多智能体旅游助手实战

打造你的专属 AI 旅行管家：基于 OpenAgents 的多智能体旅游助手实战

基于 OpenAgents 的多智能体旅游助手实战 在大模型与智能体（Agent）技术快速发展的今天，构建一个能理解需求、协调任务、调用工具的 AI 助手已不再是遥不可及的梦想。传统的聊天机器人往往只能被动回答问题，而现代智能体系统则具备“主动性”——它能拆解复杂目标、调用多个子模块、甚至与外部服务交互，从而完成端到端的任务。本文将带你从零开始，利用 OpenAgents 这一开源框架，搭建一个由多个专业智能体协同工作的本地旅游小助手。这个系统不仅能根据用户一句话生成完整的旅行计划、推荐个性化景点，还能逐步扩展至查询实时天气、预订酒店、规划交通等实用功能，真正实现“一句话开启智能旅行”。 一、本地启动智能体 要运行基于 OpenAgents 的智能体系统，首先需要启动其核心网络服务。该服务负责管理所有 Agent 的注册、通信和协作，是整个多智能体生态的“中枢神经系统”。 在终端中执行以下命令： openagents network start 首次运行时，OpenAgents 会自动打开浏览器，引导你完成初始化配置（

By Ne0inhk