• 数据结构-双链表思路解析及代码实现

    双链表是单链表的进阶版，单链表是1-2-3-4 一个个排排坐链接，只管向后拉手，其主要思想是当前节点与下一节点的关系，那么双链表就多了一层关系，当前节点不仅和一下一点连起来，也要和上一节点串联起来。与前与后都要拉手。

    如果对单链表不熟悉，建议先去看看单链表实现方式，链接如下

    单链表实现代码以及解析

    咱们还是先以定义节点开始，单链表是有当前节点和下一个节点的定义，那双向链表就需要有上一节点的定义，那就可以如下代码表现：

    1.  public class DoubleLinked {
    2.  
    3.     // 定义一个内部节点类
    4.     private static class Node {
    5.         // 当前节点
    6.         E item;
    7.         // 上一节点
    8.         Node prev;
    9.         // 下一节点
    10.         Node next;
    11.  
    12.         public Node(E item,  Node prev,Node next) {
    13.             this.item = item;
    14.             this.prev = prev;
    15.             this.next = next;
    16.         }
    17.     }
    18. }

    1.添加节点

    有了节点的定义就可以操作了，咱们先来添加操作

    添加节点默认添加到尾部，所以调用linkLast方法，我们假如要添加1-2-3，我们要考虑添加了1以后，需要把2添加到1后，添加到3以后需要考虑2添加到3前等情况，咱们来逐个分析。

    存储第一个节点时

    1.我们需要实例化一个1的节点，因为不知道上一个节点值所以prev需要为空，也因为不知道下一个节点值所以next值需要为空，这样第一个值也就设置好了，那么设置好的值存储在哪里呢？才能把后面的值串连在一起，这时我们用全局变量first节点做这个事情

    存储中间节点时

    假设第一个节点存储好，那么添加第二个节点为2的值，操作又是什么？

    当前节点为2的时候需要知道上一个节点值是1，下一个节点仍然不知道所以为空，所以构造方法就是 new Node(2,1,null)，但是怎么知道上一个节点的值呢，这时候就需要添加个全局变量last，用来存储最后一个值，当第一个节点1存储进来时将1存储到last，第二个节点2过来的时候则直接用last也就是1就可， 用完后将last改为2，后面都以此种方式，就保证了last相比最新值时为上一个值。

    1.     // 首值
    2.     private Node first;
    3.     // 最后值
    4.     private Node last;
    5.     private int size;
    6.  
    7.     public boolean add(E e) {
    8.         linkLast(e);
    9.         return true;
    10.     }
    11.  
    12.     // 1-2-3
    13.     void linkLast(E e) {
    14.         // 上一个值，在第一次存储时为空
    15.         Node l = last;
    16.         // 新节点
    17.         Node newNode = new Node(e, last, null);
    18.         // 将新节点赋值给last
    19.         last = newNode;
    20.         // 第一次存储直接赋值给first即可
    21.         if (l == null) {
    22.             first = newNode;
    23.         } else {
    24.             // 通过引用类型的概念，此种方式则可让first串起来
    25.             // 第二次及以后的值需要将上一个值的next设置为当前新的节点
    26.             l.next = newNode;
    27.         }
    28.         size++;
    29.     }
    30.  
    31.     // 打印链表数据
    32.     private void printData() {
    33.         Node f = null;
    34.         for (int i = 0; i < size; i++) {
    35.             if (i == 0) {
    36.                 System.out.print(first.item);
    37.                 f = first.next;
    38.             } else {
    39.                 System.out.print("-" + f.item);
    40.                 f = f.next;
    41.             }
    42.  
    43.         }
    44.         System.out.println("");
    45.     }
    1.    public static void main(String[] args) {
    2.         DoubleLinked doubleLinked = new DoubleLinked();
    3.         doubleLinked.add("1");
    4.         doubleLinked.add("2");
    5.         doubleLinked.add("3");
    6.  
    7.         doubleLinked.printData();
    8.         System.out.println("添加完毕-----------");
    9.     }

     结果：

    2.查询元素

    根据小标索引查询链表数据，它这里用了将当前的链表长度除2，如果你要搜索的索引小于我计算过后的数字就证明你要找的位置比较靠前，所以就从头开始向后找（也就是说从first全局变量里循环取出next的数据），如果相反则证明你要找的数据在中后部分，需要从后向前找(也就是从last全局变量循环取出prev数据)，还算蛮简单的哈。

    1.   // 根据索引获取链表元素
    2.  public E get(int index) {
    3.      return node(index).item;
    4.  }  
    5.  
    6.  Node node(int index) {
    7.         // 右移1位相当于除以2
    8.         int i = size >> 1;
    9.         // 如果要找的索引不大于i，则从前往后找最快
    10.         if (index < i) {
    11.             Node find = first;
    12.             for (int i1 = 0; i1 < index; i1++) {
    13.                 find = find.next;
    14.             }
    15.             return find;
    16.         } else {
    17.             // 如果要找的索引大于i，则从后往前找更快
    18.             Node find = last;
    19.             for (int i1 = size - 1; i1 > index; i1--) {
    20.                 find = find.prev;
    21.             }
    22.             return find;
    23.         }
    24.     }

     3.删除

    删除节点，毋庸置疑我们要移动前后节点，挤出待删除节点。

    待删除为中间节点的话：

     比如1-2-3-4-5 我需要将2删除，索引就是1，需要将2的前一个节点也就是1找到，然后将1的下一个节点改为3，将2的下一个节点3找到，将3的上一个节点改为1，这样2的这个节点自然就删除了，这是删除中间的链表

    待删除是头节点第一个的话：

    假如1-2-3-4-5 删除的是1，索引就是0，此时1的节点上一个是空，这时需要找到当前节点的下一个节点直接赋值头节点即可。

    待删除是最后一个节点的话：

    假如1-2-3-4-5 删除的是5，索引就是4，此时下一个节点就是空，这时需要找到当前节点的上一个节点置为空即可。

    1.     // 1-2-3-4-5
    2.     public boolean remove(int index) {
    3.         // 得到待删除的节点
    4.         Node node = node(index);
    5.         // 得到删除的节点前一个节点
    6.         Node prev = node.prev;
    7.         // 得到删除的节点后一个节点
    8.         Node next = node.next;
    9.         // 当前节点前一个为空，则证明要删除第一个，直接将当前值下一个节点覆盖first即可
    10.         if (prev == null) {
    11.             first = next;
    12.         } else {
    13.             // 给上一个节点的next节点改成当前节点的下一个
    14.             prev.next = next;
    15.             if (next != null) {
    16.                 // 给下一个节点的prev节点改成当前节点的上一个
    17.                 next.prev = prev;
    18.             }
    19.         }
    20.         size--;
    21.         return true;
    22.     }
    1. public static void main(String[] args) {
    2.         DoubleLinked doubleLinked = new DoubleLinked();
    3.         doubleLinked.add("1");
    4.         doubleLinked.add("2");
    5.         doubleLinked.add("3");
    6.         doubleLinked.add("4");
    7.         doubleLinked.add("5");
    8.  
    9.         doubleLinked.printData();
    10.         System.out.println("添加完毕-----------");
    11.  
    12.         System.out.println("查找元素2：" + doubleLinked.get(1));
    13.         System.out.println("查找元素1：" + doubleLinked.get(0));
    14.         System.out.println("查找元素3：" + doubleLinked.get(2));
    15.  
    16.  
    17.         System.out.println("删除2：" + doubleLinked.remove(1));
    18.         System.out.println("删除3：" + doubleLinked.remove(1));
    19.         System.out.println("删除1：" + doubleLinked.remove(0));
    20.         doubleLinked.printData();
    21.  
    22.     }

     

    4.更新节点

    更新节点比较简单，不用移动前后距离，直接找到当前节点并更新就好

    1.     // 更新节点
    2.     public E set(int index, E element) {
    3.         Node currentNode = node(index);
    4.         // 找到当前节点
    5.         E oldValue = currentNode.item;
    6.         // 直接更新当前的节点
    7.         currentNode.item = element;
    8.         return oldValue;
    9.     }

    整体代码：

    1. package linkedList;
    2.  
    3. import java.util.LinkedList;
    4.  
    5. /**
    6.  * @Author df 双链表实现
    7.  * @Date 2022/11/19 10:47
    8.  * @Version 1.0
    9.  */
    10. public class DoubleLinked {
    11.  
    12.     // 定义一个内部节点类
    13.     private static class Node {
    14.         // 当前节点
    15.         E item;
    16.         // 上一节点
    17.         Node prev;
    18.         // 下一节点
    19.         Node next;
    20.  
    21.         public Node(E item, Node prev, Node next) {
    22.             this.item = item;
    23.             this.prev = prev;
    24.             this.next = next;
    25.         }
    26.     }
    27.  
    28.     // 首值
    29.     private Node first;
    30.     // 最后值
    31.     private Node last;
    32.     private int size;
    33.  
    34.     public boolean add(E e) {
    35.         linkLast(e);
    36.         return true;
    37.     }
    38.  
    39.     // 1-2-3
    40.     void linkLast(E e) {
    41.         Node l = last;
    42.         Node newNode = new Node(e, last, null);
    43.         last = newNode;
    44.         if (l == null) {
    45.             first = newNode;
    46.         } else {
    47.             l.next = newNode;
    48.         }
    49.         size++;
    50.     }
    51.  
    52.     // 根据索引获取链表元素
    53.     public E get(int index) {
    54.         return node(index).item;
    55.     }
    56.  
    57.     // 1-2-3-4-5
    58.     public boolean remove(int index) {
    59.         // 得到待删除的节点
    60.         Node node = node(index);
    61.         // 得到删除的节点前一个节点
    62.         Node prev = node.prev;
    63.         // 得到删除的节点后一个节点
    64.         Node next = node.next;
    65.         // 当前节点前一个为空，则证明要删除第一个，直接将当前值下一个节点覆盖first即可
    66.         if (prev == null) {
    67.             first = next;
    68.         } else {
    69.             // 给上一个节点的next节点改成当前节点的下一个
    70.             prev.next = next;
    71.             if (next != null) {
    72.                 // 给下一个节点的prev节点改成当前节点的上一个
    73.                 next.prev = prev;
    74.             }
    75.         }
    76.         size--;
    77.         return true;
    78.     }
    79.  
    80.  
    81.     // 更新节点
    82.     public E set(int index, E element) {
    83.         Node currentNode = node(index);
    84.         // 找到当前节点
    85.         E oldValue = currentNode.item;
    86.         // 直接更新当前的节点
    87.         currentNode.item = element;
    88.         return oldValue;
    89.     }
    90.  
    91.     Node node(int index) {
    92.         // 右移1位相当于除以2
    93.         int i = size >> 1;
    94.         // 如果要找的索引不大于i，则从前往后找最快
    95.         if (index < i) {
    96.             Node find = first;
    97.             for (int i1 = 0; i1 < index; i1++) {
    98.                 find = find.next;
    99.             }
    100.             return find;
    101.         } else {
    102.             // 如果要找的索引大于i，则从后往前找更快
    103.             Node find = last;
    104.             for (int i1 = size - 1; i1 > index; i1--) {
    105.                 find = find.prev;
    106.             }
    107.             return find;
    108.         }
    109.     }
    110.  
    111.     private void printData() {
    112.         Node f = null;
    113.         for (int i = 0; i < size; i++) {
    114.             if (i == 0) {
    115.                 System.out.print(first.item);
    116.                 f = first.next;
    117.             } else {
    118.                 System.out.print("-" + f.item);
    119.                 f = f.next;
    120.             }
    121.         }
    122.         System.out.println("");
    123.     }
    124.  
    125.     public static void main(String[] args) {
    126.         DoubleLinked doubleLinked = new DoubleLinked();
    127.         doubleLinked.add("1");
    128.         doubleLinked.add("2");
    129.         doubleLinked.add("3");
    130.         doubleLinked.add("4");
    131.         doubleLinked.add("5");
    132.  
    133.         doubleLinked.printData();
    134.         System.out.println("添加完毕-----------");
    135.  
    136.         System.out.println("查找元素2：" + doubleLinked.get(1));
    137.         System.out.println("查找元素1：" + doubleLinked.get(0));
    138.         System.out.println("查找元素3：" + doubleLinked.get(2));
    139.  
    140.  
    141.         System.out.println("删除2：" + doubleLinked.remove(1));
    142.         System.out.println("删除3：" + doubleLinked.remove(1));
    143.         System.out.println("删除1：" + doubleLinked.remove(0));
    144.         doubleLinked.printData();
    145.  
    146.         System.out.println("更改元素5为6：" + doubleLinked.set(1,"6"));
    147.         doubleLinked.printData();
    148.  
    149.     }
    150. }

     

     

  • 相关阅读:
    电脑换cpu要重装系统吗
    m基于遗传优化算法的公式参数拟合matlab仿真
    SpringBoot中properties和yml有什么区别？
    程序员的数学课02 逻辑与沟通，怎样才能讲出有逻辑的话？
    Windows 11 手机诞生，还是双屏的？
    百度ERNIE 3.0——中文情感分析实战
    python&selenium自动化测试实战项目
    计算鞍点c++
    python企业微信小程序发送信息
    计算机图形学(三) -- 3D 变换
  • 原文地址：https://blog.csdn.net/dfBeautifulLive/article/details/127933690