Java实现双向链表

本文实例为大家分享了Java实现双向链表的具体代码，供大家参考，具体内容如下

1、双向链表

1.1 双向链表的每个节点组成包含节点数据，上一个节点（pre），下一个节点（next）

1.2 双向链表节点结构

class Node {
//节点数据data
  int data;
  Node pre;
  Node next;

  public Node(int data) {
   this.data = data;
  }
  public Node() {
   super();
  }
  

 }

2、双向链表的增删改查（crud）

2.1 双向链表的增删改查

public class DoubleLinkedList {
 private Node first;
 private Node current;

 private static class Node {

  int data;
  Node pre;
  Node next;

  public Node(int data) {
   super();
   this.data = data;
  }

  public Node() {
   super();
  }
  

 }

 public DoubleLinkedList() {
  super();
 }

 /**
  * 双向链表增加
  */
 public void add(int val) {
  // 如果是头结点
  if (first == null) {
   Node node = new Node(val);
   first = node;
   first.pre = null;
   first.next = null;
   current = first;
  } else {
   Node node = new Node(val);
   current.next = node;
   node.pre = current;
   current = node;
  }
 }

 /**
  * 双向链表的删除 删除所有值为val的元素
  */
 public void del(int val) {
  if (first == null) {
   System.out.println("双向链表为空，无法进行删除操作！");
  } else {
   
   Node node = first;
   while(true) {
    // 首节点的删除可能
    if (node.data == val) {
     //如果只有一个节点
     if(node.next==null) {
      node=null;
      first=null;
      System.out.println("删除所有的"+val+"成功");
      return;
     }else {
      node = node.next;
      node.pre.next=null;
      node.pre=null;
      first=node;
      //删除后重新循环判断首节点是否值相等
      continue;
     }
    
     
    } else {
     
     while (node.next != null) {
      if (node.data == val) {
       node.pre.next = node.next;
       node.next.pre = node.pre;
       Node tempNode = node.pre;
       node.pre=null;
       node.next=null;
       node = tempNode;
      }
      node = node.next;
     }
     // 末节点删除可能
     if (node.data == val) {
      node.pre.next=null;
      node.pre=null;

     }
     System.out.println("删除所有的"+val+"成功");
     //末节点判断完成后，结束循环
     return;
    }
   }
  }

 }
 /**
  * 遍历双向链表操作
  */
 public void traverse() {
  if(first==null) {
   System.out.println("双向链表为空");
  }else {
   Node node = first;
   //循环遍历到倒数第二个节点截止
   while(node.next!=null) {
    System.out.print(node.data+" ");
    node=node.next;
   }
   //遍历最后一个节点
   System.out.print(node.data);
  }
 }
 /**
  * 双向链表插入操作,在所有值为value的后面插入一个数insert
  */
 public void insert(int value,int insert) {
  
  if(first==null) {
   System.out.println("双向链表为空，无法插入");
  }else {
   Node node = first;
   //循环遍历到倒数第二个节点截止
   while(node.next!=null) {
    if(node.data==value) {
     Node insertNode = new Node(insert);
     node.next.pre = insertNode;
     insertNode.next = node.next;
     node.next = insertNode;
     insertNode.pre = node;
    }
    node=node.next;
   }
   //最后一个节点后插入
   if(node.data == value) {
    Node insertNode = new Node(insert);
    node.next = insertNode;
    insertNode.pre = node;
   }
   System.out.println();
   System.out.println("插入操作完成");
   
  }
 }
 /**
  * 双向链表修改数据,将所有值为val的修改为revised
  */
 public void revise(int val,int revised) {
  if(first==null) {
   System.out.println("双向链表为空，无法修改");
  }else {
   Node node = first;
   while (node.next!=null) {
    if(node.data == val) {
     node.data = revised;
    }
    node=node.next;
   }
   if(node.data == val) {}
   node.data = revised;
  }
  System.out.println("修改操作完成");
 }
 /**
  * 查找双向链表中是否包含val值
  * @param val
  */
 public void contain(int val) {
  if(first==null) {
   System.out.println("链表为空，无法查找");
  }else {
   Node node = first;
   while(node!=null) {
    if(node.data==val) {
     System.out.println("该链表中包含"+val+"的值");
     return;
    }else {
     node=node.next;
    }
   }
   System.out.println("该链表不包含"+val);
  }
 }

}

2.2 测试类（main入口函数）

public class Main {
 public static void main(String[] args) {
  DoubleLinkedList list = new DoubleLinkedList();

  list.add(1);
  list.add(1);
  list.add(2);
  list.insert(1, 3);
  list.add(2);
  list.add(3);
  list.traverse();
  System.out.println();
  list.del(1);
 
  list.traverse();
  list.add(4);
  System.out.println();
  list.traverse();
  System.out.println();
  list.contain(4);
  
  list.contain(3);
  list.contain(0);

 }
}

3、一些缺点待修改

1）、循环结束是到倒数第二个节点截止的，要考虑多种不同的情况，头节点删除，尾结点删除等，导致删除函数复杂了很多
2）、在contain函数中有修改到循环到最后一个节点
3）、后续对删除函数修改有空再操作（待完成）

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持源码搜藏网。