数据结构：链表进阶

Ne0inhk

— 11 min read
数据结构：链表进阶
在这里插入图片描述


在这里插入图片描述


链表进阶

1. ArrayList的缺陷

通过源码知道，ArrayList底层使用数组来存储元素：

publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{// ...// 默认容量是10privatestaticfinalint DEFAULT_CAPACITY =10;//...// 数组：用来存储元素transientObject[] elementData;// non-private to simplify nested class access// 有效元素个数privateint size;publicArrayList(int initialCapacity){if(initialCapacity >0){this.elementData =newObject[initialCapacity];}elseif(initialCapacity ==0){this.elementData = EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("Illegal Capacity: "+ initialCapacity);}}}// ...

由于其底层是一段连续空间，**当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，**效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

在这里插入图片描述


链表的结构就类似于火车

在这里插入图片描述


实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向

在这里插入图片描述


2. 带头或者不带头

在这里插入图片描述


3. 循环或者非循环

在这里插入图片描述


虽然有这么多的链表的结构，但是我们重点掌握两种
无头单向非循环链表：结构简单，一般不会单独用来存数据。**实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。**另外这种结构在笔试面试中出现很多

在这里插入图片描述


无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

定义一个接口：

publicinterfaceIList{//头插法publicvoidaddFirst(int data);//尾插法publicvoidaddLast(int data);//任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(int index,int data);//查找是否包含关键字key是否在单链表当中publicbooleancontains(int key);//删除第一次出现关键字为key的节点publicvoidremove(int key);//删除所有值为key的节点publicvoidremoveAllKey(int key);//得到单链表的长度publicintsize();//清空单链表publicvoidclear();//遍历单链表publicvoiddisplay();//创建单链表publicvoidcrate();}

定义一个MySIngList类：
准备工作：MySingeList要继承IList接口的所有方法

publicclassMySingeListimplementsIList{//定义单链表staticclassListNode{publicint val;publicListNode next;//next存的是下一个节点的地址，/** * 就相当于Person person=new person()，next是一个引用， * next存的是地址，next引用类型是ListNode类型的引用 */publicListNode(int val){//实例化this.val = val;}}//定义一个头结点publicListNode head;

创建一个单链表：

@Overridepublicvoidcrate(){ListNode listNode1 =newListNode(11);//如何修改当前节点位置的next的值为指定节点位置ListNode listNode5 =newListNode(22);ListNode listNode4 =newListNode(33);ListNode listNode3 =newListNode(44);ListNode listNode2 =newListNode(55); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5;this.head = listNode1;//将插入的第一个节点定义为头节点}

遍历这个单链表：

@Overridepublicvoiddisplay(){//定义一个cur，让cur去走，head不变，才能在遍历以后找到headListNode car = head.next;while(car !=null){//判断是否遍历完链表System.out.println(car.val +" "); car = car.next;//如何从当前位置走到下一个节点位置}}

头插法：

//头插法;时间复杂度：O(1)@OverridepublicvoidaddFirst(int data){ListNode listNode =newListNode(data);if(this.head ==null){this.head = listNode;}else{this.head = listNode.next;this.head = listNode;}}

不同位置添加的时间复杂度不同，常见的错误观点是认为所有添加操作都是O(1)。在尾部添加需要O(n)，头部添加为O(1)，在任意位置则平均为O(n)。了解这些有助于优化链表操作的效率。
尾插法：

//尾插法时间复杂度：O(n)@OverridepublicvoidaddLast(int data){ListNode car =this.head;ListNode listNode =newListNode(data);if(this.head ==null){this.head = listNode;}else{//找到最后一个节点while(car.next !=null){ car = car.next;}//car现在指向最后一个节点/**如果想让car停在最后一个节点的位置 cur.next！=null * 如果想把整个；链表的每一个节点都遍历完，那么就是car！=null * */ car.next = listNode;}}

在链表尾部添加（addLast()）需要从头遍历，时间复杂度为O(n)

任意位置插入,第一个数据节点为0号下标：

//随便插入privateListNodeseach(int index){ListNode car =this.head;int count =0;while(count != index -1){ car = car.next; count++;}return car;}@erridepublicvoidaddIndex(int index,int data){if(index <0|| index >size()){System.out.println("不合法");thrownewPoslllgality("插入元素下标异常"+ data);}if(index ==0){addFirst(data);return;}if(index ==size()){addLast(data);return;}ListNode car =seach(index);ListNode node =newListNode(data); node.next = car.next; car.next = node;}

当在任意位置插入的时候，要考虑的情况有很多：

  1. 当index < 0 || index > size()的时候，抛出一个异常
  2. 当index为0的时候，头插法
  3. 当index为size（）的时候，尾插法
  4. 正常的插入法

查找是否包含关键字key是否在单链表当中：

@Overridepublicbooleancontains(int key){ListNode car =this.head;while(car !=null){if(car.val == key){returnfalse;} car = car.next;}returnfalse;}

删除第一次出现关键字为key的节点：

@Overridepublicvoidremove(int key){if(this.head ==null){System.out.println("无法删除");}if(this.head.val == key){this.head =null;//或者this.head==this.head.next}ListNode car =searchprev(key);if(car ==null){System.out.println("没有要删除的数字");return;}else{ListNode del = car.next;//通过car.next找到del的位置 car.next = del.next;//然后就可以自己看懂}}//写一个方法,找到关键字看的前一个节点的地址privateListNodesearchprev(int key){ListNode car =this.head;while(car.next !=null){if(car.next.val == key){return car;} car = car.next;}returnnull;}

删除所有值为key的节点：

@OverridepublicvoidremoveAllKey(int key){if(this.head ==null){return;}ListNode prev = head;ListNode car = head.next;while(car !=null){if(car.val == key){ prev.next = car.next; car = car.next;}else{ prev = car; car = car.next;}}if(head.val == key){ head = head.next;}}

得到单链表的长度：

@Overridepublicintsize(){ListNode car = head.next;int count =0;while(car !=null){ count++; car = car.next;}return count;}

清空链表：

@Overridepublicvoidclear(){ListNode car =this.head;while(car !=null){ListNode carNext = car.next;//定义一个变量把car的next记录下/* car.val=null;如果是一个应用数据类型，那么才写这个， 如果不是car.next=null就可以清除完毕 */ car.next =null; car = carNext;} head =null;//上面的循环走完，但是head还没有置空，要手动把head置空}

3.链表面试题

  1. 删除链表中等于给定值 val 的所有节点。 力扣
  2. 反转一个单链表。 力扣
  3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。力扣
  4. 输入一个链表，输出该链表中倒数第k个结点。 牛客
  5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。力扣
  6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。力扣

4.LinkedList的使用

5.1 什么是LinkedList


LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节
点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在这里插入图片描述


在集合框架中，LinkedList也实现了List接口，具体如下：

在这里插入图片描述


【说明】

  1. LinkedList实现了List接口
  2. LinkedList的底层使用了双向链表
  3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
  4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
  5. LinkedList比较适合任意位置插入的场景

4.2 LinkedList的使用

  1. LinkedList的构造
在这里插入图片描述
publicstaticvoidmain(String[] args){// 构造一个空的LinkedListList<Integer> list1 =newLinkedList<>();List<String> list2 =newjava.util.ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE");// 使用ArrayList构造LinkedListList<String> list3 =newLinkedList<>(list2);}

LinkedList的其他常用方法介绍

在这里插入图片描述
publicstaticvoidmain(String[] args){LinkedList<Integer> list =newLinkedList<>(); list.add(1);// add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0 list.add(0,0);// add(index, elem): 在index位置插入元素elemSystem.out.println(list); list.remove();// remove(): 删除第一个元素，内部调用的是removeFirst() list.removeFirst();// removeFirst(): 删除第一个元素 list.removeLast();// removeLast(): 删除最后元素 list.remove(1);// remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif(!list.contains(1)){ list.add(0,1); list.add(1);System.out.println(list);System.out.println(list.indexOf(1));// indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1));// lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0);// get(index): 获取指定位置元素 list.set(0,100);// set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0,3);System.out.println(list);System.out.println(copy); list.clear();// 将list中元素清空System.out.println(list.size());}}
  1. LinkedList的遍历
publicstaticvoidmain(String[] args){LinkedList<Integer> list =newLinkedList<>(); list.add(1);// add(elem): 表示尾插 list.add(2); list.add(3); list.add(4); list.add(5); list.add(6); list.add(7);System.out.println(list.size());// foreach遍历for(int e:list){System.out.print(e +" ");}System.out.println();// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while(rit.hasPrevious()){System.out.print(rit.previous()+" ");}System.out.println();}

5. ArrayList和LinkedList的区别

在这里插入图片描述

Read more

Linux命名管道（FIFO）通信：从原理到实操，一文搞懂跨进程通信

Linux命名管道（FIFO）通信：从原理到实操，一文搞懂跨进程通信

🔥个人主页：Cx330🌸 ❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》 《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔 《Git深度解析》:版本管理实战全解 🌟心向往之行必能至 🎥Cx330🌸的简介： 目录 前言： 一、先搞懂：命名管道（FIFO）是什么？ 1. 命名管道的本质 2. 命名管道的核心特点 3. 命名管道与匿名管道的对比 二. 命名管道的创建方式 2.1 命令行创建（mkfifo 命令） 2.2 代码创建（mkfifo 函数） 2.3 命名管道的打开规则 三、实操实现：手搓命名管道通信 3.1 前置准备（

By Ne0inhk
Flutter 组件 injectfy 适配鸿蒙 HarmonyOS 实战：逻辑注入矩阵，构建跨模块解耦与动态依赖管理架构

Flutter 组件 injectfy 适配鸿蒙 HarmonyOS 实战：逻辑注入矩阵，构建跨模块解耦与动态依赖管理架构

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 组件 injectfy 适配鸿蒙 HarmonyOS 实战：逻辑注入矩阵，构建跨模块解耦与动态依赖管理架构 前言 在鸿蒙（OpenHarmony）生态迈向超大规模应用拆分、涉及数百个独立 Feature 模块与底层硬件服务深度解耦的背景下，如何实现灵活的“控制反转（IoC）”与“依赖注入（DI）”，已成为决定应用架构可维护性的“生命线”。在鸿蒙设备这类强调模块化挂载与 HAP/HSP 动态分发的环境下，如果应用内部的组件实例依然采用强耦合的硬编码初始化，由于由于各模块间复杂的循环依赖，极易由于由于初始化顺序错乱导致应用在流转拉起时的崩溃。 我们需要一种能够实现零成本解耦、支持单例（Singleton）与工厂（Factory）模式且具备极简注册语义的依赖注入框架。 injectfy 为 Flutter 开发者引入了轻量级的对象容器管理方案。它不仅支持对底层 Service 的全局托管，更提供了灵活的注入探测机制。在适配到鸿蒙

By Ne0inhk
一文通透OpenVLA——在Prismatic VLM(SigLIP、DinoV2、Llama 2)的架构上：基于“下一个token预测技术”预测离散化动作

一文通透OpenVLA——在Prismatic VLM(SigLIP、DinoV2、Llama 2)的架构上：基于“下一个token预测技术”预测离散化动作

前言 当对机器人动作策略的预测越来越成熟稳定之后(比如ACT、比如扩散策略diffusion policy)，为了让机器人可以拥有更好的泛化能力，比较典型的途径之一便是基于预训练过的大语言模型中的广泛知识，然后加一个policy head(当然，一开始背后的模型比较简单，比如有用LSTM或MLP——RoboFlamingo) 再之后，便出来了越来越多成熟稳定的专门的VLA模型，比如OpenVLA，再比如近期介绍过过的π0——用于通用机器人控制的VLA模型：一套框架控制7种机械臂(基于PaliGemma和流匹配的3B模型) 1. π0的意义在于，首次用同一套策略/算法操作不同机器人/机械臂，这种基于机器人大模型的「预训练-微调」模式，很快会越来越多(犹如此前大模型革命NLP 其次CV等各模态，目前到了robot领域)，算是代表了通用机器人的核心发展方向 2. 且π0 比英伟达的HOVER早一点，当然，同时期的RDT GR2也有这个潜力的，期待这两 后续的更新 一个多月前(本文首发于25年1月)，有朋友曾说，一个月内，π0 会开源来着，当时虽然觉得不太可能，但还是抱着期待，可还

By Ne0inhk