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

Java数据结构-链表与LinkedList

链表

链表的概念

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

通俗来说,相比较于顺序表(物理上连续,逻辑上也连续),链表物理上不一定连续。

链表是由一个一个节点组织起来的,组织起来的整体就叫做链表。

链表的结构非常多样,

1.单向或双向

2.带头或不带头

3.循环或非循环

以上的链表结构可以组成八种链表。

在Java集合框架中的LinkedList底层实现的是无头双向循环链表

LinkedList模拟实现

1.创建一个无头双向链表,并标志头结点个尾结点。

static class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val = val;}}public ListNode head;//标志头节点public ListNode last;//标志尾结点
2.计算双向链表的长度:

从head开始遍历节点到尾结点,并定义一个变量count计数。

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

这里有一个问题,为什么遍历的条件是(cur!=null)?而不是(cur.next!=null)?

我们可以知道,此链表的尾结点next位置存的是null,如果以(cur.next!=null)作为判断条件,

那么当执行完循环中最后一条语句“cur = cur.next;”时,此时由于尾结点的next为空,所以会跳出循环,相当于count少进行了一次计数,那么最终的count值就是错误的。

3.查找是否包含关键字key在链表中
public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}
4.头插法

关键步骤:

        node.next = head;

        head.prev = node;

        head = node;

public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {node.next = head;head.prev = node;head = node;}}
5.尾插法:

关键步骤:

        last.next = node;

        node.prev = last;

        last = last.next;

public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {last.next = node;node.prev = last;last = last.next;}}

6.任意位置插入:

关键步骤:

        先记录要插入位置上的节点,记为cur,然后直接修改指向

        node.next = cur;

        cur.prev.next = node;

        node.prev = cur.prev;

        cur.prev = node;

注意:不能修改代码顺序

public void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//在0位置插入调用头插法if(index == 0) {addFirst(data);return;}//在尾位置插入调用尾插法if(index == size()) {addLast(data);return;}//1. 找到index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);//2、开始绑定节点node.next = cur;cur.prev.next = node;node.prev = cur.prev;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) {if(index < 0 || index > size()) {throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);}}
7.删除第一次出现关键字为key的节点

关键步骤:

(1)修改前驱指针的next,跳过cur

        cur.prev.next = cur.next;

(2)修改下一个指针的前驱,跳过cur

        cur.next.prev = cur.prev;

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 {//head == null 证明只有1个节点last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}}

8.删除所有值为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 {//head == null 证明只有1个节点last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}
9.清空链表
public void clear(){ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.prev = null;cur.next = null;cur = curN;}head = last = null;}

LinkedList

什么是LinkedList?

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节 点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

LinkedList实现了List接口。

LinkedList没有实现RandomAccess接口,因此不支持随机访问。

LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)

LinkedList的构造

方法解释
LinkedList()无参构造
public LinkedList(Collection<? extends E> c)
使用其他集合容器中元素构造list
public static void main(String[] args){ //构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");//使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);
}

LinkedList其他常用方法介绍

方法解释
boolean add(E e)
尾插 e
void add(int index, E element)
将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)
尾插 c 中的元素
E remove(int index)
删除 index 位置元素
boolean remove(Object o)
删除遇到的第一个 o
E get(int index)
获取下标 index 位置元素
E set(int index, E element)
将下标 index 位置元素设置为 element
void clear()
清空
boolean contains(Object o)
判断 o 是否在线性表中
int indexOf(Object o)
返回第一个 o 所在下标
int lastIndexOf(Object o)
返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)
截取部分 list

相关文章:

Java数据结构-链表与LinkedList

链表 链表的概念 链表是一种物理存储结构上非连续的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 通俗来说&#xff0c;相比较于顺序表&#xff08;物理上连续&#xff0c;逻辑上也连续&#xff09;&#xff0c;链表物理上不一定连续。 链表是…...

单元测试实施最佳方案(背景、实施、覆盖率统计)

1. 什么是单元测试&#xff1f; 对于很多开发人员来说&#xff0c;单元测试一定不陌生 单元测试是白盒测试的一种形式&#xff0c;它的目标是测试软件的最小单元——函数、方法或类。单元测试的主要目的是验证代码的正确性&#xff0c;以确保每个单元按照预期执行。单元测试通…...

mysql笔记(表导出文件,文件导入表)

遇见权限问题1: cat /etc/my.cnf加入[mysqld] secure_file_priv ""遇见目录错误2:因为 MySQL 服务器没有权限在根目录下创建文件。你可以尝试将文件导出到一个 MySQL 服务器有权限写入的目录下&#xff0c;例如 MySQL 数据目录或 /tmp目录。sudo chmod 755 /path/to…...

Navicat 17 新特性 | 原生支持 Linux ARM 平台以及银河麒麟和统信操作系统

随着 Navicat 17 的发布&#xff0c;引起了业界的广泛共鸣与热烈讨论。此前&#xff0c;我们深入探讨了Navicat 17的多项新特性&#xff0c;涵盖《模型设计&#xff1a;引领创新&#xff0c;优化升级》&#xff0c;《高效的查询与配置》以及《用户界面交互&#xff1a;流畅体验…...

【pytorch】手写数字识别

https://blog.csdn.net/qq_45588019/article/details/120935828 基本均参考该博客 《深度学习原理Pytorch实战》 初步处理 导包 import torch import numpy as np from matplotlib import pyplot as plt from torch.utils.data import DataLoader from torchvision import tr…...

SpringBoot3.3.0升级方案

本文介绍了由SpringBoot2升级到SpringBoot3.3.0升级方案&#xff0c;新版本的升级可以解决旧版本存在的部分漏洞问题。 一、jdk17下载安装 1、下载 官网下载地址 Java Archive Downloads - Java SE 17 Jdk17下载后&#xff0c;可不设置系统变量java_home&#xff0c;仅在id…...

用 Kotlin 编写四则运算计算器:从零开始的简单教程

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…...

java算法day13

java算法day13 104 二叉树的最大深度111 二叉树的最小深度226 翻转二叉树101 对称二叉树100 相同的树 104 二叉树的最大深度 我最开始想到的是用层序遍历。处理每一层然后计数。思路非常的清楚。 迭代法&#xff1a; /*** Definition for a binary tree node.* public class…...

方便快捷传文件—搭建rsync文件传输服务器

比如我们有一个服务器&#xff0c;想把各个机器的文件都通过脚本传给这台机&#xff0c;用sftp或者直接rsync就必须输密码&#xff0c;肯定不行&#xff0c;做等效性免密又麻烦&#xff0c;怎么办呢&#xff0c;这么办&#xff01; 在服务端 yum -y install rsync #编辑&…...

python调用qt编写的dll

报错&#xff1a;FileNotFoundError: Could not find module F:\pythonProject\MINGW\sgp4Lib.dll (or one of its dependencies). Try using the full path with constructor syntax. 只有两种情况&#xff1a; 1.路径不对 2.库的依赖不全 1、如果是使用了qt库的&#xff0…...

SCI一区级 | Matlab实现NGO-CNN-LSTM-Mutilhead-Attention多变量时间序列预测

SCI一区级 | Matlab实现NGO-CNN-LSTM-Mutilhead-Attention多变量时间序列预测 目录 SCI一区级 | Matlab实现NGO-CNN-LSTM-Mutilhead-Attention多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现NGO-CNN-LSTM-Mutilhead-Attention北方苍鹰算…...

【Redis】初识 Redis

文章目录 1 什么是 Redis2 Redis 的特点2.1 速度快2.2 可编程性2.3 可拓展性2.4 持久化2.5 主从复制2.5 高可用和分布式2.6 客户端语言多 3 Redis 使用场景3.1 实时数据存储3.2 缓存和 Session 存储3.3 消息队列 4 Redis 重大版本5 CentOS7 安装 Redis5 1 什么是 Redis Redis …...

【PTA天梯赛】L1-003 个位数统计(15分)

作者&#xff1a;指针不指南吗 专栏&#xff1a;算法刷题 &#x1f43e;或许会很慢&#xff0c;但是不可以停下来&#x1f43e; 文章目录 题目题解总结 题目 题目链接 题解 使用string把长度达1000位的数字存起来开一个代表个位数的数组 a[11]倒序计算最后一位&#xff0c;…...

c语言位操作符相关题目之交换两个数的值

文章目录 一、题目二、方法11&#xff0c;思路2&#xff0c;代码实现 三、方法21&#xff0c;思路2&#xff0c;代码实现 四、方法31&#xff0c;思路2&#xff0c;代码实现 总结 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、题目 实现两个变量的…...

智能家居装修怎么布线?智能家居网络与开关插座布置

打造全屋智能家居。计划的智能家居方案以米家系列为主&#xff0c;智能家居联网方案以无线为主。装修前为了装备智能家居做了很多准备工作&#xff0c;本文深圳侨杰智能分享一个智能家居装修和布线方面的心得与实战知识。希望能对大家的装修有所帮助。 ​1.关于网络 如果房子比…...

GD32MCU最小系统构成条件

大家是否有这个疑惑&#xff1a;大学课程学习51的时候&#xff0c;老师告诉我们51的最小系统构成&#xff1f;那么进入32位单片机时代&#xff0c;gd32最小系统构成又是怎么样的呢&#xff1f; 1.供电电路 需要确保供电的电压电流稳定&#xff0c;以东方红开发版为例&#xff…...

C语言——循环结构:while、do...while、for

while循环 基本结构 C语言中的while循环是一种基本的循环控制结构&#xff0c;它允许程序重复执行一段代码块&#xff0c;直到指定的条件不再满足为止。while循环的语法结构如下&#xff1a; while (condition) { // 循环体 // 在这里编写要重复执行的代码 } condition …...

C#实现最短路径算法

创建点集 double r 200 * 500;double width 1920;double height 1080;int col (int)(r / width);int row (int)(r / height);List<(double, double)> list1 new List<(double, double)>();for (int i 0; i < row; i){var y i * height;if (y < r){va…...

Python函数 之 匿名函数

1.概念 匿名函数: 使用 lambda 关键字 定义的表达式&#xff0c;称为匿名函数. 2.语法 lambda 参数, 参数: 一行代码 # 只能实现简单的功能&#xff0c;只能写一行代码 # 匿名函数 一般不直接调用&#xff0c;作为函数的参数使用的 3.代码 4.练习 # 1, 定义匿名函数, 参数…...

深入解析 Mybatis 中 Mapper 接口的实现原理

《深入解析 Mybatis 中 Mapper 接口的实现原理》 在使用 Mybatis 进行数据库操作时&#xff0c;Mapper 接口扮演着重要的角色。它提供了一种简洁、类型安全的方式来与数据库进行交互。那么&#xff0c;Mybatis 是如何实现 Mapper 接口的呢&#xff1f; 一、Mybatis 简介 Myb…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...