持久且不可变的 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中文网其他相关文章！