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

让你的笔记不会丢失!! Obsidian与gitee同步笔记教程

让你的笔记不会丢失!! Obsidian与gitee同步笔记教程

步骤大纲: - 安装git -通过git仓库设置需要传入的文件 -注册Gitee(或者Github) -新建一个仓库 -初始化本地库 -在Obsidian中安装Git插件 -设置插件 -测试即可 ---------------------------------------------------------- Obsidian是一款功能强悍的笔记软件 ,我一直再用这款软件 ,里面的关系图谱就十分的高级 ,给自己一种技术大拿的感觉 ,也是反馈非常好 ,强推这款软件!!! ----------------------------------------------------------- 设计同步的初衷: 极特殊情况:电脑突然坏了 ,笔记如果没有进行同步就丢了 ,如果记了很多内容那还是很可惜的 另外就是:我在笔记本电脑上面用的这款软件 ,但是有时候在某些场合笔记本不方便使用 ,想复习一下笔记内容就没有办法做到 ,同步以后就可以支持双端观看 ,解决了这个问题 ,复习笔记内容更久快捷 ,在不方便的场合下也可以达到复盘笔记的目的 .    因为Obsidian自带

By Ne0inhk
使用开源三件套OpenClaw+Ollama+1Panel部署7×24运行

使用开源三件套OpenClaw+Ollama+1Panel部署7×24运行

一、写在前面 本次操作教程将以开源 Linux 服务器运维面板 1Panel 为基础，搭配 Ollama 本地大模型（无需担心 Token 消耗费用），手把手教你部署 OpenClaw 个人 AI 助理，实现 7×24 小时稳定运行，轻松拥有专属智能助手！ 二、资源准备 本次 OpenCalw 本地个人 AI 助理基于一台腾讯 GPU 云服务器构建，云服务器获取过程不做赘述，参见腾讯云官网。其中服务器的配置参见如下： * 操作系统：Ubuntu Server 24.04 LTS 64 位 * 计算资源：20 核 80 G * 磁盘容量：100G

By Ne0inhk

GitHub 上开源了 30+ 个 OpenClaw 真实使用案例。

最近逛 GitHub 的时候发现了一个挺有意思的仓库，专门收集 OpenClaw 的 usecases。 说实话，很多人装完 OpenClaw 之后的操作都是一样的：疯狂往里面塞各种 Skill，ClawHub 逛得跟菜市场一样热闹，今天装个天气查询，明天装个股票分析，后天又来个翻译助手。 结果装了一堆却发现每天还是在信息搜索、做个记录。Skill 装了一百个，生活一点没变轻松。 这个开源项目就是专门收集人们真实在用的 OpenClaw 场景，而不是单纯介绍某个 Skill 或插件。 01 开源项目简介 awesome-openclaw-usecases 目前收录了 30 多个经过验证的真实使用场景。 它的核心理念非常简单：不是教你装什么 Skill，而是告诉你别人是怎么把 OpenClaw 变成真正能帮人类干活的私人助理的。 如果你不知道 OpenClaw 具体能做什么，只停留在抽象概念。有一些自动化或搭建 AI 智能体想法，但不知道如何系统落地，想参考别人已经跑通的真实工作流和自动化方案。

By Ne0inhk
Enterprise Architect 16 下载、安装与无限30天操作

Enterprise Architect 16 下载、安装与无限30天操作

文章目录 * Enterprise Architect 16 简介 * （一）支持多种建模语言和标准 * （二）强大的版本控制、协作和文档管理功能 * （三）增强的技术和用户体验 * （四）高级功能和扩展性 * 一，下载软件 * （一）官网 * （二）阿里云盘 * （三）百度网盘 * （四）迅雷 * 二，安装软件 * 三，无限30天设置 * （一）删除`fkey.dat`文件 * （二）删除注册表Kane文件夹 * （三）查看效果 Enterprise Architect 16 简介 Enterprise Architect 16是一款功能强大的企业级建模工具，它为企业和机构在系统设计、业务流程建模、数据建模以及软件开发等方面提供了全面的支持。以下是对Enterprise Architect 16的详细介绍：

By Ne0inhk