持久且不可變的 Java LinkedList

在本文中，我們將使用 Java 實作 LinkedList 的持久且不可變的變體
部分結構共享可提高時間和空間效率。

介紹

什麼是鍊錶

鍊錶是一種由節點集合組成的資料結構，其中每個節點都包含一個值和對序列中下一個節點的引用。在清單頭部新增元素或從頭部刪除元素等操作都是 O(1) 操作。但是，在列表末尾添加元素或從末尾刪除元素等操作是 O(n) 操作，其中 n 是列表中元素的數量。

為什麼我們需要一個不可變的 LinkedList

在函數式程式設計中，不變性是一個關鍵概念。不變性意味著一旦創建了資料結構，它
無法修改。相反，透過修改創建一個新的資料結構，原始資料結構保持不變。

此屬性為我們帶來了多項好處：

1. 執行緒安全性：由於資料結構是不可變的，因此可以在多個執行緒之間共用，無需同步。
2. 可預測性：由於資料結構是不可變的，我們可以推斷資料結構在任何時間點的狀態。
3. 撤銷：由於資料結構是不可變的，我們總是可以透過使用先前版本的資料結構來恢復到先前的狀態。
4. 調試：不變性使偵錯更容易，因為資料結構無法修改。

但是，Java 中的集合預設是可變的，並且由於本文的重點是 LinkedList。原因可能有很多
從設計集合時不被考慮到
中固有的性能原因 不可變的資料結構。

不可修改的 JDK 集合和此 LinkedList 之間的區別

JDK 提供了不可修改的集合，它們是原始集合的包裝器。它們支援不變性，但它們不是持久性的，也沒有提供真正的類型安全方式。它們是原始系列的包裝，並且它們
呼叫修改操作時拋出異常。這與不變性不同，不變性中資料結構根本無法修改，同時確保在執行時很難獲得 UnsupportedOperationException。

持久與不可變

雖然持久性和不可變這兩個術語經常互換使用，但它們具有不同的含義。不變性不允許修改資料結構，而持久性允許在修改資料結構時共用資料結構。這意味著當修改資料結構（即建立新版本）時，舊資料結構的部分內容可以與新資料結構共享，從而實現時間和空間效率的提高。這種技術稱為結構共享。

有多種方法可以實現資料結構的持久化。資料結構範圍從簡單到複雜，例如使用平衡樹（如 AVL 或紅黑樹），到更複雜的樹（如手指樹和基於基數的平衡樹）。

在本文中，我們將實作一個具有部分結構共享的持久且不可變的 LinkedList 的簡單版本。原因是 LinkedList 是一種簡單的資料結構，它將幫助我們更好地理解不變性和持久性的概念，而通常更複雜的資料結構的實作本質上是一項具有挑戰性的任務。

執行

下面我們將一步步用 Java 實作一個持久且不可變的單鍊錶。

要獲得完整的實作以及額外的 monad 和實用程式來幫助您進行 Java 函數式程式設計之旅，您可以查看這個很棒的小型程式庫 FunctionUtils。

我們為 LinkedList 指定的名稱將是 SeqList，它將是一個泛型類別。

首先，我們需要考慮我們要在清單中支援的操作。

1. 加入到清單的頭部，這將是一個 O(1) 操作。
2. 從清單中刪除一個元素，如果該元素位於末尾，則最壞的情況是 O(n) 操作。
3. 加入到清單中的任意位置。
4. 過濾操作，用於過濾給定謂詞的元素。
5. Map 和 FlatMap 操作將我們的 List 轉換為 Monad，以便更輕鬆地進行函數組合。

我們可以將 LinkedList 視為由節點組成的結構，其中每個節點包含：

1. head 持有一個值。
2. tail 儲存清單的其餘部分，而清單又是一個由 head 和 tail 組成的 LinkedList，直到清單結尾。
3. 列表的末尾由一個空的 LinkedList 表示，這意味著頭和尾都為空。

完整的實作可以在這裡找到

鑑於清單的最後一個元素是一個空的 LinkedList，並且每個元素都是一個有頭和尾的節點，我們可以將 LinkedList 表示為由兩個類別組成的遞歸資料結構：

public record Empty<T>() implements SeqList<T> {
}

public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
}

其中 Cons 是一個名為 Construct 的函數式程式設計術語，其歷史可以追溯到 Lisp 程式語言。

有鑑於上述情況，我們可以實作 SeqList 接口，如下所示：

public sealed interface SeqList<T> permits Empty, Cons {
  /**
   * Creates an empty list.
   *
   * @param <T> the type of the elements
   * @return an empty list
   */
  static <T> SeqList<T> empty() {
    return new Empty<>();
  }

  /**
   * Creates a new list with the given elements. The complexity of this method is O(n) where n is
   * the number of elements.
   *
   * @param elements the elements to add
   * @param <T>      the type of the elements
   * @return a new list with the elements added
   */
  @SafeVarargs
  static <T> SeqList<T> of(T... elements) {
    SeqList<T> list = empty();
    for (int i = elements.length - 1; i >= 0; i--) {
      list = list.add(elements[i]);
    }
    return list;
  }

  /**
   * Prepends the element to the list. The complexity of this method is O(1).
   *
   * @param element the element to add
   * @return a new list with the element prepended
   */
  default SeqList<T> add(T element) {
    return new Cons<>(element, this);
  }
}

讓我們分解一下上面寫的內容：

1. 我們建立了一個密封介面 SeqList，它將成為我們的 LinkedList 的介面。
2. empty() 方法建立一個空列表，它是 Empty 類別的實例。
3. add() 方法將一個元素加入到清單中。此方法的複雜度為 O(1)，因為我們只是使用給定元素和當前清單來建立一個新節點。此方法使用結構共用，因為新清單共用目前清單的尾部。
4. of() 方法使用給定元素建立一個新清單。此方法的複雜度為 O(n)，其中 n 是元素的數量。很明顯，我們從最後一個元素開始並將其添加到列表中。這是因為我們想要保留元素的順序。

我們需要實作剩餘的操作。讓我們從刪除操作開始：

/**
   * Removes the first occurrence of the element from the list. If the element is not found, the
   * list is returned as is. The complexity of this method is O(n) where n is the number of
   * elements. It uses structural sharing up to the element to remove. If the element is not found
   * the structural sharing is not utilized.
   *
   * @param element the element to remove
   * @return a new list with the element removed
   * @throws StackOverflowError for infinite lists
   */
  default SeqList<T> remove(T element) {
    if (isEmpty()) {
      return this;
    }
    if (head().equals(element)) {
      return tail();
    }
    return new Cons<>(head(), tail().remove(element));
  }

另外在我們的子類別中實作 tail() 方法和其他一些有用的方法：

public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {

  @Override
  public boolean isEmpty() {
    return false;
  }

  @Override
  public Optional<T> headOption() {
    return Optional.ofNullable(head);
  }

  @Override
  public Optional<T> last() {
    if (tail.isEmpty()) {
      return Optional.ofNullable(head);
    }
    return tail.last();
  }
}

public record Empty<T>() implements SeqList<T> {

  @Override
  public boolean isEmpty() {
    return true;
  }

  @Override
  public T head() {
    throw new UnsupportedOperationException("head() called on empty list");
  }

  @Override
  public Optional<T> headOption() {
    return Optional.empty();
  }

  @Override
  public SeqList<T> tail() {
    throw new UnsupportedOperationException("tail() called on empty list");
  }

  @Override
  public Optional<T> last() {
    return Optional.empty();
  }
}

正如我們可以從remove方法的實作中檢查的那樣，我們正在使用遞歸呼叫來從
中刪除元素 名單。這是函數式程式設計中的典型模式，我們使用遞歸來遍歷列表並
刪除該元素。應注意避免在無限列表的情況下堆疊溢位。未來的改進可能是使用 Java 不支援的尾遞歸優化，但可以使用彈翻床來實現。

最後，讓我們實作map和flatMap運算，將我們的List變成Monad：

/**
   * Applies a map function to the elements of the list. The complexity of this method is O(n) where
   * n is the number of elements.
   * <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the map function
   * @param <U> the type of the elements of the new list
   * @return a new list with the elements mapped
   * @throws StackOverflowError for infinite lists
   */
  default <U> SeqList<U> map(Function<? super T, ? extends U> fn) {
    if (isEmpty()) {
      return empty();
    }
    return new Cons<>(fn.apply(head()), tail().map(fn));
  }

  /**
   * Applies a flat map function to the elements of the list. The complexity of this method is O(n)
   * where n is the number of elements.
   * <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the flat map function
   * @param <U> the type of the elements of the new list
   * @return a new list with the elements flat mapped
   * @throws StackOverflowError for infinite lists
   */
  default <U> SeqList<U> flatMap(Function<? super T, ? extends SeqList<U>> fn) {
    if (isEmpty()) {
      return empty();
    }
    SeqList<U> mappedHead = fn.apply(head());
    SeqList<U> newTail = tail().flatMap(fn);
    return concat(mappedHead, newTail);
  }

  /**
   * Concatenates two lists. The complexity of this method is O(n) where n is the number of
   * elements.
   *
   * @param list1 the first list
   * @param list2 the second list
   * @param <T>   the type of the elements
   * @return a new list with the elements of the two lists concatenated
   * @throws StackOverflowError for infinite lists
   */
  static <T> SeqList<T> concat(SeqList<T> list1, SeqList<T> list2) {
    if (list1.isEmpty()) {
      return list2;
    }
    return new Cons<>(list1.head(), concat(list1.tail(), list2));
  }

從 map 和 flatMap 方法的實作中可以看出，我們使用遞歸呼叫來遍歷列表並將函數應用於每個元素。 flatMap 方法有點複雜，因為它需要函數傳回一個新列表，我們需要將其與列表的其餘部分連接起來。由於其眾所周知的難度和使用高級資料結構的重要性，這兩種方法都不使用結構共享。未來的改進將在以後的文章中進行探討。

使用範例

讓我們來看看 SeqList 的一些使用範例。

• 假設我們有一個整數列表，我們想要過濾掉偶數，然後將它們乘以 2 的冪，但具有不變性和持久性。

SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
SeqList<Double> updatedList = list
   .filterOut(number -> number % 2 == 0)
   .map(number -> Math.pow(number, 2));

• 假設我們有一個字串列表，我們想用前綴和後綴將它們連接起來。

SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
   .map(letter -> "prefix" + letter + "suffix");

• 假設我們有一個列表列表，我們想要將它們展平。

SeqList<SeqList<Integer>> list = SeqList.of(SeqList.of(1, 2), SeqList.of(3, 4), SeqList.of(5, 6));
SeqList<Integer> updatedList = list
   .flatMap(seqList -> seqList);

• 另一個例子是使用 JDK 21 開關表達式進行模式匹配並利用編譯器檢查。

SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
  case Empty() -> {
    // do something
  }
  case Cons<Integer> cons -> {
    //do something else
  }
}

缺點

1. 效能：如果清單主要用於從清單頭部取得元素的前置元素，那麼效能就很好。在所有其他情況下，此實作至少需要 O(n)。
2. 複雜性：持久且不可變的 LinkedList 的實現比其可變的對應物更複雜。
3. 記憶體：由於為每個操作建立新列表，持久且不可變的 LinkedList 的實現比其可變的對應項需要更多的記憶體。透過結構共享，這種情況會得到緩解，但不會消除。

結論

在本文中，我們用 Java 實作了一個具有部分結構共享的持久且不可變的 LinkedList。我們演示了不變性和持久性的好處以及如何在 Java 中實現它們。我們也展示如何將 LinkedList 轉換為 Monad 以便更輕鬆地進行函數組合。我們討論了持久性和不可變資料結構的優點和缺點以及如何在實踐中使用它們。

以上是持久且不可變的 Java LinkedList的詳細內容。更多資訊請關注PHP中文網其他相關文章！