java - 具有良好插入、移除和随机访问能力的数据结构

Question

目前，我正在寻找以下数据结构。

1. 快速插入尾部。
2. 快速从头部移除。
3. 能够执行随机访问。

我意识到 ArrayBlockingQueue 擅长 (1) 和 (2)，而 ArrayList 擅长 (3)。是否有来自标准库/Apache 库/Google 库的单一数据结构，使我能够同时满足所有 3 个要求？

Answer 1

我认为最适合你的数据结构是 ringbuffer/circular buffer .环形缓冲区在恒定时间内执行所有三个操作。

可以找到实现 here和许多其他here

编辑:环形缓冲区的问题是您应该在开始时就知道在最坏情况下该缓冲区中有多少元素。但也存在动态环形缓冲区。