data-structures - 在现实世界中重新实现数据结构

Question

今天算法课的主题是重新实现数据结构，特别是 Java 中的 ArrayList。您可以通过各种方式自定义结构这一事实确实让我感兴趣，尤其是 add() 和 iterator.remove() 方法的变体。

但是，与现实世界的程序员相比，重新实现和定制数据结构是学术界更感兴趣的事情吗？有没有人在商业应用程序/程序中重新实现了他们自己的数据结构版本，为什么你选择了这条路线而不是你的特定语言的实现？

Answer 1

了解数据结构是如何实现和可以实现的绝对是每个人都感兴趣的，而不仅仅是学术界。如果该语言已经提供了具有合适功能和性能特征的实现，您很可能不会重新实现数据结构，但您很可能必须通过组合其他数据结构来创建自己的数据结构……或者您可能需要实现行为与众所周知的数据结构略有不同的数据结构。在这种情况下，您当然需要知道原始数据结构是如何实现的。或者，您可能最终需要一个不存在的数据结构，或者它提供与现有数据结构类似的行为，但它的使用方式要求它针对不同的函数集进行优化。同样，这种情况需要你知道如何实现(和改变)数据结构，所以是的，它很有趣。

编辑
我不是提倡你重新实现现有的数据结构!不要那样做。我想说的是，这些知识确实有实际应用。例如，您可能需要创建一个双向 map 数据结构(可以通过组合两个单向 map 数据结构来实现)，或者您可能需要创建一个堆栈来跟踪各种统计信息(例如 min、max、 mean) 使用现有的堆栈数据结构，其元素类型包含值以及这些各种统计信息。这些是您可能需要在现实世界中实现的一些简单示例。