Java——LinkedList

2024-06-14 09:12
文章标签 java linkedlist

本文主要是介绍Java——LinkedList，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、链表

1.1 链表的概念及结构

链表在逻辑层面上是连续的，在物理层面上不一定是连续的

链表结构可分为，单向或双向、带头或不带头、循环或非循环，组合共计8种

重点：无头单向非循环链表、无头双向链表

1.2 模拟实现无头单向非循环链表

一个链表由若干节点组成，结合 内部类 知识，可将节点类定义在链表类中，成为内部类

public class MySingleLinkedList {static class ListNode {//该内部类中定义的是节点的属性public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//链表的头节点，定义在MySingleLinkedList类中}

下面以穷举的方式创建链表方便理解（真正创建链表并非如此）

//MySingleLinkedList类//该方法创建一个链表，头节点为node1，当该方法结束后，变量node1...都会销毁，只剩下头节点为head的链表public void createdList(){ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(2);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(4);ListNode node5 = new ListNode(5);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}

打印链表

//MySingleLinkedList 类public void display() {ListNode cur = head; //若直接使用head进行遍历打印，将只能打印一次，再次调用该函数，头节点就不在原来的位置了while(cur != null) { //注意！此处若写成 cur.next != null 则不会打印最后一个节点System.out.print(cur.val + " ");cur = cur.next;}}

求链表长度：

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

头插法：

    public void addFirst(int data) {ListNode newNode = new ListNode(data);newNode.next = head;head = newNode;}

尾插法：

    public void addLast(int data) {ListNode newNode = new ListNode(data);//不要忘记：判空！if(head == null) {head = newNode;return;}ListNode cur = head;while(cur.next != null) { //此处若写成 cur.next != null 则不会打印最后一个节点cur = cur.next;}cur.next = newNode;}

在index位置插入

// IndexNotLegalException 异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}// MySingleLinkedList 类public void addIndex(int index, int data) {//1、判断index合法性try{checkIndex(index);}catch(IndexNotLegalException e) {e.printStackTrace();}//2、index == 0 || index == size()if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//3、找到index的前一个位置ListNode cur = findIndexSubOne(index);//4、进行连接ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法！");}}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while(count < index-1) {cur = cur.next;count++;}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;}//若头节点为keywhile(head.val == key) {head = head.next;return;}ListNode cur = head;//遍历找到值为key的节点while(cur.next != null) {if(cur.next.val == key) {cur.next = cur.next.next;return;}cur = cur.next;}System.out.println("没有找到要删除的数字！");}

删除所有值为key的节点

    public void removeAllKey(int key) {//判空if (this.head == null) {return;}//快慢指针ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//处理头节点，当上述操作完成后，只剩下头节点没有判断//该方法优于一上来就判断头节点if(head.val == key) {head =head.next;}}

清空链表

    public void clear() {ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}

1.3 模拟实现无头双向非循环链表

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

链表遍历方式：

    public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);//直接sout打印System.out.println(list);System.out.println("======");//foreatch循环打印for(Integer x : list) {System.out.print(x + " ");}System.out.println();System.out.println("======");//for循环打印for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("======");//Iterator打印Iterator<Integer> it = list.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("======");//ListIterator可以倒着打印ListIterator<Integer> it3 = list.listIterator(list.size());while(it3.hasPrevious()) {System.out.print(it3.previous() + " ");}}

运行结果：

2、ArrayList 和 LinkedList 的区别

不同点ArrayListLinkedList
存储空间上逻辑&物理均连续逻辑上连续，物理上不一定连续
随机访问支持，时间复杂度为O(1)不支持，时间复杂度为O(N)
头插需要搬运元素，O(N)只需修改引用的指向，O(1)
插入空间不够时需要扩容没有容量概念
应用场景元素高效存储+频繁访问频繁在任意位置插入删除操作

这篇关于Java——LinkedList的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1059978。

相关文章

spring AMQP代码生成rabbitmq的exchange and queue教程

spring AMQP代码生成rabbitmq的exchange and queue教程

《springAMQP代码生成rabbitmq的exchangeandqueue教程》使用SpringAMQP代码直接创建RabbitMQexchange和queue,并确保绑定关系自动成立,简... 目录spring AMQP代码生成rabbitmq的exchange and 编程queue执行结果总结s
阅读更多...
Java调用Python脚本实现HelloWorld的示例详解

Java调用Python脚本实现HelloWorld的示例详解

《Java调用Python脚本实现HelloWorld的示例详解》作为程序员,我们经常会遇到需要在Java项目中调用Python脚本的场景,下面我们来看看如何从基础到进阶,一步步实现Java与Pyth... 目录一、环境准备二、基础调用：使用 Runtime.exec()2.1 实现步骤2.2 代码解析三、
阅读更多...
聊聊springboot中如何自定义消息转换器

聊聊springboot中如何自定义消息转换器

《聊聊springboot中如何自定义消息转换器》SpringBoot通过HttpMessageConverter处理HTTP数据转换,支持多种媒体类型,接下来通过本文给大家介绍springboot中... 目录核心接口springboot默认提供的转换器如何自定义消息转换器Spring Boot 中的消息
阅读更多...
Springboot项目构建时各种依赖详细介绍与依赖关系说明详解

Springboot项目构建时各种依赖详细介绍与依赖关系说明详解

《Springboot项目构建时各种依赖详细介绍与依赖关系说明详解》SpringBoot通过spring-boot-dependencies统一依赖版本管理,spring-boot-starter-w... 目录一、spring-boot-dependencies1.简介2. 内容概览3.核心内容结构4.
阅读更多...
Spring Boot 整合 SSE(Server-Sent Events)实战案例(全网最全)

Spring Boot 整合 SSE(Server-Sent Events)实战案例(全网最全)

《SpringBoot整合SSE(Server-SentEvents)实战案例(全网最全)》本文通过实战案例讲解SpringBoot整合SSE技术,涵盖实现原理、代码配置、异常处理及前端交互,... 目录Spring Boot 整合 SSE（Server-Sent Events）1、简述SSE与其他技术的对
阅读更多...
Spring Security 前后端分离场景下的会话并发管理

Spring Security 前后端分离场景下的会话并发管理

《SpringSecurity前后端分离场景下的会话并发管理》本文介绍了在前后端分离架构下实现SpringSecurity会话并发管理的问题,传统Web开发中只需简单配置sessionManage... 目录背景分析传统 web 开发中的 sessionManagement 入口ConcurrentSess
阅读更多...
Java整合Protocol Buffers实现高效数据序列化实践

Java整合Protocol Buffers实现高效数据序列化实践

《Java整合ProtocolBuffers实现高效数据序列化实践》ProtocolBuffers是Google开发的一种语言中立、平台中立、可扩展的结构化数据序列化机制,类似于XML但更小、更快... 目录一、Protocol Buffers简介1.1 什么是Protocol Buffers1.2 Pro
阅读更多...
Java实现本地缓存的四种方法实现与对比

Java实现本地缓存的四种方法实现与对比

《Java实现本地缓存的四种方法实现与对比》本地缓存的优点就是速度非常快,没有网络消耗,本地缓存比如caffine,guavacache这些都是比较常用的,下面我们来看看这四种缓存的具体实现吧... 目录1、HashMap2、Guava Cache3、Caffeine4、Encache本地缓存比如 caff
阅读更多...
MyBatis-Plus 与 Spring Boot 集成原理实战示例

MyBatis-Plus 与 Spring Boot 集成原理实战示例

《MyBatis-Plus与SpringBoot集成原理实战示例》MyBatis-Plus通过自动配置与核心组件集成SpringBoot实现零配置,提供分页、逻辑删除等插件化功能,增强MyBa... 目录 一、MyBATis-Plus 简介 二、集成方式（Spring Boot）1. 引入依赖 三、核心机制
阅读更多...
Java高效实现Word转PDF的完整指南

Java高效实现Word转PDF的完整指南

《Java高效实现Word转PDF的完整指南》这篇文章主要为大家详细介绍了如何用Spire.DocforJava库实现Word到PDF文档的快速转换,并解析其转换选项的灵活配置技巧,希望对大家有所帮助... 目录方法一：三步实现核心功能方法二：高级选项配置性能优化建议方法补充ASPose 实现方案Libre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2