当前位置： 首页 > news >正文

Java-数构链表

news 2025/7/17 8:59:57

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.lryc.cn/news/590193.html

相关文章：

  • golang语法-----指针
  • 笔试——Day10
  • 简单易懂，什么是连续分配管理方式
  • Qt 将触摸事件转换为鼠标事件（Qt4和Qt5及以上版本）
  • Java线程创建与运行全解析
  • DuckDB 高效导入 IPv6 地址数据的实践与性能对比
  • #Datawhale组队学习#7月-强化学习Task1
  • java解析word文档
  • 使用JS编写一个购物车界面
  • C++ 面向对象
  • 第2章通用的高并发架构设计——2.3 高并发读场景方案2：本地缓存
  • 开源 python 应用 开发（七）数据可视化
  • Linux 定时器应用示例（修正版）
  • GIT版本回退
  • Python中可以反转的数据类型
  • GaussDB 数据库架构师修炼(五) 存储容量评估
  • 搜索框的显示与隐藏（展开与收起）
  • el-input 回显怎么用符号￥和变量拼接展示？
  • openEuler 22.03 LTS Rootless Docker 安装指南
  • MongoDB复杂查询 聚合框架
  • 洛谷 P11247 [GESP202409 六级] 算法学习-普及/提高-
  • pymongo库：简易方式存取数据
  • ETL还是ELT，大数据处理怎么选更靠谱？
  • 步态循环（Gait Cycle）
  • 【MySQL事务和锁】回顾事务
  • 图像质量评价（Image Quality Assessment，IQA）
  • 调试bug记录
  • 【基于飞浆训练车牌识别模型】
  • Docker——Redis
  • 【C语言网络编程】HTTP 客户端请求（发送请求报文过程）