• Java 数据结构篇-实现双链表的核心API

    🔥博客主页： 小扳_-CSDN博客
    ❤感谢大家点赞👍收藏⭐评论✍     

     

     

    文章目录

            1.0 双链表的说明

            1.1 双链表 - 创建

            1.2 双链表 - 根据索引查找节点

            1.3 双链表 - 根据索引插入节点

            1.4 双链表 - 头插节点

            1.5 双链表 - 尾插

            1.6 双链表 - 根据索引来删除节点

            1.7 头删节点

            1.8 尾删节点

            1.9 实现迭代器循环

            2.0 双链表完整的实现代码

            3.0 环形双链表的说明

            3.1 环形双链表 - 创建

            3.2 环形双链表 - 头插节点

            3.3 环形双链表 - 尾插节点

            3.4 环形双链表 - 头删节点

            3.5 环形双链表 - 尾删节点

            3.6 环形链表 - 根据值来删除节点

            4.0 环形双链表完整的实现代码

            1.0 双链表的说明

            双链表是一种数据结构，其中每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。双链表可以在任意位置插入或删除节点，而不需要像单链表那样遍历整个链表来找到需要操作的位置。双链表可以用于实现栈、队列、以及其他需要快速插入和删除操作的数据结构。由于每个节点包含两个指针，双链表的内存占用量通常比单链表更大。

            1.1 双链表 - 创建

            把双链表封装成一个类，类中还需要封装一个节点类 Node，该节点类的成员有指向前一个节点的变量 Node prev，值 value ，指向后一个节点的变量 Node next 。

    代码如下：

    1. public class MyDoubleLists{
    2.     private final Node hand;
    3.     private final Node tail;
    4.  
    5.     private static class Node {
    6.         public Node prev;
    7.         public Node next;
    8.         public int value;
    9.  
    10.         public Node(Node prev, int value, Node next) {
    11.             this.prev = prev;
    12.             this.next = next;
    13.             this.value = value;
    14.         }
    15.     }
    16.  
    17.     public MyDoubleLists() {
    18.         hand = new Node(null,0,null);
    19.         tail = new Node(hand,-1,null);
    20.         hand.next = tail;
    21.         tail.prev = hand;
    22.     }
    23.  
    24. }

             注意外部类中，还需要定义头节点，尾节点，再利用外部类的构造器中就可以完成对头尾节点的初始化了。内部类中的节点类建议用静态来修饰。

            1.2 双链表 - 根据索引查找节点

            由于这个方法可以为其他几个方法提供服务，因此，把这个方法独立出来。实现思路为：开始的节点应为 hand，循环终止条件为：p == tail 当指向尾节点的那一刻就该结束循环了。还要加一个变量 i = -1 ，每一次循环结束要进行 i++ ,当 i == index 时，找到了该索引的节点，返回该节点即可，若循环结束还是没找到，就得返回 null 。

    代码如下：

    1.     //根据索引查找节点
    2.     private Node findNode(int index) {
    3.         int i = -1;
    4.         for (Node p = hand; p !=tail ; p = p.next,i++){
    5.             if (i == index) {
    6.                 return p;
    7.             }
    8.         }
    9.         return null;
    10.     }

            这个方法一般不会对外开发，因此，加上 private 来修饰，当 i == -1 时，返回的时头节点，所以一开始的节点为 hand 。对外是索引从 0 开始才会存储值的，对于头节点存储什么值是不关心的。

            1.3 双链表 - 根据索引插入节点

             根据索引插入节点，提前需要准备好该节点的前一个节点 prev、该节点的后一个节点 next 。通过以上已经实现的方法来找到插入位置的前一个结点，prev = findNode(index - 1)，后一个节点也就可以找到了，next = prev.next。

    代码如下：

    1.     //根据索引插入节点
    2.     public void insert(int index, int value) {
    3.         Node p = findNode(index - 1);
    4.         if (p == null){
    5.             throw new RuntimeException("用索引访问失败");
    6.         }
    7.         Node prev = p;
    8.         Node next = prev.next;
    9.         Node insertNode = new Node(prev, value,next);
    10.         prev.next = insertNode;
    11.         next.prev = insertNode;
    12.     }

            prev.next 指向新的节点，next.prev 指向上一个节点。新的节点的头节点的引用为 prev，尾节点为 next 。 

             1.4 双链表 - 头插节点

            其实这个方法就比较简单了，这个就是根据索引 0 来插入节点的，就是一个索引等于0的特例，所以可以直接调用已经实现的 insert(0，int value) 方法。

    代码如下：

    1.     //头插节点
    2.     public void addFirst(int value) {
    3.         insert(0,value);
    4.     }

             1.5 双链表 - 尾插

            对尾部的操作是双链表的一个很大的优势，对尾部的查询、增加节点、删除节点效率都很快，因为对尾节点是有记录的，就不用从头开始来查找尾部节点了，直接可以得到。

            实现方法的思路为：需要找到插入的前一个节点，插入的后一个节点肯定是尾节点，所以，可以通过   prev =  tail.prev，来找到插入的前一个节点。

    代码如下：

    1.     //尾插节点
    2.     public void addLast(int value) {
    3.         Node lats = tail;
    4.         Node prev = lats.prev;
    5.         Node addNode = new Node(prev,value,lats);
    6.         prev.next = addNode;
    7.         lats.prev = addNode;
    8.     }

            新的节点的前一个节点为 prev ，后节点为 tail，prev.next 与 tail.prev 就要更改为指向新的节点了。

            1.6 双链表 - 根据索引来删除节点

            先通过已经实现的 findNode() 方法来找到该索引的节点，还有找到删除该节点的前一个节点与后一个节点。

    代码如下：

    1.     //根据索引来删除节点
    2.     public void remove(int index) {
    3.         Node prev = findNode(index - 1);
    4.         if (prev == null) {
    5.             throw new RuntimeException("用索引来删除数据失败！");
    6.         }
    7.         Node remove = prev.next;
    8.         if (remove == tail) {
    9.             throw new RuntimeException("用索引来删除数据失败！");
    10.         }
    11.         Node next = remove.next;
    12.  
    13.         prev.next = next;
    14.         next.prev = next;
    15.     }

             接着就可以将要删除的前一个节点指向要删除的节点后一个节点，但是考虑两种情况，第一种，当要删除的节点没找到，就要抛出异常了。第二种，当发现要删除的节点为 tail 时需要抛出异常，总不能自己把自己的尾巴 "切了吧" 然而不用考虑是否把头节点删除，因为要删除的节点总是拿不到头节点。

             1.7 头删节点

            当索引为0时，就是头删，是 remove(0) 方法的一个特例。可以直接来调用根据索引来删除节点的方法。

    代码如下：

    1.     //头删节点
    2.     public void removeFirst() {
    3.         remove(0);
    4.     }

             1.8 尾删节点

            双链表尾删的效率是很高的，因为对尾节点是有记录的。

    代码如下：

    1.     //尾删节点
    2.     public void removeLast() {
    3.         Node remove = tail.prev;
    4.         if (remove == hand){
    5.             throw new RuntimeException();
    6.         }
    7.         Node prev = remove.prev;
    8.         prev.next = tail;
    9.         tail.prev = prev;
    10.     }

            需要找到三个节点，要删除的节点、删除节点的前一个节点、还有尾节点。需要注意的是，判断要删除的节点为头节点，需要抛出异常，总不能自己把自己的 " 头部 " 给切了吧。

             1.9 实现迭代器循环

            这个完成 Iterable 接口，创建新的该接口子类对象，重写两个方法即可。

    代码如下：

    1.     //实现迭代器循环
    2.     @Override
    3.     public Iterator iterator() {
    4.         return new Iterator() {
    5.             Node p = hand.next;
    6.             @Override
    7.             public boolean hasNext() {
    8.                 return p != tail;
    9.             }
    10.  
    11.             @Override
    12.             public Integer next() {
    13.                 int value = p.value;
    14.                 p = p.next;
    15.                 return value;
    16.             }
    17.         };
    18.  
    19.     }

            需要注意的是，头节点的值是不用在乎的，所以遍历开始为 hand.next ，循环结束条件为，p == tail，遍历到尾节点就要终止了。

            2.0 双链表完整的实现代码

     

    1. import java.util.Iterator;
    2.  
    3. public class MyDoubleLists implements Iterable{
    4.     private final Node hand;
    5.     private final Node tail;
    6.  
    7.     private static class Node {
    8.         public Node prev;
    9.         public Node next;
    10.         public int value;
    11.  
    12.         public Node(Node prev, int value, Node next) {
    13.             this.prev = prev;
    14.             this.next = next;
    15.             this.value = value;
    16.         }
    17.     }
    18.  
    19.     public MyDoubleLists() {
    20.         hand = new Node(null,0,null);
    21.         tail = new Node(hand,-1,null);
    22.         hand.next = tail;
    23.         tail.prev = hand;
    24.     }
    25.  
    26.     //根据索引查找节点
    27.     private Node findNode(int index) {
    28.         int i = -1;
    29.         for (Node p = hand; p !=tail ; p = p.next,i++){
    30.             if (i == index) {
    31.                 return p;
    32.             }
    33.         }
    34.         return null;
    35.     }
    36.  
    37.     //根据索引插入节点
    38.     public void insert(int index, int value) {
    39.         Node p = findNode(index - 1);
    40.         if (p == null){
    41.             throw new RuntimeException("用索引访问失败");
    42.         }
    43.         Node prev = p;
    44.         Node next = prev.next;
    45.         Node insertNode = new Node(prev, value,next);
    46.         prev.next = insertNode;
    47.         next.prev = insertNode;
    48.     }
    49.  
    50.     //头插节点
    51.     public void addFirst(int value) {
    52.         insert(0,value);
    53.     }
    54.  
    55.     //尾插节点
    56.     public void addLast(int value) {
    57.         Node lats = tail;
    58.         Node prev = lats.prev;
    59.         Node addNode = new Node(prev,value,lats);
    60.         prev.next = addNode;
    61.         lats.prev = addNode;
    62.     }
    63.  
    64.     //根据索引来删除节点
    65.     public void remove(int index) {
    66.         Node prev = findNode(index - 1);
    67.         if (prev == null) {
    68.             throw new RuntimeException("用索引来删除数据失败！");
    69.         }
    70.         Node remove = prev.next;
    71.         if (remove == tail) {
    72.             throw new RuntimeException("用索引来删除数据失败！");
    73.         }
    74.         Node next = remove.next;
    75.  
    76.         prev.next = next;
    77.         next.prev = next;
    78.     }
    79.  
    80.     //头删节点
    81.     public void removeFirst() {
    82.         remove(0);
    83.     }
    84.  
    85.     //尾删节点
    86.     public void removeLast() {
    87.         Node remove = tail.prev;
    88.         if (remove == hand){
    89.             throw new RuntimeException();
    90.         }
    91.         Node prev = remove.prev;
    92.         prev.next = tail;
    93.         tail.prev = prev;
    94.     }
    95.  
    96.     //根据索引来查询数据
    97.     public int get(int index) {
    98.         Node find = findNode(index);
    99.         if (find == null){
    100.             throw new RuntimeException("根据该索引找不到数据");
    101.         }
    102.         return find.value;
    103.     }
    104.  
    105.     //实现迭代器循环
    106.     @Override
    107.     public Iterator iterator() {
    108.         return new Iterator() {
    109.             Node p = hand.next;
    110.             @Override
    111.             public boolean hasNext() {
    112.                 return p != tail;
    113.             }
    114.  
    115.             @Override
    116.             public Integer next() {
    117.                 int value = p.value;
    118.                 p = p.next;
    119.                 return value;
    120.             }
    121.         };
    122.  
    123.     }
    124.  
    125. }

            3.0 环形双链表的说明

            环形双链表是一种数据结构，它类似于双向链表，但是链表的最后一个节点指向第一个节点，形成一个环形结构。简单来说，先对比与一般的双链表，环形双链表就是头尾节点都是同一个节点。

            3.1 环形双链表 - 创建

            把环形双链表看成一个对象，该类中需要封装一个节点的内部类，对外不开放的，需要用限制修饰符来修饰。外部类中的成员变为 sentinel ，即作为头节点，也作为尾节点。

    代码如下：

    1. public class MyAnnularDoubleList{
    2.     private final Node sentinel;
    3.     private static class Node {
    4.         public Node prev;
    5.         public int value;
    6.         public Node next;
    7.  
    8.         public Node(Node prev, int value, Node next) {
    9.             this.prev = prev;
    10.             this.value = value;
    11.             this.next = next;
    12.         }
    13.     }
    14.  
    15.     public MyAnnularDoubleList() {
    16.         sentinel = new Node(null,0,null);
    17.         sentinel.prev = sentinel;
    18.         sentinel.next = sentinel;
    19.     }
    20.  
    21. }

            在创建环形双链表时，在用无参构造器就可以先把 sentinel 初始化了。

            3.2 环形双链表 - 头插节点

            根据 next =  sentinel.next 就可以得到插入点的下一个节点，就可以把新节点的指向的前一个节点来指向 sntinel，新节点的指向后一个节点来指向 next 。

            这里需要考虑一种情况，假设，该环形双链表中就只有一个 sentinel 节点，以上阐述的思路还能不能用呢？答案时可以的，如果实在理解不了的话，可以把一个 sentinel 节点，想象成两个 sentinel 节点，效果都是一样的，都是指向自己嘛。

    代码如下：

    1.     //头插节点
    2.     public void addFirst(int value) {
    3.         Node hand = sentinel;
    4.         Node tail = sentinel.next;
    5.         Node addNode = new Node(hand,value,tail);
    6.         hand.next = addNode;
    7.         tail.prev = addNode;
    8.     }

            3.3 环形双链表 - 尾插节点

            根据 prev = sentinel.prev 来找到插入节点的前一个的节点，插入节点的后一个节点就是 sentinel ，新节点的指向前的节点为 prev，新节点的指向后的节点为 sentinel ，接着 prev.next 指向新节点，sentinel.prev 指向新节点。

    代码如下：

    1.     //尾插节点
    2.     public void addLast(int value) {
    3.         Node prev = sentinel.prev;
    4.         Node next = sentinel;
    5.         Node addNode = new Node(prev,value,next);
    6.         prev.next = addNode;
    7.         next.prev = addNode;
    8.  
    9.     }

            同理，不需要额外考虑当节点只有一个时，以上代码依旧可以实现尾插节点。

            3.4 环形双链表 - 头删节点

            根据 remove = sentinel.next ，可以得到需要删除的节点，再由 next = remove.next，得到删除节点的后一个节点，这样三个节点后已知了，santinel.next 指向 next ，next.prev 指向sentinel ，剩下的没有被引用的节点（对象），会被 JVM 自动回收。

    代码如下：

    1.     //头删节点
    2.     public void removeFirst() {
    3.         Node remove = sentinel.next;
    4.         if (remove == sentinel) {
    5.             throw new RuntimeException("删除失败！");
    6.         }
    7.         Node next = remove.next;
    8.         sentinel.next = next;
    9.         next.prev = sentinel;
    10.     }

            需要注意的是，当删除的节点为 sentinel 需要抛出异常，但是个人感觉不加判断也可以，sentinel 根本不会被删除，即使只有 sentinel 一直被删除。

            3.5 环形双链表 - 尾删节点

            根据 remove = sentinel.prev 得到需要删除的节点，通过 prev = remove.prev 得到需要删除的前一个节点，prev.next 指向 sentinel，sentinel.prev 指向 prev 即可。

    代码如下：

    1.     //尾删节点
    2.     public void removeLast() {
    3.         Node remove = sentinel.prev;
    4.         Node prev = remove.prev;
    5.         prev.next = sentinel;
    6.         sentinel.prev = prev;
    7.     }

            同样的，当删除的节点为 sentinel 需要抛出异常，但是个人感觉不加判断也可以，sentinel 根本不会被删除，即使只有 sentinel 一直被删除。

             3.6 环形链表 - 根据值来删除节点

            先独立一个方法，根据值来查询节点，一开始的循环节点为 sentinel.next ，对于 sentinel 里面的值是什么根本不在乎的。循环终止条件为：p == sentinel 已经转完一圈了。找到就返回该节点，找不到就返回 null 。删除的原理是一样的，得先找到三个节点，然后把前后节点直接关联起来。

    代码如下：

    1.     //根据值来删除节点
    2.     private Node findValue (int value) {
    3.         for (Node p = sentinel.next; p != sentinel; p = p.next) {
    4.             if (p.value == value) {
    5.                 return p;
    6.             }
    7.         }
    8.         return null;
    9.     }
    10.  
    11.     public void removeValue (int value) {
    12.         Node remove = findValue(value);
    13.         if (remove == null) {
    14.             throw new RuntimeException("找不到该数据来删除相对应的节点");
    15.         }
    16.         Node prev = remove.prev;
    17.         Node next = remove.next;
    18.         prev.next = next;
    19.         next.prev = prev;
    20.     }

            需要注意的是，当接收到的节点为 null 时，需要抛出异常，找不到对应该值的节点。

            4.0 环形双链表完整的实现代码

    1. import java.util.Iterator;
    2.  
    3. public class MyAnnularDoubleList implements Iterable{
    4.     private final Node sentinel;
    5.     private static class Node {
    6.         public Node prev;
    7.         public int value;
    8.         public Node next;
    9.  
    10.         public Node(Node prev, int value, Node next) {
    11.             this.prev = prev;
    12.             this.value = value;
    13.             this.next = next;
    14.         }
    15.     }
    16.  
    17.     public MyAnnularDoubleList() {
    18.         sentinel = new Node(null,0,null);
    19.         sentinel.prev = sentinel;
    20.         sentinel.next = sentinel;
    21.     }
    22.  
    23.     //头插节点
    24.     public void addFirst(int value) {
    25.         Node hand = sentinel;
    26.         Node tail = sentinel.next;
    27.         Node addNode = new Node(hand,value,tail);
    28.         hand.next = addNode;
    29.         tail.prev = addNode;
    30.     }
    31.  
    32.     //尾插节点
    33.     public void addLast(int value) {
    34.         Node prev = sentinel.prev;
    35.         Node next = sentinel;
    36.         Node addNode = new Node(prev,value,next);
    37.         prev.next = addNode;
    38.         next.prev = addNode;
    39.  
    40.     }
    41.  
    42.  
    43.     //头删节点
    44.     public void removeFirst() {
    45.         Node remove = sentinel.next;
    46.         if (remove == sentinel) {
    47.             throw new RuntimeException("删除失败！");
    48.         }
    49.         Node next = remove.next;
    50.         sentinel.next = next;
    51.         next.prev = sentinel;
    52.     }
    53.  
    54.     //尾删节点
    55.     public void removeLast() {
    56.         Node remove = sentinel.prev;
    57.         Node prev = remove.prev;
    58.         prev.next = sentinel;
    59.         sentinel.prev = prev;
    60.     }
    61.  
    62.     //根据值来删除节点
    63.     private Node findValue (int value) {
    64.         for (Node p = sentinel.next; p != sentinel; p = p.next) {
    65.             if (p.value == value) {
    66.                 return p;
    67.             }
    68.         }
    69.         return null;
    70.     }
    71.  
    72.     public void removeValue (int value) {
    73.         Node remove = findValue(value);
    74.         if (remove == null) {
    75.             throw new RuntimeException("找不到该数据来删除相对应的节点");
    76.         }
    77.         Node prev = remove.prev;
    78.         Node next = remove.next;
    79.         prev.next = next;
    80.         next.prev = prev;
    81.     }
    82.  
    83.     //实现迭代器
    84.     @Override
    85.     public Iterator iterator() {
    86.         return new Iterator() {
    87.             Node p = sentinel.next;
    88.             @Override
    89.             public boolean hasNext() {
    90.                 return p != sentinel;
    91.             }
    92.  
    93.             @Override
    94.             public Integer next() {
    95.                 int value = p.value;
    96.                 p = p.next;
    97.                 return value;
    98.             }
    99.         };
    100.     }
    101. }

  • 相关阅读:
    rust学习—— 不一样的break
    Java项目：SSM企业工资管理系统
    C++编程语言的深度解析: 从零开始的学习路线
    TRCX：触摸屏（TSP）分析
    基于Django的租房数据展示系统设计与实现
    Java基于springboot+vue的企业人事员工工资考勤管系统 nodejs 前后端分离
    阿里P8大佬，整理的从零构建企业级容器集群实战笔记，真涨薪神器
    批量加载excel的xsl文件到hive分区表
    MySQL8.0爬坑二三事
    响应式网页设计（Responsive Web Design）的核心原理
  • 原文地址：https://blog.csdn.net/Tingfeng__/article/details/134276107