持久且不可變的 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 函數式程式設計之旅，您可以查看這個很棒的小型庫FunctionalUtils。

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

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

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

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

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

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

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

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

鑑於上述，我們可以實作 SeqList 介面如下：

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

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

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

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

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

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

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

使用範例

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

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

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

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

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

缺點

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

結論

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

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