linked-list - 链表单类 vs 多类

Question

在我作为计算机科学专业学生的第二个学期中，几乎整个学期我们都专注于编写不同变体(堆栈、队列等)的链表。这些列表的设计总是归结为这一点

class List<T> {
    class ListElement {
        T value;
        ListElement next;
    }
    ListElement root;
}

实现的方法及其工作方式有所不同(为简单起见，我在这里省略了构造函数和属性)。

某天我开始学习 Scala 并专注于函数式编程。这也到了编写链表但采用不同风格实现方式的地步。

class List[T]( head: T, tail: List[T])

尽管语法和不变性不同，但在我看来这是一种不同的方法。我心想“好吧，你可以用 C# 或 Java 中相同的方式来实现列表，而且比你学到的方法少一个 class”。

我明白为什么您会在递归不像 C# 或 Java 那样危险的函数式语言中实现这样的链表，因为至少在我看来，递归实现所有这种设计链表的常用方法非常直观。

我不明白的是为什么 C# 或 Java 中的链表通常以第一种方式实现，而您可以用更少的代码但同样冗长的其他方式来实现它们？(我不是在说关于列表在语言库中的实现，但关于您通常作为程序员编写的列表)

我可以看到第一种方法的唯一好处是您可以更好地向用户隐藏实现，但这是原因吗？这是否值得额外的 class ？ 我什至不需要向用户公开我的实现，因为我仍然可以在内部以不同的方式实现我的列表，并且可能只选择了这样的构造函数并提供将列表的第一个元素检索为 head 的功能。以及其余的 tail .

Answer 1

您提到的“以第一种方式实现”的原因包括

性能。

在编写算法或实现支持搜索和排序等操作的数据结构时，时间和空间复杂性是两个最重要的问题。正如您所提到的，以递归方式创建的列表是不可变的!创建列表的真正目的是实现更快的操作。所以设计师更喜欢“第一时尚”。

面向对象

在解决现实世界的问题时，最初的面向对象分析和设计 (OOAD) 非常重要。通过尽可能接近真实世界对象/事物的对象建模，设计人员可以获得更好的解决方案。递归的方法似乎忽略了这方面

可扩展性

API/库的设计者在起草设计时会牢记可扩展性。以“第一时尚”编写的代码更具可扩展性，并且易于理解。

其他设计问题

这并不是一个详尽的原因列表。编程民间传说中存在许多其他因素和基于经验的学习，导致选择第一种时尚。