Java实现双向循环链表

上一篇文章实现了单向循环链表，双向很简单，在单向循环链表的基础上加一个前驱指针，

节点类如下：

/**
 * 双向链表节点
 */
public class Node
{
    private int data;//数据域
    private Node pre;//指向上一个节点
    private Node next;//指向下一个节点

    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getPre() {
        return pre;
    }
    public void setPre(Node pre) {
        this.pre = pre;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }

    //构造函数
    public Node(int data, Node pre, Node next){
        this.data = data;
        this.pre = pre;
        this.next = next;
    }
    public Node(int data){
        this(data,null,null);
    }
    public Node(){
        this(0,null,null);
    }

}

具体实现：

  1 /**
  2  * Java实现双向循环链表
  3  * Author：hangwei
  4  * 2022/11
  5  */
  6 public class DLinkedList {
  7     private Node head;
  8     private Node tail;
  9     private int size;
 10     public Node getHead() {
 11         return head;
 12     }
 13     public Node getTail() {
 14         return tail;
 15     }
 16     public DLinkedList(){
 17         tail = head = null;
 18         size = 0;
 19     }
 20 
 21     /**
 22      * 在双向循环链表的任意位置之后新增一个节点
 23      * @param position 新增的位置，即新增节点的上一个节点
 24      * @param target 新增节点
 25      */
 26     public void addNode(Node position,Node target){
 27         if(target == null)
 28             return;
 29         if (size == 0) {
 30             target.setPre(target);
 31             target.setNext(target);
 32             tail = head = target;
 33         } else if (position == null) {//position为空就在链表尾部添加新节点
 34             tail.setNext(target);//尾节点的下一个节点是新节点
 35             target.setPre(tail);//新节点的上一个节点是尾节点
 36             target.setNext(head);//新节点的下一个节点是头节点
 37             //标记新的尾节点
 38             tail = target;
 39         } else {
 40             target.setPre(position);
 41             target.setNext(position.getNext());//原来position节点的下一个节点变成target的下一个节点
 42             position.setNext(target);
 43             if(size == 1 || position == tail)//标记新的尾节点
 44                 tail = target;
 45         }
 46         size++;
 47     }
 48 
 49     /**
 50      * 删除链表中的任意节点
 51      * @param target 即将被删除的节点
 52      */
 53     public void deleteNode(Node target){
 54         if(size == 0 || target == null){
 55             System.out.println("null linked list ,can not delete.");
 56             return;
 57         }
 58         else if(size == 1){
 59             head = tail = null;
 60         }
 61         else {
 62             if(target == head){//如果目标是头节点
 63                 head.getNext().setPre(tail);
 64                 tail.setNext(head.getNext());
 65                 head = head.getNext();
 66             }
 67             else {
 68                 //计算目标节点的上一个节点
 69 /*                Node n = new Node();//n表示target节点的上一个节点
 70                 n = head;
 71                 while (n.getNext() != tail) {//可以看到这里：当想要求解单向链表中的某个非头/尾节点时始终涉及到遍历
 72                     if (n.getNext() == target)
 73                         break;
 74                     n = n.getNext();
 75                 }*/
 76                 Node n = target.getPre();//双向循环链表这里不用计算上一个节点
 77                 target.getNext().setPre(n);
 78                 n.setNext(target.getNext());
 79                 if(target == tail)//如果目标是尾节点
 80                     tail = n;//标记新的尾节点
 81             }
 82         }
 83         size--;
 84     }
 85 
 86     //打印链表
 87     public void print(){
 88         Node node = new Node();
 89         node = head;
 90         while (node.getNext() != head && node.getNext() != null){//遍历
 91             System.out.print(node.getData());
 92             System.out.print("<->");
 93             node = node.getNext();
 94         }
 95         System.out.print(node.getData());//补充打印循环体的最后一个节点
 96         System.out.print("<->");
 97         //最后打印出头节点
 98         System.out.print(head.getData());
 99         System.out.println();
100     }
101 }

测试类：

public class Main {
    public static void main(String[] args) {
        //测试双向循环链表
        DLinkedList ll = new DLinkedList();
        ll.addNode(null,new Node(0));
        ll.print();
        ll.addNode(null,new Node(1));
        ll.addNode(null,new Node(2));
        ll.addNode(null,new Node(3));
        ll.print();
        ll.addNode(ll.getHead().getNext(),new Node(4));
        ll.print();
        ll.deleteNode(ll.getHead().getNext().getNext());
        ll.print();
        ll.deleteNode(ll.getHead());
        ll.print();
        ll.deleteNode(ll.getTail().getPre());
        ll.print();
    }
}

执行结果：

*重点：相比单向链表，双向链表的优点：不需要通过遍历(O(n))来查找某个节点的上一个节点。