双向循环链表

双向循环链表 (CircularDoubly Linked List)

4. 双向循环链表（Circular Doubly Linked List）

• 定义：双链表的变种，头节点的 prev 指向尾节点，尾节点的 next 指向头节点。

• 性质：

  • 同时支持双向遍历和循环访问。
  • 实现复杂，但操作灵活（如删除任意节点只需 (O(1))）。

• Java 实现：

  class CDNode {
      int data;
      CDNode prev, next;
      
      CDNode(int data) {
          this.data = data;
          this.prev = null;
          this.next = null;
      }
  }
  
  class CircularDoublyLinkedList {
      private CDNode head;
      
      // 在头部插入
      public void insertAtBeginning(int data) {
          CDNode newNode = new CDNode(data);
          
          if (head == null) {
              newNode.next = newNode;
              newNode.prev = newNode;
              head = newNode;
              return;
          }
          
          CDNode last = head.prev;
          
          newNode.next = head;
          head.prev = newNode;
          newNode.prev = last;
          last.next = newNode;
          
          head = newNode;
      }
  }