数据结构：链表进阶

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

Python开发从入门到精通：异步编程与协程

Python开发从入门到精通：异步编程与协程

《Python开发从入门到精通》设计指南第二十一篇：异步编程与协程 一、学习目标与重点 💡 学习目标：掌握Python异步编程的基本概念和方法，包括协程、任务调度、事件循环等；学习asyncio、aiohttp等核心库的使用；通过实战案例开发异步应用程序。 ⚠️ 学习重点：协程的定义与使用、任务调度、事件循环、asyncio库、aiohttp库、异步编程实战。 21.1 异步编程概述 21.1.1 什么是异步编程 异步编程是一种并发编程方式，通过非阻塞的操作提高程序的执行效率。在异步编程中，程序可以在等待I/O操作完成时继续执行其他任务，而不需要阻塞等待。 21.1.2 异步编程的优势 * 提高执行效率：在等待I/O操作完成时，程序可以继续执行其他任务。 * 降低资源消耗：减少了线程切换的开销。 * 简化代码结构：通过协程和任务调度，代码结构更加简洁。 21.1.3 异步编程的应用场景

By Ne0inhk
2026 Python+AI 学习方向拆解：3 个高性价比赛道，新手优先学

2026 Python+AI 学习方向拆解：3 个高性价比赛道，新手优先学

欢迎文末添加好友交流，共同进步！ “ 俺はモンキー・D・ルフィ。海贼王になる男だ！” * 前言 * 一、AI数据处理与分析赛道 * 1.1 为什么选择这个方向？ * 1.2 核心技能树 * 1.3 实战代码示例 * 数据清洗与预处理 * 1.4 学习路线图 * 二、AI应用开发赛道（LLM + RAG） * 2.1 为什么选择这个方向？ * 2.2 RAG技术架构流程 * 2.3 实战代码：构建RAG问答系统 * 2.4 学习路线图 * 三、AI自动化办公赛道 * 3.1 为什么选择这个方向？ * 3.2 自动化办公应用场景 * 3.3 实战代码示例

By Ne0inhk

你还在手动拼接JSON？Python模板化生成的3种高阶方法曝光

第一章：你还在手动拼接JSON？Python模板化生成的3种高阶方法曝光 在现代Web开发中，动态生成结构化JSON数据已成为高频需求。手动拼接字符串不仅易错，还难以维护。Python提供了多种优雅的模板化方式来自动生成JSON，提升开发效率与代码可读性。 使用Jinja2模板引擎生成JSON Jinja2不仅适用于HTML渲染，也能高效生成JSON内容。将数据结构注入模板，实现逻辑与内容分离。 # 安装：pip install jinja2 from jinja2 import Template json_template = Template(''' { "user_id": "{{ user_id }}", "username": "{{ username }}", "roles": [ {% for role in roles %}"

By Ne0inhk
Python中的“==“与“is“：深入解析与Vibe Coding时代的优化实践

Python中的“==“与“is“：深入解析与Vibe Coding时代的优化实践

🌟 Python中的"=="与"is"：深入解析与Vibe Coding时代的优化实践 * 1. 🧐 `==`与`is`的本质区别 * 2. 🕵️‍♂️ `is`判断对象身份 - 数组与常量池案例 * 案例1：列表对象的身份 * 案例2：小整数常量池 * 案例3：字符串驻留 * 3. 🔍 `==`与`__eq__`魔法函数 * 4. 🔎 类型判断的正确姿势：使用`is` * 5. 🚀 Vibe Coding时代的提示词优化 * 场景1：解释概念 * 场景2：代码生成 * 场景3：调试帮助 * 📊 对比总结表 * 💡 实际应用建议 * 🌈 结语 在Python的奇妙世界中，==和is这两个看似简单的操作符常常让初学者感到困惑。它们如同双胞胎，外表相似却性格迥异。本文将带你深入探索它们的区别，并通过生动的案例和图表展示它们的应用场景，

By Ne0inhk