数据结构：图文详解双向链表的各种操作（头插法，尾插法，任意位置插入，查询节点，删除节点，求链表的长度... ...）

目录

一.双向链表的概念

二.双向链表的数据结构

三.双向链表的实现

节点的插入

头插法

尾插法

任意位置插入

节点的删除

删除链表中第一次出现的目标节点

删除链表中所有与关键字相同的节点

节点的查找

链表的清空

链表的长度

四.模拟实现链表的完整代码

前言：在上一篇文章中，我们认识了链表中的单链表，而本篇文章则是介绍线链表中的另一个结构双向链表，有兴趣的朋友们可以点击了解：图文详解单链表的各种操作

一.双向链表的概念

双向链表（Doubly Linked List）是一种数据结构，它与单向链表相似，但每个节点不仅包含指向下一个节点的指针，还包含指向上一个节点的指针。

双向链表的每个节点通常包含以下两个指针：

  • prev：指向上一个节点
  • next：指向下一个节点

通过这两个指针，可以在双向链表中沿着两个方向遍历。

相比于单向链表，双向链表能够更方便地进行插入和删除操作。因为每个节点包含指向前一个节点的指针，所以在删除或插入一个节点时，只需要修改该节点前后节点的指针即可。而在单向链表中，则需要在删除或插入节点时，找到该节点的前一个节点，以便进行指针修改，显得相对麻烦。

二.双向链表的数据结构

双向俩表有俩个指针，分别存放前驱节点的地址和后继节点的地址，如图所示

对于其中每一个节点，我们可以如下存储

    public class Node{public int data;public Node prev;public Node next;//构造方法，给每个节点赋值public Node(int data) {this.data = data;}}

而我们的链表则是需要将所有的节点封装起来，放进一个数据结构中，因此将刚才定义的节点类作为链表的内部类即可，而链表又需要实现各种各样的功能，我们可以将所有的链表的功能抽象出一个接口，然后通过链表去具体的实现那些功能

public class MyLinkList implements Ilst{//节点的数据结构public class Node{public int data;public Node prev;public Node next;//构造方法public Node(int data) {this.data = data;}}public Node head;//头节点public Node last;//尾节点
}

接口：

public interface Ilst {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入public void addIndex(int index,int data);//查找是否包含关键字key是否在链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到链表的长度public int size();//展示链表public void display();//清空链表public void clear();
}

三.双向链表的实现

节点的插入

节点的插入分为三种情况，一是在链表最前面进行插入也就是头插法，二是在链表末尾进行插入，也就是尾插法，三是在链表中间位置插入

头插法

如图所示有一个新的节点，我们需要将其插入头节点的位置

第一步：将目标节点的后继指针指向头节点位置的节点

第二步，将头节点的前驱指针指向目标节点

在使用代码具体实现的时候，需要对异常做出判断，假如头节点为空，也就是链表里面没有节点的时候，我们就直接让我们要新加的节点既是头节点，又是尾节点；在做出异常处理后，我们就可以按照刚才图示的过程进行头插了，但是需要注意的是，在完成头插后需要更新头节点的位置 

    @Override//头插法public void addFirst(int data) {Node newNode = new Node(data);if (head == null){head = newNode;last = newNode;}else {newNode.next = head;head.prev = newNode;//更新头节点head = newNode;}}

尾插法

如图所示有一个新的节点，我们需要将其插入链表的末尾

第一步：将目标节点的前驱指针指向尾部节点

第二步：将尾部节点的后继指针指向目标节点

在使用代码具体实现的时候，需要对异常做出判断，假如头节点为空，也就是链表里面没有节点的时候，我们就直接让我们要新加的节点既是头节点，又是尾节点；在做出异常处理后，我们就可以按照刚才图示的过程进行尾插了，但是需要注意的是，在完成头插后需要更新尾部节点的位置

    @Override//尾插法public void addLast(int data) {Node newNode =  new Node(data);if (head == null){head = newNode;last = newNode;}else {newNode.prev = last;last.next = newNode;//更新尾部节点last = newNode;}}

任意位置插入

如图，假如想让新节点插入第三个节点的位置，该如何做呢？

第一步：先将目标节点的后继指针指向要插入节点的后一个节点

 

第二步：将目标节点的前驱指针指向插入节点 

 

第三步：将插入节点的后继指针指向目标节点

第四步：将插入节点的后一个节点的前驱指针指向目标节点 

对于节点的插入，最难的一点便是这4个步骤的顺序，顺序不是一成不变也不必死背，只需要记住一个原则——保证链表不断，在这个原则的基础上进行操作就不会出现问题了，也就是说在我们插入的时候，不要因为先去处理前面的节点导致找不到后面的节点就可以，因此我们在对链表进行插入操作的时候，一般都习惯先对后面的节点进行操作。

对于输入的位置我们要进行合法性的判断，如果在最前面就刚好使用头插法，如果是最后面就使用尾插法，之后遍历找到我们要插入的位置

    @Override//任意位置插入public void addIndex(int index, int data) {//对输入位置进行判断if (index < 0 || index > size()) {System.out.println("输入位置不合法");return;}if (index == 0) {//如果插入位置在最前面就使用头插addFirst(data);return;}if (index == size()) {//这里的size方法在后文中有定义//如果插入位置在最后面就使用尾插addLast(data);return;}//在中间插入Node newNode = new Node(data);//找到要插入的位置Node cur = head;while (index != 1) {cur = cur.next;index--;}//将新节点插入到cur之前newNode.next = cur;newNode.prev = cur.prev;cur.prev.next = newNode;cur.prev = newNode;
//        //将新节点插入到cur之后
//        newNode.next = cur.next;
//        newNode.prev = cur;
//        cur.next = newNode;
//        newNode.next.prev = newNode;}

节点的删除

对于节点的删除我们分为俩种，一种的将单个节点进行删除，一种是将所有与目标值相同的节点进行删除

删除链表中第一次出现的目标节点

如图，我们假定我们要删除链表中第三个节点

第一步：将删除节点的前驱节点的后继指针指向删除节点的后继节点 

第二步：将删除节点的后继节点的前驱指针指向删除节点的前驱节点

对于上面俩个过程只是俩行代码就可以解决：

cur.next.prev = cur.prev;
cur.prev.next = cur.next;

删除的过程非常简单，但是要找到正确的位置并不是一件容易事，就算找到后也要进行合法性的判断，具体代码如下：

    @Override//删除第一次出现关键字为key的节点public void remove(int key) {Node 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.next != null) {//删除中间节点cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}return;}cur = cur.next;}}

删除链表中所有与关键字相同的节点

对于和刚才唯一不同的点就是我们在删除一个点后不需要停止返回，继续遍历整个链表进行删除即可，这里就不再赘述

    @Override//删除所有值为key的节点public void removeAllKey(int key) {Node 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.next != null) {//删除中间节点cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}}cur = cur.next;}}

节点的查找

对于节点的查找，只需要挨个遍历判断就可以

    @Override//查找是否包含关键字key是否在链表当中public boolean contains(int key) {Node cur = head;while (cur != null){if (cur.data == key){return true;}else {cur = cur.next;}}return false;}

链表的清空

清空链表需要对每个节点进行清空，因此我们遍历整个链表然后进行赋值为空就可以，但是有一点需要注意，我们在删除每一个节点的后继指针之前得先做临时的记录，不然我们删除了一个节点的后继指针后就无法通过它访问后一个节点了

    @Override//清空链表public void clear() {Node cur = head;while (cur != null){Node tempNode = cur.next;//记录当前节点的下一个节点的地址cur.prev = null;cur.next = null;cur = tempNode;}this.head = null;this.last = null;}

链表的长度

求链表的长度只需要使用计数器遍历累加就可以

    @Override//得到单链表的长度public int size() {int count = 0;Node cur = head;while (cur != null) {count++;cur = cur.next;}return count;}

四.模拟实现链表的完整代码

package MyLinkList;public class MyLinkList implements Ilst {public class Node {public int data;public Node prev;public Node next;//构造方法public Node(int data) {this.data = data;}}public Node head;public Node last;@Override//头插法public void addFirst(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;last = newNode;} else {newNode.next = head;head.prev = newNode;//更新头节点head = newNode;}}@Override//尾插法public void addLast(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;last = newNode;} else {newNode.prev = last;last.next = newNode;//更新尾部节点last = newNode;}}@Override//任意位置插入public void addIndex(int index, int data) {//对输入位置进行判断if (index < 0 || index > size()) {System.out.println("输入位置不合法");return;}if (index == 0) {//如果插入位置在最前面就使用头插addFirst(data);return;}if (index == size()) {//如果插入位置在最后面就使用尾插addLast(data);return;}//在中间插入Node newNode = new Node(data);//找到要插入的位置Node cur = head;while (index != 1) {cur = cur.next;index--;}//将新节点插入到cur之前newNode.next = cur;newNode.prev = cur.prev;cur.prev.next = newNode;cur.prev = newNode;
//        //将新节点插入到cur之后
//        newNode.next = cur.next;
//        newNode.prev = cur;
//        cur.next = newNode;
//        newNode.next.prev = newNode;}@Override//查找是否包含关键字key是否在链表当中public boolean contains(int key) {Node cur = head;while (cur != null){if (cur.data == key){return true;}else {cur = cur.next;}}return false;}@Override//删除第一次出现关键字为key的节点public void remove(int key) {Node 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.next != null) {//删除中间节点cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}return;}cur = cur.next;}}@Override//删除所有值为key的节点public void removeAllKey(int key) {Node 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.next != null) {//删除中间节点cur.next.prev = cur.prev;cur.prev.next = cur.next;}else {//删除尾巴节点cur.prev.next = cur.next;last = last.prev;}}}cur = cur.next;}}@Override//得到单链表的长度public int size() {int count = 0;Node cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Override//展示链表public void display() {Node cur = head;while (cur != null) {System.out.print(cur.data + " ");cur = cur.next;}System.out.println();}@Override//清空链表public void clear() {Node cur = head;while (cur != null){Node tempNode = cur.next;cur.prev = null;cur.next = null;cur = tempNode;}this.head = null;this.last = null;}
}

  本次的分享就到此为止了，希望我的分享能给您带来帮助，也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见

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

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

相关文章

“此应用专为旧版android打造,因此可能无法运行”，问题解决方案

“此应用专为旧版android打造,因此可能无法运行”，问题解决方案

当用户在Android P系统上打开某些应用程序时&#xff0c;可能会弹出一个对话框&#xff0c;提示内容为&#xff1a;“此应用专为旧版Android打造&#xff0c;可能无法正常运行。请尝试检查更新或与开发者联系”。 随着Android平台的发展&#xff0c;每个新版本通常都会引入新的…
阅读更多...
线程池大小设置多少，比较合适？

线程池大小设置多少，比较合适？

设置线程数的核心点 压测&#xff01;压测&#xff01;再压测&#xff01;实际对性能要求比较高的场景&#xff0c;压测是最佳的方式&#xff01; 并发编程适用于什么场景&#xff1f; CPU 密集型 对于 CPU 密集型任务&#xff0c;希望最大限度地提高 CPU 利用率&#xff0c…
阅读更多...
每周一算法：背包问题（三）多重背包

每周一算法：背包问题（三）多重背包

多重背包 有 N N N件物品和一个容量是 M M M的背包。第 i i i种物品最多有 s i s_i si​件&#xff0c;每件的体积是 v i v_i vi​&#xff0c;价值是 w i w_i wi​。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输…
阅读更多...
pytorch 模型量化quantization

pytorch 模型量化quantization

pytorch 模型量化quantization 1.workflow1.1 PTQ1.2 QAT 2. demo2.1 构建resnet101_quantization模型2.2 PTQ2.3 QAT 参考文献 pytorch框架提供了三种量化方法&#xff0c;包括&#xff1a; Dynamic QuantizationPost-Training Static Quantization&#xff08;PTQ&#xff0…
阅读更多...
DevOps搭建(三)-Git安装详细步骤

DevOps搭建(三)-Git安装详细步骤

前面两篇文章我们讲了如何安装swappiness安装和虚拟机。这篇我们详细讲下如何安装Git。 1、YUM源更改为阿里云镜像源 1.1、备份CentOS-Base.repo 先备份原有的 CentOS-Base.repo 文件 sudo mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup…
阅读更多...
OCR原理解析

OCR原理解析

目录 1.概述 2.应用场景 3.发展历史 4.基于传统算法的OCR技术原理 4.1 图像预处理 4.1.1 灰度化 4.1.2 二值化 4.1.3 去噪 4.1.4 倾斜检测与校正 4.1.4.2 轮廓矫正 4.1.5 透视矫正 4.2 版面分析 4.2.1 连通域检测文本 4.2.2 MSER检测文本 4.3 字符切割 4.3.1 连…
阅读更多...
2022年全国大学生数据分析大赛医药电商销售数据分析求解全过程论文及程序

2022年全国大学生数据分析大赛医药电商销售数据分析求解全过程论文及程序

2022年全国大学生数据分析大赛 医药电商销售数据分析 原题再现&#xff1a; 问题背景   20 世纪 90 年代是电子数据交换时代&#xff0c;中国电子商务开始起步并初见雏形&#xff0c;随后 Web 技术爆炸式成长使电子商务处于蓬勃发展阶段&#xff0c;目前互联网信息碎片化以…
阅读更多...
数组逆序重放

数组逆序重放

数组逆序重放的意思是将数组的元素逆序排列&#xff0c;然后重新放回原数组中。这个操作可以在很多编程语言中实现&#xff0c;例如Python、Java等。 下面是一个Python的示例代码&#xff0c;可以实现这个操作&#xff1a; def reverse_and_rearrange(arr): # 反转数组 …
阅读更多...
git rebase冲突说明（base\remote\local概念说明）

git rebase冲突说明（base\remote\local概念说明）

主线日志及修改 $ git log master -p commit 31213fad6150b9899c7e6b27b245aaa69d2fdcff (master) Author: Date: Tue Nov 28 10:19:53 2023 08004diff --git a/123.txt b/123.txt index 294d779..a712711 100644 --- a/123.txtb/123.txt-1,3 1,4 123 4^Mcommit a77b518156…
阅读更多...
分享几个电视颜色测试图形卡

分享几个电视颜色测试图形卡

介绍 本文分享几个常见的电视颜色测试图形卡和一段matlab程序&#xff0c;完成JPG转FPGA烧写文件&#xff0c;便于把彩色图片预装载到FPGA内。 电视颜色测试图形卡 一种专业检测电视显示效果的工具。它通常由一张卡片和一些色块组成&#xff0c;可以根据标准色彩空间和颜色渐…
阅读更多...
Web安全漏洞分析-XSS（中）

Web安全漏洞分析-XSS（中）

随着互联网的迅猛发展&#xff0c;Web应用的普及程度也愈发广泛。然而&#xff0c;随之而来的是各种安全威胁的不断涌现&#xff0c;其中最为常见而危险的之一就是跨站脚本攻击&#xff08;Cross-Site Scripting&#xff0c;简称XSS&#xff09;。XSS攻击一直以来都是Web安全领…
阅读更多...
版本依赖冲突问题排查过程记录

版本依赖冲突问题排查过程记录

问题 开发平台在集成minio时&#xff0c;pom引入了sdk。 <dependency><groupId>io.minio</groupId><artifactId>minio</artifactId><version>8.5.7</version> </dependency>在调用上传文件API时&#xff0c;控制台报错&…
阅读更多...
如何开启Windows Server 2016 远端桌面

如何开启Windows Server 2016 远端桌面

使用GUI 设定 服务器管理器–> 本地服务器–> 远端桌面 启用远端桌面 远端–> 允许远端连线至此电脑 会提示防火墙设定跟电源设定 防火墙之前已经关闭了 完成
阅读更多...
fpga rom 初始化文件的一些心得

fpga rom 初始化文件的一些心得

目录 可能遇到的问题 问题 解决方案 rom的初始化 用途 文件类型 如何生成初始化文件 示例 Altera Xilinx 可能遇到的问题 问题 altera FPGA的rom找不到初始化文件&#xff0c;编译过程会提示类似的问题 Error(127001): Cant find Memory Initialization File or He…
阅读更多...
Google Earth Engine谷歌地球引擎计算多年中某两个时间点之间遥感数据差值的平均值

Google Earth Engine谷歌地球引擎计算多年中某两个时间点之间遥感数据差值的平均值

本文介绍在谷歌地球引擎GEE中&#xff0c;提取、计算某一种遥感影像产品在连续的多年中&#xff0c;2个不同时相的数据差值的多年平均值&#xff0c;并将计算得到的这一景差值的结果图像导出的方法。 本文是谷歌地球引擎&#xff08;Google Earth Engine&#xff0c;GEE&#x…
阅读更多...
R语言单因素方差分析+差异显著字母法标注+逐行详细解释

R语言单因素方差分析+差异显著字母法标注+逐行详细解释

R语言单因素方差分析 代码如下 df <- read.csv("data.csv",header TRUE,row.names 1) library(reshape2) df <- melt(df,idc()) names(df) <- c(trt, val) df aov1 <- aov(val~trt,datadf) summary(aov1)library(agricolae) data <- LSD.test(aov…
阅读更多...
harmonyOS学习笔记之stateStyles

harmonyOS学习笔记之stateStyles

stateStyles:多态样式 stateStyles可以依据组件的内部状态的不同,设置不同的样式 stateStyles是属性方法,可以根据状态来设置样式,类似于css伪类,但是语法不一样,ArkUI提供了四种状态: focused:获焦态 normal:正常态 pressed:按压态 disable:不可用态例如: Entry Component …
阅读更多...
NAND Flash和NOR Flash的异同

NAND Flash和NOR Flash的异同

NAND Flash和NOR Flash是两种常见的闪存类型。 NOR Flash是Intel于1988年首先开发出来的存储技术&#xff0c;改变了原先由EPROM和EEPROM一统天下的局面。 NAND Flash是东芝公司于1989年发布的存储结构&#xff0c;强调降低每比特的成本&#xff0c;更高的性能&#xff0c;并…
阅读更多...
java企业财务管理系统springboot+jsp

java企业财务管理系统springboot+jsp

1、基本内容 &#xff08;1&#xff09;搭建基础环境&#xff0c;下载JDK、开发工具eclipse/idea。 &#xff08;2&#xff09;通过HTML/CSS/JS搭建前端框架。 &#xff08;3&#xff09;下载MySql数据库&#xff0c;设计数据库表&#xff0c;用于存储系统数据。 &#xff08;4…
阅读更多...
LeedCode刷题---子数组问题

LeedCode刷题---子数组问题

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、最大子数组和 题目链接&#xff1a;最大子数组和 题目描述 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发