[数据结构] 链表

目录

1.链表的基本概念

2.链表的实现 -- 节点的构造和链接

        节点如何构造?

        如何将链表关联起来?

3.链表的方法(功能)

1).display() -- 链表的遍历

2).size() -- 求链表的长度

3).addFirst(int val) -- 头插法

4).addLast(int val) -- 尾插法

5).addIndex -- 在任意位置插入

6).contains(int val) -- 链表中是否包含某个元素

7). remove(int key) -- 删除第一次出现的关键字的节点

8).removeAll(int val) -- 删除所有出现的关键字的节点

9).clear() -- 清空

        回收对象,防止浪费 : head == null;



1.链表的基本概念

  • 链表(Linked List)是一种常见的基础数据结构,它由一系列节点(Node)组成,每个节点包含两部分:一部分存放数据元素,另一部分存放指向下一个节点的指针.

2.链表的实现 -- 节点的构造和链接

        节点如何构造?

在 Java 中,通常通过定义一个类来表示链表中的节点。每个节点通常包含两个部分:数据域和指针域。对于单向链表,每个节点的指针域指向下一个节点.

public class LinkedList {// 定义链表节点static class ListNode {int val; // 数据域ListNode next; // 指针域ListNode(int x) {this.val = x;this.next = null;}}public ListNode head;
}

        如何将链表关联起来?

通过访问node1的指针域next,将其赋值为下一个节点的地址,以此类推,最后让头节点head指向第一个节点node1.

        node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;

3.链表的方法(功能)

1).display() -- 链表的遍历

首先,我们创建一个名为 cur 的局部变量,它是一个指向 ListNode 类型的引用。将链表的头节点(head)赋值给 cur,这样我们就有了一个可以用来遍历整个链表的起始点.使用 while 循环来遍历链表。只要 cur不是 null(即还没有到达链表的末尾),就继续执行循环体内的代码。如果 cur 是 null,则说明已经到了链表的末尾,循环结束。在循环体内,我们使用 System.out.print 来打印当前节点的数据。这里用 + " -> " 格式化输出,以箭头分隔各个数据项,直观地表示出它们之间的链接关系。更新 cur指针,使其指向下一个节点(通过 cur.next 获取)。这一步非常重要,因为它确保了我们在下一次迭代时能够访问链表中的下一个节点。当循环结束后,我们额外打印一个 null,表示链表的终止。这是为了更清晰地展示链表结构,表明没有更多的节点了。

public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + "->");cur = cur.next;}System.out.println("null");}

2).size() -- 求链表的长度

        定义count变量,记录cur向后走的次数,每走一步,count++

public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}

3).addFirst(int val) -- 头插法

        1. 将head头节点的地址传给node.next  2. 然后让head指向node

        注意: 这里两步的顺序不可以交换 , 否则 就是自己指向自己了

public void addFirst(int val) {ListNode node = new ListNode(val);node.next = head;head = node;}

4).addLast(int val) -- 尾插法

        1.为了避免head == null 报错, 先进行判断,若head == null , 则 head = node,然后return掉.

        2.若head != null , 则 这通过循环找到 cur.next == null ,最后让cur.next = node.

public void addLast(int val) {ListNode node = new ListNode(val);if(head == null) {head = node;return;}ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = node;}

5).addIndex -- 在任意位置插入

1.判断index的合法性: (1). 定义一个 checkIndex(int index) 方法用来检查 index 的合法性

2.index == 0 || index == size();前者相当于是头插,直接调用 addFirst(),后者相当于是尾插,直接调用 addLast()

3.找到 index 的前一个位置,创建一个 findIndexSubOne(int index) 方法,创建一个节点 cur 来接收调用方法的返回值, 最后 cur 就是 index 位置的前一个节点了

4.进行连接,实例化一个所带数据为 val 的节点 node,

node.next = cur.next;

cur.next = node;

public void addIndex(int index,int val) {// 1.判断index的合法性try {checkIndex(index);} catch(IndexNotLegalException e) {e.printStackTrace();}// index == 0 || index == size()if(index == 0) {addFirst(val);return;} else if(index == size()) {addLast(val);return;}// 3.找到index前一个位置ListNode cur = findIndexSubOne(index);// 4.进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}public ListNode findIndexSubOne(int index) {ListNode cur = head;for (int i = 0; i < index - 1; i++) {cur = cur.next;}return cur;}public void checkIndex(int index) {if(index < 0 || index >size()) {throw new IndexNotLegalException("index位置不合法");}}public class IndexNotLegalException extends RuntimeException {public IndexNotLegalException() {}public IndexNotLegalException(String message) {super(message);}}

6).contains(int val) -- 链表中是否包含某个元素

遍历链表,如果能在链表中找到val,则返回true,否则,返回false

public boolean contains(int val) {ListNode cur = head;while(cur != null) {if(cur.val == val) {return true;}cur = cur.next;}return false;}

7). remove(int key) -- 删除第一次出现的关键字的节点

        1.首先判断链表是否为空

        2.循环遍历 : cur.next != null

        3.找到val值的前一个节点cur : 当cur.next.val = val 时,找到目标

        4.进行删除

        

public void remove(int key) {// 如果链表为空if(head == null) {return;}// 如果第一个元素就为val时if(head.val == key) {head = head.next;return;}ListNode cur = head;while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;return;}cur = cur.next;}}

8).removeAll(int val) -- 删除所有出现的关键字的节点

  • 定义两个引用变量
    • cur 代表当前需要删除的节点
    • prev 代表当前需要删除节点的前驱
  1. 若 cur.val == val
    1. prev.next = cur.next
    2. cur = cur.next
  2. 否则:
    1. prev = cur
    2. cur = cur.next
  3. 处理头节点
public void removeAll(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}// 除了头节点都删除完成if(head.val == key) {head = head.next;}}

9).clear() -- 清空

        回收对象,防止浪费 : head == null;

public void clear() {this.head = null;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/493444.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

springmvc的拦截器,全局异常处理和文件上传

拦截器: 拦截不符合规则的&#xff0c;放行符合规则的。 等价于过滤器。 拦截器只拦截controller层API接口。 如何定义拦截器。 定义一个类并实现拦截器接口 public class MyInterceptor implements HandlerInterceptor {public boolean preHandle(HttpServletRequest reque…

RestTemplate远程调用、服务注册、

一.RestTemplate Spring给我们提供了一个RestTemplate的API&#xff0c;可以方便的实现Http请求的发送。 同步客户端执行HTTP请求&#xff0c;在底层HTTP客户端库(如JDK HttpURLConnection、Apache HttpComponents等)上公开一个简单的模板方法API。RestTemplate通过HTTP方法为常…

台球助教平台系统开发APP和小程序信息收藏功能需求解析(第十二章)

以下是开发台球助教系统客户端&#xff08;APP&#xff0c;小程序&#xff0c;H5&#xff09;几端的信息收藏功能的详细需求和功能说明&#xff0c;内容比较详细&#xff0c;可以说是一个教科书式的详细说明了&#xff0c;这套需求说明不仅仅用在我们的台球助教系统程序上&…

React系列(八)——React进阶知识点拓展

前言 在之前的学习中&#xff0c;我们已经知道了React组件的定义和使用&#xff0c;路由配置&#xff0c;组件通信等其他方法的React知识点&#xff0c;那么本篇文章将针对React的一些进阶知识点以及React16.8之后的一些新特性进行讲解。希望对各位有所帮助。 一、setState &am…

【开源免费】基于SpringBoot+Vue.JS房屋租赁管理系统(JAVA毕业设计)

本文项目编号 T 091 &#xff0c;文末自助获取源码 \color{red}{T091&#xff0c;文末自助获取源码} T091&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…

netcore 集成Prometheus

一、安装包 <ItemGroup><PackageReference Include"prometheus-net" Version"8.2.1" /><PackageReference Include"prometheus-net.AspNetCore" Version"8.2.1" /> </ItemGroup> 二、添加代码 #region Pro…

CLION中运行远程的GUI程序

在CLION中运行远程GUI程序&#xff0c;很有可能会遇到下面错误 Gtk-WARNING **: cannot open display: 这是因为远程的GUI程序不能再本地机器上显示。这个问题一般有两种解决方法 通过SSH的ForwardX11的方法&#xff0c;就是将远程的GUI程序显示到本地机器上&#xff0c;一般在…

datasets 笔记:加载数据集(基本操作)

参考了huggingface的教程 1 了解数据集基本信息&#xff08; load_dataset_builder&#xff09; 在下载数据集之前&#xff0c;通常先快速了解数据集的基本信息会很有帮助。数据集的信息存储在 DatasetInfo 中&#xff0c;可能包括数据集描述、特征和数据集大小等信息。&…

Java期末复习暨学校第十三次上机课作业

Java期末复习暨学校第十三次上机课作业&#xff1a; &#xff08;1&#xff09;&#xff1a;掌握正则表达式的使用 第一题&#xff1a; 第13行代码为正则表达式&#xff0c;中国内地的手机号必须是11个数字&#xff1a; &#xff08;1&#xff09; ^1&#xff1a;是该电话号码…

aosp15 - Activity生命周期切换

本文探查的是&#xff0c;从App冷启动后到MainActivity生命周期切换的系统实现。 调试步骤 在com.android.server.wm.RootWindowContainer#attachApplication 方法下断点&#xff0c;为了attach目标进程在com.android.server.wm.ActivityTaskSupervisor#realStartActivityLock…

【libuv】Fargo信令1:client发connect消息给到server

tcp 单机测试,进行模拟 (借助copilot实现) 【Fargo】28:字节序列client发connect消息给到serverserver 收到后回复ack给到客户端程序借助copilot实现。项目构建 Console依赖于Halo.dll提供的api,Halo 依赖于 Immanuel, 运行效果 遗留问题 客户端似乎么有逻辑收到ack做处理各…

libmodbus安装使用

要配置和编译 libmodbus&#xff0c;您需要确保安装了所有必要的依赖项&#xff0c;并按照正确的步骤进行操作。以下是详细的环境配置和编译指南&#xff0c;适用于不同的操作系统。 1. Linux (Debian/Ubuntu) 安装依赖项 首先&#xff0c;确保您的包列表是最新的&#xff1…

猫咪睡眠:萌态背后的奥秘与启示

猫咪的睡眠&#xff0c;犹如一本充满趣味与奥秘的小书&#xff0c;每一页都写满了它们独特的习性与本能。 猫咪堪称 “睡眠大师”&#xff0c;睡眠时间之长令人咋舌&#xff0c;一天中大约有 12 - 16 个小时在梦乡中度过&#xff0c;幼猫和老年猫甚至能睡更久。它们似乎深谙放…

关于小程序内嵌h5打开新的小程序

关于小程序内嵌h5打开新的小程序 三种方式 https://juejin.cn/post/7055551463489011749 只依赖于h5本身的就是 https://huaweicloud.csdn.net/64f97ebb6b896f66024ca16c.html https://juejin.cn/post/7055551463489011749 navigateToMiniProgram 故小程序webview里的h5无法…

免费GIS工具箱:轻松将glb文件转换成3DTiles文件

在GIS地理信息系统领域&#xff0c;GLB文件作为GLTF文件的二进制版本&#xff0c;主要用于3D模型数据的存储和展示。然而&#xff0c;GLB文件的使用频率相对较低&#xff0c;这是因为GIS系统主要处理的是地理空间数据&#xff0c;如地图、地形、地貌、植被、水系等&#xff0c;…

音视频入门基础:MPEG2-TS专题(21)——FFmpeg源码中,获取TS流的视频信息的实现

一、引言 通过FFmpeg命令可以获取到TS文件/TS流的视频压缩编码格式、色彩格式&#xff08;像素格式&#xff09;、分辨率、帧率信息&#xff1a; ./ffmpeg -i XXX.ts 本文以H.264为例讲述FFmpeg到底是从哪个地方获取到这些视频信息的。 二、视频压缩编码格式 FFmpeg获取TS文…

BenchmarkSQL使用教程

1. TPC-C介绍 Transaction Processing Performance Council (TPC) 事务处理性能委员会&#xff0c;是一家非盈利IT组织&#xff0c;他们的目的是定义数据库基准并且向产业界推广可验证的数据库性能测试。而TPC-C最后一个C代表的是压测模型的版本&#xff0c;在这之前还有TPC-A、…

火山引擎发布数据飞轮 2.0,AI 重塑企业数据消费

12 月 18 日&#xff0c;在 2024 冬季火山引擎 FORCE 原动力大会上&#xff0c;火山引擎数智平台&#xff08;VeDI&#xff09;正式升级发布数据飞轮 2.0 模式。 延续去年 4 月发布的数据飞轮“以数据消费促资产建设&#xff0c;以数据消费助业务发展”的核心内涵&#xff0c;…

LLaMA-Factory 单卡3080*2 deepspeed zero3 微调Qwen2.5-7B-Instruct

环境安装 git clone https://gitcode.com/gh_mirrors/ll/LLaMA-Factory.git 下载模型 pip install modelscope modelscope download --model Qwen/Qwen2.5-7B-Instruct --local_dir /root/autodl-tmp/models/Qwen/Qwen2.5-7B-Instruct 微调 llamafactory-cli train \--st…

合并比对学习资料

目录 ContractComparison已开源: ContractComparison已开源: GitHub - UnstoppableCurry/ContractComparison: Comparison of General Chinese Contracts with OCR Pytorch