devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：我家自动化 | 2024-06-28 21:52:32

赞

踩

双链表操作

目录

一.双向链表的概念

二.双向链表的数据结构

三.双向链表的实现

节点的插入

头插法

尾插法

任意位置插入

节点的删除

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

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

节点的查找

链表的清空

链表的长度

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

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

一.双向链表的概念

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

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

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

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

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

二.双向链表的数据结构

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

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

  1.     public class Node{
  2.         public int data;
  3.         public Node prev;
  4.         public Node next;
  5.         //构造方法，给每个节点赋值
  6.         public Node(int data) {
  7.             this.data = data;
  8.         }
  9.     }

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

  1. public class MyLinkList implements Ilst{
  2.     //节点的数据结构
  3.     public class Node{
  4.         public int data;
  5.         public Node prev;
  6.         public Node next;
  7.         //构造方法
  8.         public Node(int data) {
  9.             this.data = data;
  10.         }
  11.     }
  12.     public Node head;//头节点
  13.     public Node last;//尾节点
  14. }

接口：

  1. public interface Ilst {
  2.     //头插法
  3.     public void addFirst(int data);
  4.     //尾插法
  5.     public void addLast(int data);
  6.     //任意位置插入
  7.     public void addIndex(int index,int data);
  8.     //查找是否包含关键字key是否在链表当中
  9.     public boolean contains(int key);
  10.     //删除第一次出现关键字为key的节点
  11.     public void remove(int key);
  12.     //删除所有值为key的节点
  13.     public void removeAllKey(int key);
  14.     //得到链表的长度
  15.     public int size();
  16.     //展示链表
  17.     public void display();
  18.     //清空链表
  19.     public void clear();
  20. }

三.双向链表的实现

节点的插入

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

头插法

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

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

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

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

  1.     @Override//头插法
  2.     public void addFirst(int data) {
  3.         Node newNode = new Node(data);
  4.         if (head == null){
  5.             head = newNode;
  6.             last = newNode;
  7.         }else {
  8.             newNode.next = head;
  9.             head.prev = newNode;
  10.             //更新头节点
  11.             head = newNode;
  12.         }
  13.     }

尾插法

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

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

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

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

  1.     @Override//尾插法
  2.     public void addLast(int data) {
  3.         Node newNode =  new Node(data);
  4.         if (head == null){
  5.             head = newNode;
  6.             last = newNode;
  7.         }else {
  8.             newNode.prev = last;
  9.             last.next = newNode;
  10.             //更新尾部节点
  11.             last = newNode;
  12.         }
  13.     }

任意位置插入

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

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

 

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

 

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

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

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

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

  1.     @Override//任意位置插入
  2.     public void addIndex(int index, int data) {
  3.         //对输入位置进行判断
  4.         if (index < 0 || index > size()) {
  5.             System.out.println("输入位置不合法");
  6.             return;
  7.         }
  8.         if (index == 0) {
  9.             //如果插入位置在最前面就使用头插
  10.             addFirst(data);
  11.             return;
  12.         }
  13.         if (index == size()) {//这里的size方法在后文中有定义
  14.             //如果插入位置在最后面就使用尾插
  15.             addLast(data);
  16.             return;
  17.         }
  18.         //在中间插入
  19.         Node newNode = new Node(data);
  20.         //找到要插入的位置
  21.         Node cur = head;
  22.         while (index != 1) {
  23.             cur = cur.next;
  24.             index--;
  25.         }
  26.         //将新节点插入到cur之前
  27.         newNode.next = cur;
  28.         newNode.prev = cur.prev;
  29.         cur.prev.next = newNode;
  30.         cur.prev = newNode;
  31. //        //将新节点插入到cur之后
  32. //        newNode.next = cur.next;
  33. //        newNode.prev = cur;
  34. //        cur.next = newNode;
  35. //        newNode.next.prev = newNode;
  36.     
  37.     }

节点的删除

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

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

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

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

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

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

  1. cur.next.prev = cur.prev;
  2. cur.prev.next = cur.next;

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

  1.     @Override//删除第一次出现关键字为key的节点
  2.     public void remove(int key) {
  3.         Node cur = head;
  4.         while (cur != null) {
  5.             if(cur.data == key) {
  6.                 if(cur == head) {
  7.                     head = head.next;
  8.                     if(head != null) {
  9.                         head.prev = null;
  10.                     }else {
  11.                         //只有一个节点 且是需要删除的节点
  12.                         last = null;
  13.                     }
  14.                 }else {
  15.                     if(cur.next != null) {
  16.                         //删除中间节点
  17.                         cur.next.prev = cur.prev;
  18.                         cur.prev.next = cur.next;
  19.                     }else {
  20.                         //删除尾巴节点
  21.                         cur.prev.next = cur.next;
  22.                         last = last.prev;
  23.                     }
  24.                 }
  25.                 return;
  26.             }
  27.             cur = cur.next;
  28.         }
  29.     }

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

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

  1.     @Override//删除所有值为key的节点
  2.     public void removeAllKey(int key) {
  3.         Node cur = head;
  4.         while (cur != null) {
  5.             if(cur.data == key) {
  6.                 if(cur == head) {
  7.                     head = head.next;
  8.                     if(head != null) {
  9.                         head.prev = null;
  10.                     }else {
  11.                         //只有一个节点 且是需要删除的节点
  12.                         last = null;
  13.                     }
  14.                 }else {
  15.                     if(cur.next != null) {
  16.                         //删除中间节点
  17.                         cur.next.prev = cur.prev;
  18.                         cur.prev.next = cur.next;
  19.                     }else {
  20.                         //删除尾巴节点
  21.                         cur.prev.next = cur.next;
  22.                         last = last.prev;
  23.                     }
  24.                 }
  25.             }
  26.             cur = cur.next;
  27.         }
  28.     }

节点的查找

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

  1.     @Override//查找是否包含关键字key是否在链表当中
  2.     public boolean contains(int key) {
  3.         Node cur = head;
  4.         while (cur != null){
  5.             if (cur.data == key){
  6.                 return true;
  7.             }else {
  8.                 cur = cur.next;
  9.             }
  10.         }
  11.         return false;
  12.     }

链表的清空

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

  1.     @Override//清空链表
  2.     public void clear() {
  3.         Node cur = head;
  4.         while (cur != null){
  5.             Node tempNode = cur.next;//记录当前节点的下一个节点的地址
  6.             cur.prev = null;
  7.             cur.next = null;
  8.             cur = tempNode;
  9.         }
  10.         this.head = null;
  11.         this.last = null;
  12.     }

链表的长度

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

  1.     @Override//得到单链表的长度
  2.     public int size() {
  3.         int count = 0;
  4.         Node cur = head;
  5.         while (cur != null) {
  6.             count++;
  7.             cur = cur.next;
  8.         }
  9.         return count;
  10.     }

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

  1. package MyLinkList;
  2.  
  3. public class MyLinkList implements Ilst {
  4.     
  5.     public class Node {
  6.         public int data;
  7.         public Node prev;
  8.         public Node next;
  9.         
  10.         //构造方法
  11.         public Node(int data) {
  12.             this.data = data;
  13.         }
  14.     }
  15.     
  16.     public Node head;
  17.     public Node last;
  18.     
  19.     @Override//头插法
  20.     public void addFirst(int data) {
  21.         Node newNode = new Node(data);
  22.         if (head == null) {
  23.             head = newNode;
  24.             last = newNode;
  25.         } else {
  26.             newNode.next = head;
  27.             head.prev = newNode;
  28.             //更新头节点
  29.             head = newNode;
  30.         }
  31.     }
  32.     
  33.     @Override//尾插法
  34.     public void addLast(int data) {
  35.         Node newNode = new Node(data);
  36.         if (head == null) {
  37.             head = newNode;
  38.             last = newNode;
  39.         } else {
  40.             newNode.prev = last;
  41.             last.next = newNode;
  42.             //更新尾部节点
  43.             last = newNode;
  44.         }
  45.     }
  46.     
  47.     @Override//任意位置插入
  48.     public void addIndex(int index, int data) {
  49.         //对输入位置进行判断
  50.         if (index < 0 || index > size()) {
  51.             System.out.println("输入位置不合法");
  52.             return;
  53.         }
  54.         if (index == 0) {
  55.             //如果插入位置在最前面就使用头插
  56.             addFirst(data);
  57.             return;
  58.         }
  59.         if (index == size()) {
  60.             //如果插入位置在最后面就使用尾插
  61.             addLast(data);
  62.             return;
  63.         }
  64.         //在中间插入
  65.         Node newNode = new Node(data);
  66.         //找到要插入的位置
  67.         Node cur = head;
  68.         while (index != 1) {
  69.             cur = cur.next;
  70.             index--;
  71.         }
  72.         //将新节点插入到cur之前
  73.         newNode.next = cur;
  74.         newNode.prev = cur.prev;
  75.         cur.prev.next = newNode;
  76.         cur.prev = newNode;
  77. //        //将新节点插入到cur之后
  78. //        newNode.next = cur.next;
  79. //        newNode.prev = cur;
  80. //        cur.next = newNode;
  81. //        newNode.next.prev = newNode;
  82.     
  83.     }
  84.     
  85.     @Override//查找是否包含关键字key是否在链表当中
  86.     public boolean contains(int key) {
  87.         Node cur = head;
  88.         while (cur != null){
  89.             if (cur.data == key){
  90.                 return true;
  91.             }else {
  92.                 cur = cur.next;
  93.             }
  94.         }
  95.         return false;
  96.     }
  97.     
  98.     @Override//删除第一次出现关键字为key的节点
  99.     public void remove(int key) {
  100.         Node cur = head;
  101.         while (cur != null) {
  102.             if(cur.data == key) {
  103.                 if(cur == head) {
  104.                     head = head.next;
  105.                     if(head != null) {
  106.                         head.prev = null;
  107.                     }else {
  108.                         //只有一个节点 且是需要删除的节点
  109.                         last = null;
  110.                     }
  111.                 }else {
  112.                     if(cur.next != null) {
  113.                         //删除中间节点
  114.                         cur.next.prev = cur.prev;
  115.                         cur.prev.next = cur.next;
  116.                     }else {
  117.                         //删除尾巴节点
  118.                         cur.prev.next = cur.next;
  119.                         last = last.prev;
  120.                     }
  121.                 }
  122.                 return;
  123.             }
  124.             cur = cur.next;
  125.         }
  126.     }
  127.     
  128.     @Override//删除所有值为key的节点
  129.     public void removeAllKey(int key) {
  130.         Node cur = head;
  131.         while (cur != null) {
  132.             if(cur.data == key) {
  133.                 if(cur == head) {
  134.                     head = head.next;
  135.                     if(head != null) {
  136.                         head.prev = null;
  137.                     }else {
  138.                         //只有一个节点 且是需要删除的节点
  139.                         last = null;
  140.                     }
  141.                 }else {
  142.                     if(cur.next != null) {
  143.                         //删除中间节点
  144.                         cur.next.prev = cur.prev;
  145.                         cur.prev.next = cur.next;
  146.                     }else {
  147.                         //删除尾巴节点
  148.                         cur.prev.next = cur.next;
  149.                         last = last.prev;
  150.                     }
  151.                 }
  152.             }
  153.             cur = cur.next;
  154.         }
  155.     }
  156.     
  157.     @Override//得到单链表的长度
  158.     public int size() {
  159.         int count = 0;
  160.         Node cur = head;
  161.         while (cur != null) {
  162.             count++;
  163.             cur = cur.next;
  164.         }
  165.         return count;
  166.     }
  167.     
  168.     @Override//展示链表
  169.     public void display() {
  170.         Node cur = head;
  171.         while (cur != null) {
  172.             System.out.print(cur.data + " ");
  173.             cur = cur.next;
  174.         }
  175.         System.out.println();
  176.     }
  177.     
  178.     @Override//清空链表
  179.     public void clear() {
  180.         Node cur = head;
  181.         while (cur != null){
  182.             Node tempNode = cur.next;
  183.             cur.prev = null;
  184.             cur.next = null;
  185.             cur = tempNode;
  186.         }
  187.         this.head = null;
  188.         this.last = null;
  189.     }
  190. }

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

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号