数据结构---链表(java)
目录
1. 链表
2. 创建Node
3. 增加
4. 获取元素
5. 删除
6. 遍历链表
7. 查找元素是否存在
8. 链栈的实现
9. 链队的实现
1. 链表
- 数据存放在"Node"结点中
优点:不用考虑扩容和缩容的问题,实现了动态存储数据
缺点:没有随机访问的能力
2. 创建Node
先创建一个MyLinkedList类,初始化Node结点内部类
private class Node {private T val;private Node next;public Node() {this.val = null;this.next = null;}public Node(T val) {this.val = val;this.next = null;}}
3. 增加
<1> 在头部添加
public void addHead(T val) {Node node = new Node(val);node.next = this.header;this.header = node;this.size++;}
<2> 在尾部添加
public void tail(T val) {Node node = new Node(val);this.size++;if(header.next==null){this.header=node;return;}Node cur = header;while (cur.next!=null){cur = cur.next;}cur.next=node;}
<3> 在任意位置添加
public void add(int index, T val) {if (index < 0 || index > this.size) {throw new IllegalArgumentException("index is invalid");}//要插入的结点Node node = new Node(val);//新建一个虚拟头节点Node dummyHead = new Node(null);dummyHead.next = header;Node pre = dummyHead;//找到待插入位置的前一个结点for (int i = 0; i < index; i++) {pre = pre.next;}node.next = pre.next;pre.next = node;//更新头节点header = dummyHead.next;this.size++;}
4. 获取元素
<1> 获取头部元素
public T getHead() {if (isEmpty()) {return null;}return header.val;
}
<2> 获取尾部元素
public T getHail() {if (isEmpty()) {return null;}Node cur = this.header;while (cur.next != null) {cur = cur.next;}return cur.val;}
<3> 获取任意节点元素
public T get(int index) {if (index < 0 || index > this.size) {throw new IllegalArgumentException("index is invalid");}Node cur = this.header;int i = 1;while (i <= index) {cur = cur.next;i++;}return cur.val;}
5. 删除
<1> 通过下标删除结点
public Optional<T> removeByIndex(int index){if(index<0||index>=this.size){return Optional.empty();}//判断是否是头结点//使用虚拟头节点Node dummyNode = new Node(null);dummyNode.next = header;Node pre = dummyNode;int i=1;//寻找要删除的结点while(i<=index){pre = pre.next;i++;}//改变指针指向Node delNode = pre.next;pre.next = delNode.next;delNode.next = null;this.size--;this.header = dummyNode.next;return Optional.of(delNode.val);}
<2> 通过值删除结点
public void removeByVal(T val){if(isEmpty()){return;}Node dummyNode = new Node(null);dummyNode.next = header;Node pre = dummyNode;while(pre.next!=null){Node cur = pre.next;if(cur.val.equals(val)){pre.next=cur.next;cur.next=null;size--;}else {pre = pre.next;}}header = dummyNode.next;}
<3> 不使用虚拟头结点删除元素
public void removeWithoutDummyHead(T val){while(this.header!=null&&this.header.val.equals(val)){this.header = this.header.next;this.size--;}if(this.header==null){return;}//此时头节点一定不是要删除的结点Node pre = this.header;while(pre.next!=null){if(pre.next.val.equals(val)){pre.next = pre.next.next;this.size--;}else{pre = pre.next;}}
}
6. 遍历链表
重写toString()方法,将他拼接成链表的样子
@Overridepublic String toString() {//创建一个临时结点Node cru = header;StringBuffer sb = new StringBuffer();while (cru != null) {sb.append(cru.val + "--->");cru = cru.next;}sb.append("Null");return sb.toString();}
7. 查找元素是否存在
public boolean contains(T val) {Node res = new Node(val);Node cur = header;for (int i = 0; i < this.size; i++) {if (res.val.equals(cur.val)) {return true;}cur = cur.next;}return false;}
8. 链栈的实现
public interface Stack<T> {void push(T element);T pop();int getSize();boolean isEmpty();T peek();
}
public class LinkedStack<T> implements Stack<T> {private MyLinkedList<T> data;public LinkedStack(MyLinkedList<T> data) {this.data = data;}@Overridepublic void push(T element) {this.data.addTail(element);}@Overridepublic T pop() {Optional<T> optional = this.data.removeByIndex(0);if(optional.isPresent()){return optional.get();}return null;}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}@Overridepublic T peek() {return this.data.getHead();}
}
9. 链队的实现
public interface Queue<T>{void offer(T ele);T poll();boolean isEmpty();int getSize();T getFront();
}
public class LinkedQueue implements Queue {private MyLinkedList data;public LinkedQueue(MyLinkedList myLinkedList) {this.data = myLinkedList;}@Overridepublic void offer(Object ele) {this.data.addTail(ele);}@Overridepublic Object poll() {return this.data.removeByIndex(0);}@Overridepublic boolean isEmpty() {return this.data.isEmpty();}@Overridepublic int getSize() {return this.data.getSize();}@Overridepublic Object getFront() {return this.data.getHead();}
}
相关文章:

数据结构---链表(java)
目录 1. 链表 2. 创建Node 3. 增加 4. 获取元素 5. 删除 6. 遍历链表 7. 查找元素是否存在 8. 链栈的实现 9. 链队的实现 1. 链表 数据存放在"Node"结点中 优点:不用考虑扩容和缩容的问题,实现了动态存储数据 缺点:没有…...

Qt --- Day02
实现效果: 点击登录,检验用户密码是否正确,正确则弹出消息框,点击ok转到另一个页面 不正确跳出错误消息框,默认选线为Cancel,点击Yes继续登录 点击Cancel跳出问题消息框,默认选项No,…...

Redis 集合(Set)快速指南 | Navicat
Redis 支持通过多种数据类型来存储项目集合。其中,包括列表、集合和哈希。上周的博文介绍了列表(List)数据类型并重点介绍了一些用于管理列表(List)的主要命令。在今天的文章中,我们将转向关注集合…...

【华为云云耀云服务器L实例评测】- 云原生实践,快捷部署人才招聘平台容器化技术方案!
🤵♂️ 个人主页: AI_magician 📡主页地址: 作者简介:CSDN内容合伙人,全栈领域优质创作者。 👨💻景愿:旨在于能和更多的热爱计算机的伙伴一起成长!!&…...
【Java】泛型 之 什么是泛型
什么是泛型 泛型是一种“代码模板”,可以用一套代码套用各种类型。 在讲解什么是泛型之前,我们先观察Java标准库提供的ArrayList,它可以看作“可变长度”的数组,因为用起来比数组更方便。 实际上ArrayList内部就是一个Object[]…...

Python yaml 详解
文章目录 1 概述1.1 特点1.2 导入 2 对象2.1 字典2.2 数组2.3 复合结构 3 操作3.1 读取3.2 写入 1 概述 1.1 特点 yaml 文件是一种数据序列化语言,广泛用于配置文件、日志文件等特点: ① 大小写敏感。② 使用缩进表示层级关系。缩进时不允许使用 Tab 键…...
RabbitMQ消息可靠性(二)-- 消费者消息确认
一、消费者消息确认是什么? 在这种机制下,消费者在接收到消息后,需要向 RabbitMQ 发送确认信息,告知 RabbitMQ 已经接收到该消息,并已经处理完毕。如果 RabbitMQ 没有接收到确认信息,则会将该消息重新加入…...
【python第7课 实例,类】
文章目录 一、实例1.1实例的变量1.2实例方法1.3 构造方法1.4析构函数1.4预置实例属性: 二,类1.1类变量1.2类方法1.3静态方法1.4类属性的增删改查 一、实例 1.1实例的变量 使用示例 class dog:def __init__(self,k,c,a):self.kinds kself.color csel…...

RocketMQ源码解析(上)
一、ACL权限控制 应用场景: RocketMQ提供了针对队列、用户等不同维度的非常全面的权限管理机制。通常来说,RocketMQ作为一个内部服务,是不需要进行权限控制的,但是,如果要通过RocketMQ进行跨部门甚至跨公司的合作&…...

Webpack打包CSS文件,解决You may need an appropriate loader to handle this file type报错
在项目文件夹下创建webpack.config.js文件,该文件就是Webpack的配置文件 注意:该文件中遵循Node.js的代码格式规范 ,需要对导出配置文件中的内容 Webpack在默认情况下只能打包js文件,如果我们希望他能够打包其他类型的文件&#…...

轮换对称性
二重积分 普通对称性–D关于 y x yx yx对称: ∬ D f ( x , y ) d σ { 2 ∬ D 1 f ( x , y ) d σ f ( x , y ) f ( y , x ) 0 f ( x , y ) − f ( y , x ) \iint_{D}f(x,y)d\sigma\begin{cases} 2\iint_{D_1}f(x,y)d\sigma\ \ \ \ \ \ f(x,y)f(y,x) \\ 0 \ \…...

【MySQL基础】--- 约束
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【MySQL学习专栏】🎈 本专栏旨在分享学习MySQL的一点学习心得,欢迎大家在评论区讨论💌 目录 一、什么…...

ROS2 的行为树 — 第 1 部分:解锁高级机器人决策和控制
一、说明 在复杂而迷人的机器人世界中,行为树(BT)已成为决策过程中不可或缺的一部分。它们提供了一种结构化、模块化和高效的方法来对机器人的行为进行编程。BT起源于视频游戏行业,用于控制非玩家角色,他们在机器人领域…...
kafka事务的详解
一 kafka事务的机制 1.1 kafka的事务机制 通过事务机制,KAFKA 可以实现对多个 topic 的多个 partition 的原子性的写入,即处于同一个事务内的所有消息,不管最终需要落地到哪个 topic 的哪个 partition, 最终结果都是要么全部写成功…...
Flutter Fair逻辑动态化架构设计与实现
本文的核心内容包括: 数据逻辑处理布局中的逻辑处理Flutter类型数据处理一、数据逻辑处理 我们接触的每一个Flutter界面,大多由布局和逻辑相关的代码组成。如Flutter初始工程的Counting Demo的代码: class _MyHomePageState extends State<MyHomePage> {// 变量 int…...

【每日一题】74. 搜索二维矩阵
74. 搜索二维矩阵 - 力扣(LeetCode) 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返…...

软件测试进大厂,拿高薪,怎么做?看这里!
有些同学大学专业不对口,但有想进大厂想拿高薪心,只要你有想法,那就一定有实现的方法。 俗话说:“世间无难事,只怕有心人”。仔细思索一下,哪家大厂能缺软件测试这一重要职位。相对大学所学专业而言&#…...
【读书笔记】基于世界500强的高薪实战Kubernetes课程
第1章 课程简介&&自我介绍 1-1 自我介绍 1-2 课程大纲内容介绍 1-3 课程更新通知 第2章 K8s必备知识-Docker容器基础入门 2-1 课程介绍 2-2 docker容器介绍 2-3 docker优缺点 2-4 安装和配置docker 2-5 修改内核参数 2-6 配置镜像加速器 2-7 配置常用镜像加…...

【Java 基础篇】Java并发包详解
多线程编程是Java开发中一个重要的方面,它能够提高程序的性能和响应能力。然而,多线程编程也伴随着一系列的挑战,如线程安全、死锁、性能问题等。为了解决这些问题,Java提供了一套强大的并发包。本文将详细介绍Java并发包的各个组…...

MYSQL存储引擎基础知识介绍
下面重点介绍几种常用的存储引擎,并对比各个存储引擎之间的区别,以帮助读者理解 不同存储引擎的使用方式。 MyISAM MyISAM是 MySQL的默认存储引擎。MyISAM不支持事务、也不支持外键,其优势是访 问的速度快,对事务完整性没有要求或者以 SEL…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...