持久且不可变的 Java LinkedList

在文章实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《持久且不可变的 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 表示为由两个类组成的递归数据结构：

public record empty() implements seqlist {
}

public record cons(t head, seqlist tail) implements seqlist {
}

其中 cons 是一个名为 construct 的函数式编程术语，其历史可以追溯到 lisp 编程语言。

鉴于上述，我们可以实现 seqlist 接口如下：

public sealed interface seqlist permits empty, cons {
  /**
   * creates an empty list.
   *
   * @param  the type of the elements
   * @return an empty list
   */
  static  seqlist 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       the type of the elements
   * @return a new list with the elements added
   */
  @safevarargs
  static  seqlist of(t... elements) {
    seqlist 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 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 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 head, seqlist tail) implements seqlist {

  @override
  public boolean isempty() {
    return false;
  }

  @override
  public optional headoption() {
    return optional.ofnullable(head);
  }

  @override
  public optional last() {
    if (tail.isempty()) {
      return optional.ofnullable(head);
    }
    return tail.last();
  }
}

public record empty() implements seqlist {

  @override
  public boolean isempty() {
    return true;
  }

  @override
  public t head() {
    throw new unsupportedoperationexception("head() called on empty list");
  }

  @override
  public optional headoption() {
    return optional.empty();
  }

  @override
  public seqlist tail() {
    throw new unsupportedoperationexception("tail() called on empty list");
  }

  @override
  public optional last() {
    return optional.empty();
  }
}

我们可以从删除方法的实现中检查，我们正在使用递归调用来从中删除元素
列表。这是函数式编程中的典型模式，我们使用递归来遍历列表并
删除该元素。应注意避免在无限列表的情况下堆栈溢出。未来的改进可能是使用 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.
   * it does not use structural sharing as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the map function
   * @param  the type of the elements of the new list
   * @return a new list with the elements mapped
   * @throws stackoverflowerror for infinite lists
   */
  default  seqlist map(function 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.
   * it does not use structural sharing as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the flat map function
   * @param  the type of the elements of the new list
   * @return a new list with the elements flat mapped
   * @throws stackoverflowerror for infinite lists
   */
  default  seqlist flatmap(function> fn) {
    if (isempty()) {
      return empty();
    }
    seqlist mappedhead = fn.apply(head());
    seqlist 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    the type of the elements
   * @return a new list with the elements of the two lists concatenated
   * @throws stackoverflowerror for infinite lists
   */
  static  seqlist concat(seqlist list1, seqlist list2) {
    if (list1.isempty()) {
      return list2;
    }
    return new cons<>(list1.head(), concat(list1.tail(), list2));
  }

seqlist list = seqlist.of(1, 2, 3, 4, 5, 6);
seqlist updatedlist = list
   .filterout(number -> number % 2 == 0)
   .map(number -> math.pow(number, 2));

seqlist list = seqlist.of("a", "b", "c", "d", "e");
seqlist updatedlist = list
   .map(letter -> "prefix" + letter + "suffix");

seqlist> list = seqlist.of(seqlist.of(1, 2), seqlist.of(3, 4), seqlist.of(5, 6));
seqlist updatedlist = list
   .flatmap(seqlist -> seqlist);

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