单链表

单链表 (Singly Linked List)

1. 单链表（Singly Linked List）

• 定义：每个节点包含数据和指向下一节点的引用，最后一个节点指向 null。

• 性质：

  • 插入 / 删除时间复杂度 (O(1))（需已知前驱节点）。
  • 查询时间复杂度 (O(n))，需从头遍历。
  • 不支持随机访问，空间利用率高（无预分配）。

• Java 实现：

  class Node {
      int data;
      Node next;
      
      Node(int data) {
          this.data = data;
          this.next = null;
      }
  }
  
  class SinglyLinkedList {
      private Node head;
      
      // 在链表头部插入
      public void insertAtBeginning(int data) {
          Node newNode = new Node(data);
          newNode.next = head;
          head = newNode;
      }
      
      // 删除指定值的节点
      public void delete(int key) {
          if (head == null) return;
          
          if (head.data == key) {
              head = head.next;
              return;
          }
          
          Node current = head;
          while (current.next != null && current.next.data != key) {
              current = current.next;
          }
          
          if (current.next != null) {
              current.next = current.next.next;
          }
      }
  }