【資料結構】線性表之單向連結清單

• 并發程式設計模型 燕歸來兮 https://www.zhoutao123.com/page/book/11
• 資料結構與算法 燕歸來兮 https://www.zhoutao123.com/page/book/13

連結清單通常指的是單向連結清單，他包含多個節點，每個節點都有一個紙箱下一個幾點的next指針。表中最後一個節點指向NULL，表示連結清單的結束。

下面是一個基于Java 聲明的連結清單節點

public class Node<T extends Serializable> {
  // 節點資料
  private  T data;

  // 指向的Next 節點
  private Node<T> next;
}
           

• 周遊連結清單
• 在連結清單中插入一個元素
• 在連結清單中删除一個元素

1.1 連結清單的周遊

假設表頭節點是指向連結清單的第一個節點，完成連結清單的周遊隻需要執行以下步驟。

1. 沿指針周遊
2. 顯示目前指針所指向的内容
3. 将目前節點指向 Next 節點
4. 當 Next 節點指向NULL的時候周遊結束

public static <T extends Serializable> void linkedListForeach(Node<T> headNode) {
    Node<T> currentNode = headNode;
    // 4. 周遊終止條件，Next指向NULL
    while (currentNode != null) {
      // 2.輸出目前節點的資料
      System.out.println(currentNode.getData() + "->");
      // 3. 将目前節點指向Next 節點
      currentNode = currentNode.getNext();
    }
  }
           

根據同樣的邏輯，也可以根據此實作連結清單長度的計算。

private static <T extends Serializable> int length(Node<T> headNode) {
    Node<T> currentNode = headNode;
    int count = 0;
    while (currentNode != null) {
      count++;
      currentNode = currentNode.getNext();
    }
    return count;
  }
           

1.2 連結清單插入元素

連結清單中插入元素分為三種，分别是在連結清單頭部插入元素，在連結清單中間插入元素以及在連結清單尾部插入元素。需要注意的這裡的連結清單的位置指的在p位置插入元素，在插入完成之後，連結清單的p位置指向的是新的節點。

1.2.1 在連結清單的頭部插入新的節點

其邏輯步驟是：

• 首先将新的節點的指針指向表頭節點
• 将表頭節點指向新的節點

1.2.2 在連結清單尾部插入節點

在連結清單尾部插入新的節點也非常簡單，需要将新的節點的NEXT 指針指向NULL，然後将原連結清單的尾指針執行新節點，即可。

1.2.3 在連結清單中間插入節點

• 首先定位到需要插入的節點位置，斷開其 Next 節點，注意需要儲存 Next 節點的引用
• 将目前節點的 Next 指針執行新的節點
• 将新節點的 Next 指針指向 Next 節點

1.2.4 源碼示例

// 時間複雜度 O(n) 空間複雜度 O(1)
  private static <T extends Serializable> Node<T> insert(
      Node<T> headNode, Node<T> insertNode, int position) {
    
    // 判斷長度，插入的位置是否合法
    int length = length(headNode);
    if (position <= 0 || position > length) {
      throw new IllegalArgumentException();
    }
    

    // 如果是連結清單頭部，直接指向Next節點
    if (position == 1) {
      insertNode.setNext(headNode);
      return insertNode;
    }

    // 如果不是頭部，那麼擷取到目前插入位置的節點
    Node<T> currentNode = findByPosition(headNode, position - 1);
    if (currentNode == null) {
      return headNode;
    }

    // 儲存目前插入位置節點的Next引用
    Node<T> next = currentNode.getNext();
    // 目前節點的Next 指向新的節點
    currentNode.setNext(insertNode);
    // 新的節點的Next 指向Next節點
    insertNode.setNext(next);

    return headNode;
  }
           

1.3 連結清單删除元素

同插入類似，連結清單删除也分為三種情況，分别是在删除連結清單頭部元素，删除連結清單中間元素以及在删除連結清單尾部元素。

1.3.1 删除連結清單頭部節點

删除頭部節點元素非常簡單，隻需要将原頭部節點的NEXT指向NULL，然後将表頭指針指向原頭結點的Next節點即可。

1.3.2 删除連結清單尾部節點

删除尾部節點也非常簡單，隻要将尾部節點的前驅的Next節點設定為NULL，即可

1.3.3 删除連結清單中間的節點

删除連結清單的中間節點的步驟是：

• 定位目前節點為需要删除節點的前驅位置，目前節點的後驅就是即将删除的節點
• 将删除節點的Next 指向NULL
• 将目前節點的Next指針執行将要删除的節點的Next節點。

1.3.4 代碼示例

// 時間複雜度 O(n) 空間複雜度 O(1) 
 private static <T extends Serializable> Node<T> remove(Node<T> headNode, int position) {
    int length = length(headNode);
    if (position <= 0 || position > length) {
      throw new IllegalArgumentException();
    }
    // 如果是删除頭部節點，直接傳回頭部節點的Next
    if (position == 1) {
      headNode.setNext(null);
      return headNode.getNext();
    }

    // 定位到删除節點的前驅節點，以及即将删除的節點
    Node<T> preNode = findByPosition(headNode, position - 1);
    Node<T> currentNode = findByPosition(headNode, position);

    // 如果前驅節點存在，則将前驅節點的Next設定為删除節點的Next
    if (preNode != null) {
      Node<T> next = Objects.isNull(currentNode) ? null : currentNode.getNext();
      preNode.setNext(next);
    }
    return headNode;
  }