双链表

双链表 (Doubly Linked List)

2. 双链表（Doubly Linked List）

• 定义：每个节点包含数据、指向前驱节点的引用 prev 和指向后继节点的引用 next。

• 性质：

  • 支持双向遍历，可快速访问前驱节点。
  • 插入 / 删除时间复杂度 (O(1))（需已知节点）。
  • 空间开销更大（每个节点多一个引用）。

• Java 实现：

  class DNode {
      int data;
      DNode prev, next;
      
      DNode(int data) {
          this.data = data;
          this.prev = null;
          this.next = null;
      }
  }
  
  class DoublyLinkedList {
      private DNode head;
      
      // 在头部插入
      public void insertAtBeginning(int data) {
          DNode newNode = new DNode(data);
          newNode.next = head;
          
          if (head != null) {
              head.prev = newNode;
          }
          
          head = newNode;
      }
      
      // 删除指定节点
      public void delete(DNode node) {
          if (node.prev != null) {
              node.prev.next = node.next;
          } else {
              head = node.next;
          }
          
          if (node.next != null) {
              node.next.prev = node.prev;
          }
      }
  }