链表(Linkedlist)

ops/2024/11/13 11:11:51/

序言

我们都了解链表是一种数据的存储结构,在Java使用中逻辑与c++,c语言数据结构别无二致,但主要由于Java中不存在指针的说法,从而导致在实现过程中的代码不同,所以在学习的过程中我们无需过于担心,逻辑都是想通的,此博客就是针对Java中的主流两种链表进行介绍。

一.单链表

定义:一组存储单元被用来存储线性表的数据元素 所构成的结构被称为链表

在Java中每个数据元素我们以链节称之,以下就是单链表的逻辑结构:

由上图所示每个链节都含有两部分内容    1.数据   2.下一个链节的地址

头结点:一般情况下,为了处理方便,在单链表的第一个节点之前附设一个节点或者就以第一个节点为头结点。添加头结点便于对链表的处理

链表是非随机存取的存储结构,要取得第i个数据元素必须从头结点出发顺序寻找,也称为顺序存取的存取结构。

链表的代码实现:

以上就是一个节点内部类的实现 ListNode next 就是指向下个节点

cur=cur.next;    //代表cur指向了cur的下一个节点

1.插入链表节点的代码 分为首插,尾插,和中间部分插入

2.查找操作:判断链表是否存在该数据

3.删除单个元素以及删除数据等于该数据的所有节点

4.计算单链表长度:

5.遍历链表

6.清空链表

结尾

链表只要明确节点结构特点注重节点描述 访问时避免野地址的访问 单链表作为一种简单的数据结构 希望读者能够多联系即可掌握。

二.双链表

链表是对单链表存储功能单向性缺点所设计的一种存储结构

顾名思义 在双链表节点中有两个指向域,一个指向直接后继,一个指向指向前驱,节点如下设计:

需要在双链表中为方便访问定义一个头结点与一个尾节点

1.双链表的插入:

2.双链表的查找:

3.双链表的删除:

4.双链表长度:

三,单链表与双链表的优缺点

链表是一种链式存储的线性表,每个节点包含数据域和指向下一节点的指针域。优点是结构简单,存储开销小,易于实现插入和删除操作(特别是在链表头部或中间位置)。例如,要在单链表的头部插入一个新节点,只需让新节点的指针指向原头部节点,再将新节点设为头部即可。缺点是只能单向遍历,查找一个节点的前驱节点比较麻烦,时间复杂度高。
 
链表每个节点有两个指针域,分别指向前驱和后继节点。其优点是可以双向遍历,方便查找前驱和后继节点,在某些操作上更灵活。比如在需要频繁前后移动的场景中效率更高。缺点是每个节点的存储开销较大,因为多了一个指针域,并且插入和删除操作的代码相对复杂,要同时处理前驱和后继节点指针的更新。

关于链表一些做题代码大家可以在此链接中查询:linkedList/src/linkedList.java · 王昕/Java进行之路 - 码云 - 开源中国


http://www.ppmy.cn/ops/132950.html

相关文章

使用ref操作DOM(React)

一、获取指向节点的ref 1、一般方式: 引入useRef Hook函数,它用来创建可变的ref对象。一般用于访问DOM元素或在组件之间维持不变的值 import { useRef } from react; 使用useRef来声明一个myRef const myRef useRef(null); 最后,将myR…

hbase 工具类

hbase 工具类 pom.xml <dependency><groupId>org.apache.hbase</groupId><artifactId>hbase-client</artifactId><version>2.5.10-hadoop3</version> </dependency> <dependency><groupId>com.google.guava<…

如何不封禁UDP协议同时防止UDP攻击

UDP&#xff08;User Datagram Protocol&#xff09;协议因其简单、高效的特点&#xff0c;广泛应用于各种网络服务中&#xff0c;如视频流、在线游戏和VoIP等。然而&#xff0c;UDP协议的无连接特性和缺乏内置的安全机制使其容易成为攻击者的靶标&#xff0c;常见的攻击类型包…

Redis 高并发分布式锁实战

目录 环境准备 一 . Redis 安装 二&#xff1a;Spring boot 项目准备 三&#xff1a;nginx 安装 四&#xff1a;Jmeter 下载和配置 案例实战 优化一&#xff1a;加 synchronized 锁 优化二&#xff1a;使用 redis 的 setnx 实现分布式锁 优化三&#xff1a;使用 Lua 脚本…

docker快速安装与配置mongoDB

docker快速安装与配置mongoDB 拉取 MongoDB Docker 映像 docker pull mongodb/mongodb-community-server:latest将映像作为 container 运行 docker run --restartalways --name mongodb -p 27017:27017 --privilegedtrue -e MONGO_INITDB_ROOT_USERNAMEroot -e MONGO_INITD…

科技改变生活:最新智能开关、调光器及插座产品亮相

根据QYResearch调研团队的最新力作《欧洲开关、调光器和插座市场报告2023-2029》显示&#xff0c;预计到2029年&#xff0c;欧洲开关、调光器和插座市场的规模将攀升至57.8亿美元&#xff0c;并且在接下来的几年里&#xff0c;将以4.2%的复合年增长率&#xff08;CAGR&#xff…

《手写Spring渐进式源码实践》实践笔记(第十七章 数据类型转换)

文章目录 第十七章 数据类型转换工厂设计实现背景技术背景Spring数据转换实现方式类型转换器&#xff08;Converter&#xff09;接口设计实现 业务背景 目标设计实现代码结构类图实现步骤 测试事先准备属性配置文件转换器工厂Bean测试用例测试结果&#xff1a; 总结 第十七章 数…

数据中心类DataCenter(三)

数据中心类DataCenter&#xff08;三&#xff09; 前言 在上一集&#xff0c;我们就完成了整个数据中心类的构造函数以及析构函数&#xff0c;我们讨论了我们的数据持久化的相关事宜&#xff0c;那么我们这一集就要来完成这一个内容。 需求分析 我们需要暂且就规定我们的路…