Array.shift 和 JavaScript 中的链表等效项之间的性能差异是什么

Question

在 JavaScript 中实现队列时有很多选择。一种可能的实现是使用数组，使用 Array.push 将元素添加到队列中，并使用 Array.shift 从队列中删除它们。另一种可能的实现是使用链接列表并添加到尾部并从头部删除。

通过测试 Stacks 实现，我确定 Array.push 和 Array.pop，无论数组大小如何，都比在链表尾部添加或删除元素快 3-5 倍。因此，在JavaScript中，使用链表来实现堆栈是没有意义的。但我想知道，在队列的情况下，使用 Array.shift 从数组前面删除元素与从列表前面删除元素在性能上有什么区别？

Answer 1

测试在 Windows 10 上的 Chrome v63 上运行。

50,000 个或更少元素的集合
Array.shift 比链表上的等效操作慢 38%-40%。

超过 50,000 个元素的集合
Array.shift 本质上比链表上的等效操作慢 100%。

结论和建议
Array.shift，即使在小型数组上，也比在链接列表上慢，但如果您所要做的只是到处进行一些添加或删除操作，那么性能损失可能不足以保证实施链接列表。与阵列一起走。另一方面，如果您有超过 50k 个元素的集合或经常添加和删除大量项目，则可能值得实现链接列表。

有趣的是，V8 显然在幕后应用了一些优化以使 Array.shift 更快，但该优化似乎仅适用于大小为 50,000 或更小的数组。只要看看这个基准测试，就很明显了：https://jsperf.com/likedlistvsarray/1