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

【数据结构】Java实现双向链表

作者：喵喵爱编程 | 2024-08-11 22:08:27

赞

踩

java实现双向链表
LinkedList 的底层是双向链表结构 ，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

1. 接口的实现

（这个接口在前面的单链表，动态数组中也可以用到）

  1. public interface SeqList<E> {
  2.     //    尾插
  3.     void add(E element);
  4.     //    将 element 插入到 index 位置
  5.     void add(int index,E element);
  6.     //    删除 index 位置元素<返回删除的值
  7.     E removeByIndex(int index);
  8.     //    删除第一个值element的元素
  9.     void removeByValue(E element);
  10.     //    删除所有值element的元素
  11.     void removeAllValue(E element);
  12.     //    将下标 index 位置元素设置为 element，返回替换前的值
  13.     E set(int index,E element);
  14.     E get(int index);
  15.     //    判断 o 是否在其中
  16.     boolean contains(E element);
  17.     int indexOf(E element);
  18.     int size();
  19.     void clear();
  20. }

2. 动手实现双链表

2.1 重写SeqList接口方法

定义双向链表类，实现SeqList方法，重写同String方法。

（Alt + insert 快速实现方法重写）

  1. package seqlist.link;
  2.  
  3. import seqlist.SeqList;
  4.  
  5. public class DoubleLinkedList<E> implements SeqList<E> {
  6.     private DoubleNode head;//头节点
  7.     private DoubleNode tail;//尾节点
  8.  
  9.     private int size; // 车厢节点个数，保存的元素个数
  10.  
  11.     //车厢类的定义，车厢作为火车的内部类,对外部完全隐藏
  12.     private class DoubleNode {
  13.         E val;//保存的元素
  14.         DoubleNode prev;
  15.         DoubleNode next;
  16.         DoubleNode(E val) {
  17.             this.val = val;
  18.         }
  19.         public DoubleNode(E val, DoubleNode prev, DoubleNode next) {
  20.             this.val = val;
  21.             this.prev = prev;
  22.             this.next = next;
  23.         }
  24.     }
  25.     public void addFrist(E val){ }
  26.     @Override
  27.     public void add(E element) { }
  28.     @Override
  29.     public void add(int index, E element) { }
  30.     @Override
  31.     public E removeByIndex(int index) { }
  32.     @Override
  33.     public void removeByValue(E element) { }
  34.     @Override
  35.     public void removeAllValue(E element) { }
  36.     @Override
  37.     public E set(int index, E element) { }
  38.     public boolean rangeCheck(int index){ }
  39.     @Override
  40.     public E get(int index) { }
  41.     @Override
  42.     public boolean contains(E element) { }
  43.     @Override
  44.     public int indexOf(E element) { }
  45.     @Override
  46.     public int size() { }
  47.     @Override
  48.     public void clear() { }
  49.     @Override
  50.     public String toString() { }
  51. }

2.2 在当前链表尾部添加节点（尾插）

（1）size++

（2）如果链表为空，这个新插入的节点就是头节点

（3）链表不为空，将当前链表的尾节点的next指向新节点，新节点的前驱prev指向尾节点

（4）更新当新节点为尾节点

  1. public void add(E element) {
  2.         DoubleNode node = new DoubleNode(element);
  3.         size ++;
  4.         if (head == null){
  5.             head = node;
  6.         }else {
  7.             node.prev = tail;
  8.             tail.next = node;
  9.         }
  10.         tail = node;
  11.     }

2.3 在当前链表头部添加节点（头插）

这里头插不是重写方法！（因为前面的动态数组没又头插这一说法，所以这个方法就不放在接口里了）

（1）size++

（2）如果链表尾空，那么新节点就是头节点和尾节点

（3）链表不为空，将新节点的next指向head，head的前驱prev指向新节点

（4）更新新节点为头节点head

  1. public void addFirst(E element) {
  2.         DoubleNode node = new DoubleNode(element);
  3.         size ++;
  4.         if(head == null){
  5.             tail = node;
  6.         }else {
  7.             node.next = head;
  8.             head.prev = node;
  9.         }
  10.         head = node;
  11.     }

2.4 检验index是否合法

  1.  private boolean rangeCheck(int index) {
  2.         if (index < 0 ||index >= size) {
  3.             return false;
  4.         }
  5.         return true;
  6.     }

2.5 在 第index位置添加节点（任意位置）

（1）判断index是否合法，不合法退出
（2）判断是不是头插或者尾插，调用相应的方法添加后退出
（3）调用node方法index位置节点的找到前驱prev，将prev.next作为后继节点node方法判断index是比较靠近head就从前往后遍历，比较靠近tail就从后往前遍历，使代码效率更高
（4）节点链接，先连左边区域，再连右边区域
（5）size++ 
DoubleNode node = new DoubleNode(element,prev,next);
看前面的构造函数，这时候已经将node.prev = prev，node.next = next 
  1.     public void add(int index, E element) {
  2.         if (index < 0 || index > size){
  3.             throw new IllegalArgumentException("add index illegal");
  4.         }
  5.         if(head == null){
  6.             addFirst(element);
  7.             return;
  8.         }
  9.         if(index == size){
  10.             add(element);
  11.             return;
  12.         }
  13.  
  14.         DoubleNode prev = node(index - 1);
  15.         DoubleNode next = prev.next;
  16.         DoubleNode node = new DoubleNode(element,prev,next);
  17.         // 先处理左边区域
  18.         prev.next = node;
  19.         // 再处理右半区域
  20.         next.prev = node;
  21.         size ++;
  22.     }
  23.     // 根据传入索引与中间位置的关系，决定到底从前向后寻找节点还是从后向前寻找节点
  24.     // 内部使用的工具方法
  25.     private DoubleNode node(int index){
  26.         if (index < (size>>1)){
  27.             DoubleNode ret = head;
  28.             for (int i = 0; i < index; i++) {
  29.                 ret = ret.next;
  30.             }
  31.             return ret;
  32.         }else {
  33.             DoubleNode ret = tail;
  34.             for (int i = size -1; i > index; i--) {
  35.                 ret = ret.prev;
  36.             }
  37.             return ret;
  38.         }
  39.     }

2.6  删除第index个节点

（1）判断index是否合法，不合法退出

（2）调用node方法找到待删除节点

（3）调用unlink(node)方法进行删除，将node的前驱prev和后继next连接，将node的prev和next置空null，再size--。（前驱prev为空时，node是头节点，将新的头节点设为node的下一个节点next；后继next为空时node为尾节点，将node的前驱prev设尾节点）

（4）返回被删除节点的值

  1. public E removeByIndex(int index) {
  2.         if (!rangeCheck(index)){
  3.             throw new IllegalArgumentException("removeByIndex index illegal");
  4.         }
  5.         DoubleNode node = node(index);
  6.         unlink(node);
  7.         return node.val;
  8.     }
  9.     private void unlink(DoubleNode node){
  10.         DoubleNode prev =node.prev;
  11.         DoubleNode next = node.next;
  12.         // 先处理左半区域
  13.         if(prev == null){
  14.             this.head = next;
  15.         }else {
  16.             node.next = null;
  17.             prev.next = next;
  18.         }
  19.         // 在处理右半区域
  20.         if(next == null){
  21.             this.tail = prev;
  22.         }else {
  23.             node.next = null;
  24.             next.prev = prev;
  25.         }
  26.         size--;
  27.     }

2.7 删除第一个值element的节点

遍历链表，在链表中找到与element值相等的节点，调用unlink(node)方法进行删除
这里的图和2.6 中的图一致 
  1.     public void removeByValue(E element) {
  2.         DoubleNode node = head;
  3.         for (int i = 0; i < size; i++) {
  4.             if (node.val.equals(element)){
  5.                 unlink(node);
  6.                 return;
  7.             }
  8.             node = node.next;
  9.         }
  10.     }

2.8 删除所有值element的节点

（1）遍历链表，在链表中找到与element值相等的节点，调用unlink(node)方法进行删除

（2）链表有多长就要遍历几次，以防有的节点没有被遍历（此时，每当进行一次删除，size就会减一，直接用size遍历可能导致某些节点漏掉了，因此用length保存初始的size值）

  1. public void removeAllValue(E element) {
  2.         DoubleNode node = head;
  3.         // 因为每次unlink之后都会修改size的值，但是删除所有元素，
  4.         // 要把所有链表节点全部遍历一遍
  5.         int length = this.size;
  6.         for (int i = 0; i < length; i++) {
  7.             DoubleNode next = node.next;
  8.             if (node.val.equals(element)) {
  9.                 unlink(node);
  10.             }
  11.             node = next;
  12.         }
  13.     }

2.9 修改第index个节点的值为element

（1）判断index是否合法，不合法退出

（2）调用node方法找到该节点

（3）保存原来节点的值

（4）修改该节点的值

（5）返回原来节点的值

  1.     public E set(int index, E element) {
  2.         if(!rangeCheck(index)){
  3.             throw new IllegalArgumentException("set index illeagal");
  4.         }
  5.         DoubleNode node = node(index);
  6.         E oldVal = node.val;
  7.         node.val = element;
  8.         return oldVal;
  9.     }

2.10 获取第index个节点的值

（1）判断index是否合法，不合法退出

（2）调用node方法找到该节点并返回

  1. public E get(int index) {
  2.         if (!rangeCheck(index)) {
  3.             throw new IllegalArgumentException("get index illegal!");
  4.         }
  5.         return node(index).val;
  6.     }

2.11 判断链表中是否存在element

  1. public boolean contains(E element) {
  2.         DoubleNode node = head;
  3.         while (node.next != null){
  4.             if (node.val.equals(element)){
  5.                 return true;
  6.             }
  7.             node = node.next;
  8.         }
  9.         return false;
  10.     }

2.12  获取element在链表中的位置

  1. public int indexOf(E element) {
  2.         DoubleNode node = head;
  3.         int i = 0;
  4.         while (node.next != null){
  5.             if (node.val.equals(element)){
  6.                 return i;
  7.             }
  8.             i ++;
  9.             node = node.next;
  10.         }
  11.         return -1;
  12.     }

2.13 打印链表

  1. public String toString() {
  2.         StringBuilder sb = new StringBuilder();
  3.         for(DoubleNode x = head; x != null; x = x.next){
  4.             sb.append(x.val);
  5.             sb.append("->");
  6.             if(x.next == null){
  7.                 // 此时temp走到了尾结点
  8.                 sb.append("NULL");
  9.             }
  10.         }
  11.         return sb.toString();
  12.     }

2.14  获取链表长度以及清空链表

  1.     public int size() {
  2.         return size;
  3.     }
  4.  
  5.     @Override
  6.     public void clear() {
  7.         while (head.next != null){
  8.             DoubleNode node = head.next;
  9.             head.next =null;
  10.             head.prev = null;
  11.             head = node;
  12.         }
  13.         head = null;
  14.         size = 0;
  15.     }

3. DoubleLinkedList整体实现

3.1 DoubleLinkedList类

  1. public class DoubleLinkedList<E> implements SeqList<E> {
  2.     private DoubleNode head;//头节点
  3.     private DoubleNode tail;//尾节点
  4.  
  5.     private int size; // 车厢节点个数，保存的元素个数
  6.  
  7.     //车厢类的定义，车厢作为火车的内部类,对外部完全隐藏
  8.     private class DoubleNode {
  9.         E val;//保存的元素
  10.  
  11.         DoubleNode prev;
  12.         DoubleNode next;
  13.         DoubleNode(E val) {
  14.             this.val = val;
  15.         }
  16.  
  17.         public DoubleNode(E val, DoubleNode prev, DoubleNode next) {
  18.             this.val = val;
  19.             this.prev = prev;
  20.             this.next = next;
  21.         }
  22.     }
  23.  
  24. //    w尾插
  25.     @Override
  26.     public void add(E element) {
  27.         DoubleNode node = new DoubleNode(element);
  28.         size ++;
  29.         if (head == null){
  30.             head = node;
  31.         }else {
  32.             node.prev = tail;
  33.             tail.next = node;
  34.         }
  35.         tail = node;
  36.     }
  37.     public void addFirst(E element) {
  38.         DoubleNode node = new DoubleNode(element);
  39.         size ++;
  40.         if(head == null){
  41.             tail = node;
  42.         }else {
  43.             node.next = head;
  44.             head.prev = node;
  45.         }
  46.         head = node;
  47.     }
  48.  
  49.     @Override
  50.     public void add(int index, E element) {
  51.         if (index < 0 || index > size){
  52.             throw new IllegalArgumentException("add index illegal");
  53.         }
  54.         if(head == null){
  55.             addFirst(element);
  56.             return;
  57.         }
  58.         if(index == size){
  59.             add(element);
  60.             return;
  61.         }
  62.  
  63.         DoubleNode prev = node(index - 1);
  64.         DoubleNode next = prev.next;
  65.         DoubleNode node = new DoubleNode(element,prev,next);
  66.         // 先处理左边区域
  67.         prev.next = node;
  68.         // 再处理右半区域
  69.         next.prev = node;
  70.         size ++;
  71.     }
  72.     // 根据传入索引与中间位置的关系，决定到底从前向后寻找节点还是从后向前寻找节点
  73.     // 内部使用的工具方法
  74.     private DoubleNode node(int index){
  75.         if (index < (size>>1)){
  76.             DoubleNode ret = head;
  77.             for (int i = 0; i < index; i++) {
  78.                 ret = ret.next;
  79.             }
  80.             return ret;
  81.         }else {
  82.             DoubleNode ret = tail;
  83.             for (int i = size -1; i > index; i--) {
  84.                 ret = ret.prev;
  85.             }
  86.             return ret;
  87.         }
  88.     }
  89.  
  90.  
  91.     @Override
  92.     public E removeByIndex(int index) {
  93.         if (!rangeCheck(index)){
  94.             throw new IllegalArgumentException("removeByIndex index illegal");
  95.         }
  96.         DoubleNode node = node(index);
  97.         unlink(node);
  98.         return node.val;
  99.     }
  100.  
  101.     @Override
  102.     public void removeByValue(E element) {
  103.         DoubleNode node = head;
  104.         for (int i = 0; i < size; i++) {
  105.             if (node.val.equals(element)){
  106.                 unlink(node);
  107.                 return;
  108.             }
  109.             node = node.next;
  110.         }
  111.     }
  112.  
  113.     @Override
  114.     public void removeAllValue(E element) {
  115.         DoubleNode node = head;
  116.         // 因为每次unlink之后都会修改size的值，但是删除所有元素，
  117.         // 要把所有链表节点全部遍历一遍
  118.         int length = this.size;
  119.         for (int i = 0; i < length; i++) {
  120.             DoubleNode next = node.next;
  121.             if (node.val.equals(element)) {
  122.                 unlink(node);
  123.             }
  124.             node = next;
  125.         }
  126.     }
  127.  
  128.     private void unlink(DoubleNode node){
  129.         DoubleNode prev =node.prev;
  130.         DoubleNode next = node.next;
  131.         // 先处理左半区域
  132.         if(prev == null){
  133.             this.head = next;
  134.         }else {
  135.             node.next = null;
  136.             prev.next = next;
  137.         }
  138.         // 在处理右半区域
  139.         if(next == null){
  140.             this.tail = prev;
  141.         }else {
  142.             node.next = null;
  143.             next.prev = prev;
  144.         }
  145.         size--;
  146.     }
  147.  
  148.     private boolean rangeCheck(int index) {
  149.         if (index < 0 ||index >= size) {
  150.             return false;
  151.         }
  152.         return true;
  153.     }
  154.  
  155.     @Override
  156.     public E set(int index, E element) {
  157.         if(!rangeCheck(index)){
  158.             throw new IllegalArgumentException("set index illeagal");
  159.         }
  160.         DoubleNode node = node(index);
  161.         E oldVal = node.val;
  162.         node.val = element;
  163.         return oldVal;
  164.     }
  165.  
  166.     @Override
  167.     public E get(int index) {
  168.         if (!rangeCheck(index)) {
  169.             throw new IllegalArgumentException("get index illegal!");
  170.         }
  171.         return node(index).val;
  172.     }
  173.  
  174.     @Override
  175.     public boolean contains(E element) {
  176.         DoubleNode node = head;
  177.         while (node.next != null){
  178.             if (node.val.equals(element)){
  179.                 return true;
  180.             }
  181.             node = node.next;
  182.         }
  183.         return false;
  184.     }
  185.  
  186.     @Override
  187.     public int indexOf(E element) {
  188.         DoubleNode node = head;
  189.         int i = 0;
  190.         while (node.next != null){
  191.             if (node.val.equals(element)){
  192.                 return i;
  193.             }
  194.             i ++;
  195.             node = node.next;
  196.         }
  197.         return -1;
  198.     }
  199.  
  200.     @Override
  201.     public int size() {
  202.         return size;
  203.     }
  204.  
  205.     @Override
  206.     public void clear() {
  207.         while (head.next != null){
  208.             DoubleNode node = head.next;
  209.             head.next =null;
  210.             head.prev = null;
  211.             head = node;
  212.         }
  213.         head = null;
  214.         size = 0;
  215.     }
  216.  
  217.     @Override
  218.     public String toString() {
  219.         StringBuilder sb = new StringBuilder();
  220.         for(DoubleNode x = head; x != null; x = x.next){
  221.             sb.append(x.val);
  222.             sb.append("->");
  223.             if(x.next == null){
  224.                 // 此时temp走到了尾结点
  225.                 sb.append("NULL");
  226.             }
  227.         }
  228.         return sb.toString();
  229.     }
  230. }

3.2 Test类

  1. public class DoubleNodeTest {
  2.     public static void main(String[] args) {
  3.         DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
  4.         list.add(1);
  5.         list.add(3);
  6.         list.add(5);
  7.         list.add(9);
  8.         list.add(3);
  9.         list.add(3);
  10.         System.out.println(list);
  11.         System.out.println("清空链表");
  12.         list.clear();
  13.         System.out.println(list);
  14.         list.add(6);
  15.         list.add(10);
  16.         list.add(5);
  17.         list.add(7);
  18.         list.add(10);
  19.         list.add(10);
  20.  
  21.         System.out.println(list);
  22.         System.out.println("------------添加测试-----------");
  23.         System.out.println("从链表尾部添加99,头部添加99999");
  24.         list.add(99);
  25.         list.addFirst(99999);
  26.         System.out.println(list.size());
  27.         System.out.println("添加index为2，element为88");
  28.         list.add(2,88);
  29.         System.out.println(list);
  30.         System.out.println(list.size());
  31.         System.out.println("-----------删除测试------------");
  32.         System.out.println("删除index为0");
  33.         list.removeByIndex(0);
  34.         System.out.println("删除元素为6");
  35.         list.removeByValue(6);
  36.         System.out.println("删除所有10");
  37.         list.removeAllValue(10);
  38.         System.out.println(list);
  39.         System.out.println("-----------其他------------");
  40.         System.out.println("查看是否包含10这个元素");
  41.         System.out.println(list.contains(10));
  42.         System.out.println("修改index为3，element为19");
  43.         list.set(3,19);
  44.         System.out.println("获取index为3的元素");
  45.         System.out.println(list.get(3));
  46.         System.out.println(list);
  47.         System.out.println("获取element为88的index");
  48.         System.out.println(list.indexOf(88));
  49.         System.out.println("获取链表长度");
  50.         System.out.println(list.size());
  51.         System.out.println("清空链表");
  52.         list.clear();
  53.         System.out.println(list + "...");
  54.     }
  55. }

3.3 测试结果

趁热打铁：

【leetcode】链表（1）

【leetcode】链表（2）

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

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

  

闽ICP备14008679号