devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

7-无头双向非循环链表_非循环双向链表

作者：很楠不爱3 | 2024-06-16 10:20:24

赞

踩

非循环双向链表

目录

1.定义

2.代码

2.1.车厢类

2.2.火车类

2.2.1.在链表的头部添加节点

2.2.2.在链表的尾部添加节点

2.2.3.在链表的任意位置index处添加节点

2.2.4.查询链表的任意位置index处的节点值

2.2.5.修改链表中任意位置index处的节点值

2.2.6.传入一个双向链表节点，将该节点从双向链表中删除

2.2.7.删除链表中第一次出现某个值的节点

2.2.8.删除链表中值为val的所有节点

2.2.9.判断链表的index是否合法

2.2.10.根据index与size的大小关系快速定位指定index位置的节点

2.2.11.toString()方法

2.3.总代码实现

1.定义

既要存储下一个节点地址，还要存储前一个节点地址。是Java的集合框架中LinkedList底层实现。

2.代码

2.1.车厢类

  1. /**
  2.  * 车厢类
  3.  */
  4. class DoubleNode{
  5.     //指向前驱节点
  6.     DoubleNode prev;
  7.     //存储的具体元素
  8.     int val;
  9.     //指向后继节点
  10.     DoubleNode next;
  11.  
  12.     //有参构造
  13.     public DoubleNode(int val){
  14.         this.val=val;
  15.     }
  16. }

2.2.火车类

  1. /**
  2.  * 火车类 基于int的双向链表
  3.  */
  4. public class DoubleLinkedList {
  5.     //存储的具体车厢个数
  6.     private int size;
  7.     //头节点
  8.     private DoubleNode first;
  9.     //尾节点
  10.     private DoubleNode last;
  11.  
  12.     //具体方法实现
  13.     //...
  14. }

2.2.1.在链表的头部添加节点

  1. /**
  2.  * 头插
  3.  * @param val
  4.  */
  5. public void addFirst(int val) {
  6.     //引入一个局部变量，暂时存储一下头节点的地址
  7.     DoubleNode f = first;
  8.     //要插入一个节点，首先要new一个节点
  9.     DoubleNode node = new DoubleNode(val);
  10.     first = node; //因为是头插，那么这行代码不管当前链表是否为空都会执行
  11.     if(f == null) { //若链表为空，则新建的节点既是头节点又是尾节点
  12.         last = node;
  13.     } else {
  14.         node.next = f;
  15.         f.prev = node;
  16.     }
  17.     size++;
  18. }

2.2.2.在链表的尾部添加节点

  1. /**
  2.  * 尾插
  3.  * @param val
  4.  */
  5. public void addLast(int val) {
  6.     //引入一个局部变量，暂时存储一下尾节点的地址
  7.     DoubleNode l = last;
  8.     DoubleNode node = new DoubleNode(val);
  9.     last = node;
  10.     if(l == null) {
  11.         first = node;
  12.     } else {
  13.         node.prev = l;
  14.         l.next = node;
  15.     }
  16.     size++;
  17. }

2.2.3.在链表的任意位置index处添加节点

  1. /**
  2.  * 任意index处添加元素
  3.  * @param val
  4.  */
  5. public void addIndex(int index, int val) {
  6.     if(index < 0 || index > size) {
  7.         System.err.println("add index illegal!");
  8.         return;
  9.     } else if(index == 0) {
  10.         addFirst(val);
  11.     } else if(index == size) {
  12.         addLast(val);
  13.     } else {
  14.         //此时0 < index < size
  15.         //在报错方法(未写)上使用快捷键Alt+Enter,自动生成指定方法
  16.         DoubleNode node = node(index);
  17.         //指向当前位置的前驱节点
  18.         DoubleNode prev = node.prev;
  19.         //要插入的新节点
  20.         DoubleNode newNode = new DoubleNode(val);
  21.         //先处理后半部分引用链
  22.         newNode.next = node; ①
  23.         node.prev = newNode; ②
  24.         //再处理前半部分引用链
  25.         prev.next = newNode; ③
  26.         newNode.prev = prev; ④
  27.         size++;
  28.     }
  29. }

2.2.4.查询链表的任意位置index处的节点值

  1. /**
  2.  * 根据index索引取得节点值
  3.  * @param index
  4.  * @return
  5.  */
  6. public int get(int index) {
  7.     if(rangeCheck(index)) {
  8.         DoubleNode node = node(index);
  9.         return node.val;
  10.     } else {
  11.         System.out.println("get index illegal!");
  12.         return -1;
  13.     }
  14. }

2.2.5.修改链表中任意位置index处的节点值

  1. /**
  2.  * 修改index处的值为newVal
  3.  * @param index
  4.  * @param newVal
  5.  */
  6. public void set(int index, int newVal) {
  7.     if(rangeCheck(index)) {
  8.         DoubleNode node = node(index);
  9.         node.val = newVal;
  10.     } else {
  11.         System.out.println("set index illegal!");
  12.     }
  13. }

2.2.6.传入一个双向链表节点，将该节点从双向链表中删除

  1. /**
  2.  * 传入一个双向链表节点，将该节点从双向链表中删除
  3.  * 核心思想 分治，先处理前驱或后继，再处理另一半的情况
  4.  * @param node
  5.  */
  6. private void unlinkNode(DoubleNode node) {
  7.     //待删除节点的前驱
  8.     DoubleNode prev = node.prev;
  9.     //待删除结点的后继
  10.     DoubleNode next = node.next;
  11.         
  12.     //先处理前半部分引用链
  13.     //判断边界
  14.     if(prev == null) {
  15.         //说明此时待删除的节点恰好是头节点
  16.         first = next;
  17.     } else {
  18.         //此时前驱节点不为空
  19.         prev.next = next;
  20.         node.prev = null;
  21.     }
  22.         
  23.     //再处理后半部分引用链
  24.     if(next == null) {
  25.         last = prev;
  26.     } else {
  27.         //此时后继节点不为空
  28.         next.prev = prev;
  29.         node.next = null;
  30.     }
  31.     size--;
  32. }

2.2.7.删除链表中第一次出现某个值的节点

  1. /**
  2.  * 删除第一次出现值为val的元素
  3.  * @param val
  4.  */
  5. public void removeValueOnce(int val) {
  6.     //只需要从头开始遍历
  7.     for (DoubleNode x = first; x != null; x = x.next) {
  8.         if(x.val == val) {
  9.             unlinkNode(x);
  10.             return;
  11.         }
  12.     }
  13. }

2.2.8.删除链表中值为val的所有节点

  1. /**
  2.  * 删除单链表中所有值为val的节点
  3.  * @param val
  4.  */
  5. public void removeAllValue(int val) {
  6.     for(DoubleNode x = first; x != null;) {
  7.         if(x.val == val){
  8.             //x就是待删除的元素
  9.             //先暂存一下next的节点地址
  10.             DoubleNode next = x.next;
  11.             unlinkNode(x);
  12.             x = next; //真正让x走向next
  13.         } else {
  14.             x = x.next;
  15.         }
  16.     }
  17. }

2.2.9.判断链表的index是否合法

  1. /**
  2.  * 判断链表的index是否合法
  3.  * @param index
  4.  * @return
  5.  */
  6. private boolean rangeCheck(int index) {
  7.     if(index < 0 || index >= size) {
  8.         return false;
  9.     }
  10.     return true;
  11. }

2.2.10.根据index与size的大小关系快速定位指定index位置的节点

  1. /**
  2.  * 根据index与size的大小关系快速定位指定index位置的节点
  3.  * @param index
  4.  * @return
  5.  */
  6. private DoubleNode node(int index) {
  7.     if(index < size >> 1) {
  8.         //从头向后
  9.         DoubleNode node = first;
  10.         for (int i = 0; i < index; i++) {
  11.             node = node.next;
  12.         }
  13.         return node;
  14.     } else {
  15.         //从后向前
  16.         DoubleNode node = last;
  17.         for (int i = size-1; i > index; i--) {
  18.             node = node.prev;
  19.         }
  20.         return node;
  21.     }
  22. }

2.2.11.toString()方法

  1. public String toString() {
  2.     String ret = "";
  3.     DoubleNode node = first;
  4.     while(node != null) {
  5.         ret += node.val + "->";
  6.         node = node.next;
  7.     }
  8.     ret += "NULL";
  9.     return ret;
  10. }

2.3.总代码实现

  1. /**
  2.  * 车厢类
  3.  */
  4. class DoubleNode{
  5.     //指向前驱节点
  6.     DoubleNode prev;
  7.     //存储的具体元素
  8.     int val;
  9.     //指向后继节点
  10.     DoubleNode next;
  11.  
  12.     //有参构造
  13.     public DoubleNode(int val){
  14.         this.val=val;
  15.     }
  16. }
  17.  
  18. /**
  19.  * 火车类 基于int的双向链表
  20.  */
  21. public class DoubleLinkedList {
  22.     //存储的具体车厢个数
  23.     private int size;
  24.     //头节点
  25.     private DoubleNode first;
  26.     //尾节点
  27.     private DoubleNode last;
  28.  
  29.     /**
  30.      * 头插
  31.      * @param val
  32.      */
  33.     public void addFirst(int val){
  34.         //引入一个局部变量，暂时存储一下头节点的地址
  35.         DoubleNode f=first;
  36.         //要插入一个节点，首先要new一个节点
  37.         DoubleNode node=new DoubleNode(val);
  38.         first=node;
  39.         if(f==null){
  40.             last=node;
  41.         }else{
  42.             node.next=f;
  43.             f.prev=node;
  44.         }
  45.         size++;
  46.     }
  47.  
  48.     /**
  49.      * 尾插
  50.      * @param val
  51.      */
  52.     public void addLast(int val) {
  53.         //引入一个局部变量，暂时存储一下尾节点的地址
  54.         DoubleNode l = last;
  55.         DoubleNode node = new DoubleNode(val);
  56.         last = node;
  57.         if(l == null) {
  58.             first = node;
  59.         } else {
  60.             node.prev = l;
  61.             l.next = node;
  62.         }
  63.         size++;
  64.     }
  65.  
  66.     /**
  67.      * 任意index处添加元素
  68.      * @param val
  69.      */
  70.     public void addIndex(int index, int val) {
  71.         if(index < 0 || index > size) {
  72.             System.err.println("add index illegal!");
  73.             return;
  74.         } else if(index == 0) {
  75.             addFirst(val);
  76.         } else if(index == size) {
  77.             addLast(val);
  78.         } else {
  79.             //此时0 < index < size
  80.             //在报错方法(未写)上使用快捷键Alt+Enter,自动生成指定方法
  81.             DoubleNode node = node(index);
  82.             //指向当前位置的前驱节点
  83.             DoubleNode prev = node.prev;
  84.             //要插入的新节点
  85.             DoubleNode newNode = new DoubleNode(val);
  86.             //先处理后半部分引用链
  87.             newNode.next = node;
  88.             node.prev = newNode;
  89.             //再处理前半部分引用链
  90.             prev.next = newNode;
  91.             newNode.prev = prev;
  92.             size++;
  93.         }
  94.     }
  95.  
  96.     /**
  97.      * 根据index索引取得节点值
  98.      * @param index
  99.      * @return
  100.      */
  101.     public int get(int index) {
  102.         if(rangeCheck(index)) {
  103.             DoubleNode node = node(index);
  104.             return node.val;
  105.         } else {
  106.             System.out.println("get index illegal!");
  107.             return -1;
  108.         }
  109.     }
  110.  
  111.     /**
  112.      * 修改index处的值为newVal
  113.      * @param index
  114.      * @param newVal
  115.      */
  116.     public void set(int index, int newVal) {
  117.         if(rangeCheck(index)) {
  118.             DoubleNode node = node(index);
  119.             node.val = newVal;
  120.         } else {
  121.             System.out.println("set index illegal!");
  122.         }
  123.     }
  124.  
  125.     /**
  126.      * 传入一个双向链表节点，将该节点从双向链表中删除
  127.      * 核心思想 分治，先处理前驱或后继，再处理另一半的情况
  128.      * @param node
  129.      */
  130.     private void unlinkNode(DoubleNode node) {
  131.         //待删除节点的前驱
  132.         DoubleNode prev = node.prev;
  133.         //待删除结点的后继
  134.         DoubleNode next = node.next;
  135.  
  136.         //先处理前半部分引用链
  137.         //判断边界
  138.         if(prev == null) {
  139.             //说明此时待删除的节点恰好是头节点
  140.             first = next;
  141.         } else {
  142.             //此时前驱节点不为空
  143.             prev.next = next;
  144.             node.prev = null;
  145.         }
  146.  
  147.         //再处理后半部分引用链
  148.         if(next == null) {
  149.             last = prev;
  150.         } else {
  151.             //此时后继节点不为空
  152.             next.prev = prev;
  153.             node.next = null;
  154.         }
  155.         size--;
  156.     }
  157.  
  158.     /**
  159.      * 删除第一次出现值为val的元素
  160.      * @param val
  161.      */
  162.     public void removeValueOnce(int val) {
  163.         //只需要从头开始遍历
  164.         for (DoubleNode x = first; x != null; x = x.next) {
  165.             if(x.val == val) {
  166.                 unlinkNode(x);
  167.                 return;
  168.             }
  169.         }
  170.     }
  171.  
  172.     /**
  173.      * 删除单链表中所有值为val的节点
  174.      * @param val
  175.      */
  176.     public void removeAllValue(int val){
  177.         for(DoubleNode x=first;x!=null;){
  178.             if(x.val==val){
  179.                 //x就是待删除的元素
  180.                 //先暂存一下next的节点地址
  181.                 DoubleNode next=x.next;
  182.                 unlinkNode(x);
  183.                 x=next;
  184.             }else{
  185.                 x=x.next;
  186.             }
  187.         }
  188.     }
  189.  
  190.     /**
  191.      * 根据index与size的大小关系快速定位指定index位置的节点
  192.      * @param index
  193.      * @return
  194.      */
  195.     private DoubleNode node(int index) {
  196.         if(index < size >> 1) {
  197.             //从头向后
  198.             DoubleNode node = first;
  199.             for (int i = 0; i < index; i++) {
  200.                 node = node.next;
  201.             }
  202.             return node;
  203.         } else {
  204.             //从后向前
  205.             DoubleNode node = last;
  206.             for (int i = size-1; i > index; i--) {
  207.                 node = node.prev;
  208.             }
  209.             return node;
  210.         }
  211.     }
  212.  
  213.     /**
  214.      * 判断链表的index是否合法
  215.      * @param index
  216.      * @return
  217.      */
  218.     private boolean rangeCheck(int index) {
  219.         if(index < 0 || index >= size) {
  220.             return false;
  221.         }
  222.         return true;
  223.     }
  224.  
  225.     public String toString() {
  226.         String ret = "";
  227.         DoubleNode node = first;
  228.         while(node != null) {
  229.             ret += node.val + "->";
  230.             node = node.next;
  231.         }
  232.         ret += "NULL";
  233.         return ret;
  234.     }
  235.     
  236.     public static void main(String[] args) {
  237.         DoubleLinkedList doubleLinkedList=new DoubleLinkedList();
  238.         doubleLinkedList.addFirst(1);
  239.         doubleLinkedList.addFirst(2);
  240.         doubleLinkedList.addFirst(3);
  241.         doubleLinkedList.addLast(3);
  242.         doubleLinkedList.addLast(3);
  243.         doubleLinkedList.addLast(3);
  244.         //3->2->1->3->3->3->NULL
  245.         doubleLinkedList.addIndex(1,99);
  246.         //3->99->2->1->3->3->3->NULL
  247.         doubleLinkedList.removeValueOnce(99);
  248.         //3->2->1->3->3->3->NULL
  249.         doubleLinkedList.removeAllValue(3);
  250.         //2->1->NULL
  251.         System.out.println(doubleLinkedList);
  252.     }
  253. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/726226
推荐阅读
相关标签

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

  

闽ICP备14008679号