Java-数构链表

1.链表

1.1链表的概念和结构

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

这里大多讨论无头单向非循环链表。这种结构，结构简单，一般与其他数据结构结合，作为其他数据结构的子数据。

1.2链表的实现

public class MysingleList {static class ListNode{public  int val;//节点的值域public ListNode next;//下一个节点为地址public ListNode(int val){this.val=val;}}public ListNode head;//当前链表的头节点public  void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}}

1.3方法

这里仍然尝试自己创建方法了解一些基础的操作

//头插法public void addFirst(int data){ListNode node=new ListNode(data);node.next=head;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);ListNode cur=head;if (cur==null){head=node;return ;}while(cur.next!=null){cur=cur.next;}cur.next=node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data) {if (index<0||index>size()){System.out.println("位置不合法");return;}if (index==0){addFirst(data);}if (index==size()){addLast(data);}ListNode node = new ListNode(data);ListNode cur=findIndex(index);node.next=cur.next;cur.next=node;}private ListNode findIndex(int index){ListNode cur=head;int count=0;while (cur!=null){cur=cur.next;count++;if (count==index-1){break;}}return cur;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=head;while (cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head==null){return;}if (head.val==key){head=head.next;return;}ListNode cur=findKey(key);if(cur==null){System.out.println("没有对应的数值");return ;}ListNode del=cur.next;cur.next=del.next;}private ListNode findKey(int key){ListNode cur=head;while (cur.next!=null){if (cur.next.val==key){return cur;}cur=cur.next;}return null;}//删除所有值为key的节点public void removeAllKey(int key){if (head==null){return;}ListNode cur=head.next;ListNode pre=head;while(cur!=null){if(cur.val==key){pre.next=cur.next;cur=cur.next;}else {pre=cur;cur=cur.next;}}if (head.val==key){head=head.next;//需要放在最后不然找不到后面的数据了。}}//得到单链表的长度public int size(){int count=0;ListNode cur=head;while(cur!=null){count++;cur=cur.next;}return count;}public void clear() {this.head=null;}public void display() {ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

另外在管理员中使用jps可以显示当前系统中所有正在运行的 Java 进程的 进程 ID（PID） 和 主类名 或 JAR 包名。jmap语言可以用于查看 Java 进程的内存使用情况、生成堆转储（heap dump）等。

这里再补充几道常见链表操作的题目：

876. 链表的中间结点

这一题可以使用快慢指针，快指针永远是慢支针步数的两倍。

class Solution {public ListNode middleNode(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}
}

206. 反转链表

class Solution {public ListNode reverseList(ListNode head) {if(head==null){return null;}if(head.next==null){return head;}ListNode cur=head.next;head.next=null;while(cur!=null){ListNode curNext=cur.next;//保存下一个节点cur.next=head;head=cur;cur=curNext;}return head;}
}

LCR 027. 回文链表

class Solution {public boolean isPalindrome(ListNode head) {ListNode fast=head;ListNode slow=head;//找到中间节点while (fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}//翻转后半部分的链表ListNode cur=slow.next;while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//判断回文while(head!=slow){if(head.val!=slow.val){return false;}if(head.next==slow){return true;}head=head.next;slow=slow.next;}return true;}
}

链表分割_牛客题霸_牛客网

public ListNode partition(ListNode pHead, int x) {// write code hereListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;//没有遍历完 整个链表while(cur != null) {if(cur.val < x) {//第一次插入if(bs == null) {bs = be = cur;}else {be.next = cur;be = be.next;}}else {//第一次插入if(as == null) {as = ae = cur;}else {ae.next = cur;ae = ae.next;}}cur = cur.next;}//第一个段 没有数据if(bs == null) {return as;}be.next = as;//防止 最大的数据 不是最后一个if(as!=null) {ae.next = null;}return bs;}

141. 环形链表 - 力扣（LeetCode）

public class Solution {public boolean hasCycle(ListNode head) {if(head==null){return false;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){return true;}}return false;}
}

 160. 相交链表 - 力扣（LeetCode）

一定是Y型

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA=0;int lenB=0;ListNode pl=headA;ListNode ps=headB;while(pl!=null){lenA++;pl=pl.next;}while(ps!=null){lenA++;ps=ps.next;}pl=headA;ps=headB;int len=lenA-lenB;if(len<0){pl=headB;ps=headA;len=lenB-lenA;//让len能够一定是正数}}//让最长的链表先走差值步while(len>0){pl=pl.next;len--;}//找到相遇的点while(pl!=ps){pl=pl.next;ps=ps.next;}return pl; 
}

 142. 环形链表 II - 力扣（LeetCode）

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null){return null;}ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){break;}}if(fast==null||fast.next==null){return null;}fast=head;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}

2.LinkedList

2.1概念

LinkedList的底层是双向链表结构，由于链表没有将元素储存在连续空间中，元素存储在单独节点中，通过引用将节点链接，因此在进行插入和删除元素的操作的时候，不需要搬移元素，效率较高。

2.2方法

为帮助理解常用方法的底层逻辑，这里再自己对方法进行实现。

public class MyLinkList {//双向链表static class ListNode{private int  val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val=val;}}public ListNode head;public ListNode last;//得到单链表的长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public void display(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=head;while(cur!=null){if (cur.val==key){return true;}cur=cur.next;}return false;}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if (head==null){head=node;last=node;}else{node.next=head;head.prev=node;head=node;}}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if (head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=last.next;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){checkIndex(index);if (index==0){addFirst(data);}if (index==size()){addLast(data);}ListNode cur=findIndex(index);ListNode node=new ListNode(data);node.next=cur.next;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}private void checkIndex(int index){if (index<0||index>size()){throw new IndexOutOfException("index位置不合法");}}private ListNode findIndex(int index){ListNode cur=head;while(index !=0){cur=cur.next;index--;}return cur;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=head;while (cur!=null){if (cur.val==key){if (cur==head){//如果头节点正好是目标节点head=head.next;//如果只有这一个节点则为空if (head!=null){head.prev=null;}else {last=null;}}else {//中间节点if (cur.next!=null){cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//如果正好是last为目标节点cur.prev.next=cur.next;last=last.prev;}}return ;}else {cur=cur.next;}}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur=head;while (cur!=null){if (cur.val==key){if (cur==head){//如果头节点正好是目标节点head=head.next;//如果只有这一个节点则为空if (head!=null){head.prev=null;}else {last=null;}}else {//中间节点if (cur.next!=null){cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//如果正好是last为目标节点cur.prev.next=cur.next;last=last.prev;}}cur=cur.next;}}}public void clear(){ListNode cur=head;while(cur!=head){ListNode curNext=cur.next;//保存一下cur.prev=null;cur.next=null;cur=curNext;}head=null;last=null;}
}

2.3LinkedList的使用

LinkedList实现了List接口。

1.LinkedList的构造

LinkedList()       --无参构造

public LinkedList(Collection<? extends E> c) --使用其他集合容器中元素构造List
    public static void main(String[] args) {List<Integer>list1=new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);}

 2.4遍历

 public static void main(String[] args) {List<Integer>list1=new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);for (int x: list1) {System.out.print(x+" ");}System.out.println();ListIterator<Integer>it=list1.listIterator();while (it.hasNext()){System.out.print(it.next()+" ");}System.out.println();ListIterator<Integer>it2=list1.listIterator(list1.size());while (it.hasPrevious()){System.out.print(it.previous()+" ");}System.out.println();}

2.5ArrayList和LinkedList的区别

又可以说是链表和顺序表的区别

不同点ArrayListLinkedList
存储空间上物理地址上连续逻辑上连续，但物理地址不一定连续
随机访问支持O（1）不支持：O（N）
头插法

需要搬移元素，效率低

O（N）

只需要修改引用的指向，时间复杂度为

O（1）

插入法空间不够，需要进行扩容没有容量
应用场景元素高效存储，频繁访问任意位置插入和删除频繁

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/pingmian/89495.shtml
繁体地址，请注明出处：http://hk.pswp.cn/pingmian/89495.shtml

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

相关文章

Windows系统软件游戏丢失找不到mgmtapi.dll修复解决方法

Windows系统软件游戏丢失找不到mgmtapi.dll修复解决方法

在使用电脑系统时经常会出现丢失找不到某些文件的情况&#xff0c;由于很多常用软件都是采用 Microsoft Visual Studio 编写的&#xff0c;所以这类软件的运行需要依赖微软Visual C运行库&#xff0c;比如像 QQ、迅雷、Adobe 软件等等&#xff0c;如果没有安装VC运行库或者安装…
阅读更多...
初识C++——开启新旅途

初识C++——开启新旅途

从今天开始主包也是掉入C这个深坑&#xff0c;上完课也是跟没上一样&#xff0c;所以写好博客复习还是很重要的&#xff0c;话不多说&#xff0c;进入正题~~1、命名空间(1)namespace的价值与作用在C/C中&#xff0c;变量、函数和后面要学到的类都是大量存在的&#xff0c;这些变…
阅读更多...
vue2 面试题及详细答案150道（141 - 150）

vue2 面试题及详细答案150道（141 - 150）

《前后端面试题》专栏集合了前后端各个知识模块的面试题&#xff0c;包括html&#xff0c;javascript&#xff0c;css&#xff0c;vue&#xff0c;react&#xff0c;java&#xff0c;Openlayers&#xff0c;leaflet&#xff0c;cesium&#xff0c;mapboxGL&#xff0c;threejs&…
阅读更多...
第十三章 Go包管理

第十三章 Go包管理

文章目录使用logurs处理程序日志logrus 常用配置使用viper处理程序配置使用logurs处理程序日志 下载包&#xff0c;在终端执行命令 go get github.com/sirupsen/logrus官方示例 package mainimport (log "github.com/sirupsen/logrus" )func main() {log.WithFiel…
阅读更多...
EP01：【Python 第一弹】基础入门知识

EP01：【Python 第一弹】基础入门知识

一、基础入门知识 1.1 代码规范 1.1.1 语句分隔符 ; 换行 1.1.2 格式化 对 Windows 和 Linux 操作系统&#xff0c;快捷键是Ctrl Alt L对 macOS 操作系统&#xff0c;快捷键是Cmd Option L 1.1.3 注释 单行注释 # 这是一行注释多行注释 """ 这 是 …
阅读更多...
实用的文件和文件夹批量重命名工具

实用的文件和文件夹批量重命名工具

在日常工作中&#xff0c;文件和文件夹的命名管理常常让人头疼。尤其是面对大量文件时&#xff0c;手动重命名不仅耗时&#xff0c;还容易出错。今天&#xff0c;我要给大家推荐一款超级实用的工具——OncePower 文件批量重命名&#xff0c;它不仅能批量重命名文件和文件夹&…
阅读更多...
【Git】报错：git config --global http.sslBackend “openssl“

【Git】报错：git config --global http.sslBackend “openssl“

问题解决 报错&#xff1a;git config --global http.sslBackend “openssl”解决方法&#xff1a; git config --global http.sslBackend "openssl"之后再 push 即可正常提交。 &#x1f50d; 原因分析 ​​系统环境不支持 OpenSSL 后端​​ Git 在某些平台&#xf…
阅读更多...
Redisson RLocalCachedMap 核心参详解

Redisson RLocalCachedMap 核心参详解

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…
阅读更多...
AI辅助编程时代的高效规范开发指南：工具、原则与提效策略

AI辅助编程时代的高效规范开发指南：工具、原则与提效策略

引言&#xff1a;AI辅助编程的时代背景与核心挑战 人工智能在编程领域的应用虽可追溯至20世纪50年代&#xff0c;但近十年实现了革命性突破&#xff0c;推动其从早期的代码补全工具演进为能理解上下文、生成完整函数乃至项目架构的智能系统。关键发展里程碑包括&#xff1a;20…
阅读更多...
百度网盘TV版1.21.0 |支持倍速播放，大屏云看片

百度网盘TV版1.21.0 |支持倍速播放，大屏云看片

百度网盘TV版是专为智能电视设计的应用程序&#xff0c;让用户可以直接在大屏幕上观看保存在云端的视频资源。此应用提供了与手机端几乎相同的功能&#xff0c;包括倍速播放功能&#xff0c;使得用户可以更方便地享受高清视频内容。无需繁琐的操作步骤&#xff0c;即可实现云端…
阅读更多...
C++控制台贪吃蛇开发(二)：让灵蛇舞动起来！

C++控制台贪吃蛇开发(二)：让灵蛇舞动起来！

资料合集下载链接： ​​https://pan.quark.cn/s/472bbdfcd014​ 本文将深入讲解蛇移动的机制，并带你一步步实现以下功能： 理解蛇移动的核心算法：为什么蛇的移动是“倒着”更新的？ 用代码表示方向：如何使用​​dx​​和​​dy​​变量优雅地控制方向。 编写核心​​move…
阅读更多...
Elasticsearch+Logstash+Filebeat+Kibana部署

Elasticsearch+Logstash+Filebeat+Kibana部署

目录 软件说明&#xff1a; 架构拓扑 集群模式&#xff1a; 单机模式 环境准备 部署&#xff1a; kibana es logstash filebeat es 检查能否启动 logstash 命令设置 es 修改es配置文件 启用es kibana 修改kibana配置文件&#xff08;方便查看索引&#xff09…
阅读更多...
GLM（General Language Model，通用语言模型）

GLM（General Language Model，通用语言模型）

&#x1f9e0; 一、GLM是什么&#xff1f;一句话概括 GLM&#xff08;General Language Model&#xff0c;通用语言模型&#xff09;是一个“大脑”&#xff0c;它通过阅读海量书籍、网页、对话记录学会了人类的语言规则&#xff0c;不仅能“听懂”你说的话&#xff0c;还能“…
阅读更多...
【科研绘图系列】R语言绘制显著性标记的热图

【科研绘图系列】R语言绘制显著性标记的热图

文章目录 介绍 加载R包 数据下载 导入数据 数据预处理 画图 系统信息 参考 介绍 【科研绘图系列】R语言绘制显著性标记的热图 加载R包 library(ggplot2) library(patchwork)rm(list = ls()) options(stringsAsFactors = F)
阅读更多...
若依部署项目到服务器

若依部署项目到服务器

目录 一、环境配置 redis nginx&#xff08;宿主机|dokcer&#xff09; 1.宿主机 2.docker 二、打包jar包 0.查看后端配置 1.打包后端 2.打包前端 三、启动 1.后端 2.前端 四、以上部署常见命令/错误 一、环境配置 之前的课都配过&#xff0c;先看看自己配了没 看看…
阅读更多...
零基础学习性能测试-linux服务器监控：CPU监控

零基础学习性能测试-linux服务器监控：CPU监控

目录学习内容与快速应用路径第一阶段&#xff1a;理解 CPU 核心概念 (0.5天)第二阶段&#xff1a;掌握核心监控命令与指标 (1-2天)第三阶段&#xff1a;识别 CPU 问题与瓶颈 (核心技能)第四阶段&#xff1a;整合到性能测试工作流程 (快速应用落地)快速应用到工作中的关键策略零…
阅读更多...
智能Agent场景实战指南 Day 15：游戏NPC Agent互动设计

智能Agent场景实战指南 Day 15：游戏NPC Agent互动设计

【智能Agent场景实战指南 Day 15】游戏NPC Agent互动设计 文章内容 开篇 欢迎来到"智能Agent场景实战指南"系列的第15天&#xff01;今天我们将深入探讨游戏开发中一个极具挑战性和创新性的领域——游戏NPC Agent互动设计。在当今游戏产业中&#xff0c;玩家对游戏…
阅读更多...
Vite的优缺点（精简版）

Vite的优缺点（精简版）

优点 作为一款前端构建工具&#xff0c;它的核心特点是“快”&#xff0c;并且充分利用了现代浏览器对ES Modules的原生支持&#xff0c;一切围绕这一点展开 快启动&#xff1a;通过ES Modules&#xff0c;它省去了打包整个应用的时间&#xff0c;可以直接在浏览器中加载模块&a…
阅读更多...
【深度学习】神经网络-part2

【深度学习】神经网络-part2

一、数据加载器 数据集和加载器 1.1构建数据类 1.1.1 Dataset类 Dataset是一个抽象类&#xff0c;是所有自定义数据集应该继承的基类。它定义了数据集必须实现的方法。 必须实现的方法 __len__: 返回数据集的大小 __getitem__: 支持整数索引&#xff0c;返回对应的样本 …
阅读更多...
nextjs+react项目如何代理本地请求解决跨域

nextjs+react项目如何代理本地请求解决跨域

在 Next.js React 项目中解决本地开发跨域问题&#xff0c;可以通过以下几种方式实现代理请求&#xff1a;方案1&#xff1a;使用 Next.js 内置的 Rewrites 功能&#xff08;推荐&#xff09; 1. 修改 next.config.js /** type {import(next).NextConfig} */ const nextConfig…
阅读更多...
最新文章

Copyright @ 2022~2023