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

2023-12-07 22:01
文章标签 链表 详解 查询 操作 数据结构 位置 删除 双向 插入 节点 图文 任意 长度 插法

本文主要是介绍数据结构：图文详解双向链表的各种操作（头插法，尾插法，任意位置插入，查询节点，删除节点，求链表的长度... ...），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一.双向链表的概念

二.双向链表的数据结构

三.双向链表的实现

节点的插入

头插法

尾插法

任意位置插入

节点的删除

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

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

节点的查找

链表的清空

链表的长度

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

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

一.双向链表的概念

双向链表（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.chinasem.cn/article/467506。

相关文章

Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
day-51 合并零之间的节点

day-51 合并零之间的节点

思路 直接遍历链表即可，遇到val=0跳过，val非零则加在一起，最后返回即可 解题过程 返回链表可以有头结点，方便插入，返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2