几个月前，我在某处读到了一种在 O(1) 中将列表附加和前置到其他列表的有效方法，方法是用函数组合表示它们，一旦评估，就会在 O(n) 中构建结果列表。
不幸的是，我不记得这篇文章的来源或（如果存在）这种技术/方法的名称。请问您有这方面的参考吗？
问问题
1073 次
2 回答
11
该数据结构称为差异列表（或DList简称）。您可以在 Hackage 上提供的库中找到它的默认实现。
于 2012-07-04T13:25:35.183 回答
1
你一定在想ShowS和朋友们的前奏曲。见这里。
于 2012-07-04T13:14:24.993 回答