选择的列表结构：
同步的LinkedList。
场景：
我的程序需要在网格中渲染一些(相当于计算)生成的图像。每当(在另一个线程上)一些数据值发生变化时，这些图像都必须更新，因此，我有一个渲染队列来管理它。
渲染队列是一个同步的LinkedList，在低优先级线程上，它不断被迭代，以检查是否需要进行一些渲染工作。由于图像基于各种数据，每个数据都可以独立更改，因此我需要某种形式的队列来组合更改。
数据往往会分块变化，所以当一个大批量通过时，我会看到一条假想的线沿着它重新渲染瓦片的区域延伸。为了稍微完善一下，我决定不按标准顺序渲染，而是按随机顺序渲染(以产生"溶入/溶出"效果)。
它看起来很可爱，但唯一的问题是，完成这种效果所需的时间明显不同。
问题：
我已经从理论上推断了随机访问这个列表而不是迭代访问会导致如此显著的延迟的几个原因。首先，随机数生成器的nextInt方法可能会占用足够长的时间。其次，由于它是一个LinkedList，当列表的大小在4000秒范围内时，获得第n个项目可能也很重要。
我可能忽略了这次延误的其他原因吗？与其使用随机数生成器，甚至链表，我还能如何有效地实现随机访问&从列表中删除？如果你读过这个场景，也许你可以想出另一种方法，我可以完全这样做？
要求：
- 添加到&修改列表
- 随机存取&从列表中删除项目
- 高效的操作，具有大的数据集&运行次数
您可以使用ArrayList和几个简单的操作来非常有效地实现这一点。
- 要插入，请始终在列表末尾插入新作品(摊余恒定时间运算)
- 要提取随机作品，请选择一个随机数
i，将i处的元素与列表末尾的元素交换，然后提取并返回新的最后一个元素
以下是代码(未测试、未编译)：
class RandomizedQueue<T> {
private final List<T> workItems = new ArrayList<>();
private final Random random;
RandomizedQueue(Random random) {
this.random = random;
}
public synchronized void insert(T item) {
workItems.add(item);
}
public synchronized T extract() {
if (workItems.isEmpty()) {
return null; // or throw an exception
}
int pos = random.nextInt(workItems.size());
int lastPos = workItems.size() - 1;
T item = workItems.get(pos);
workItems.set(pos, workItems.get(lastPos));
return workItems.remove(lastPos);
}
}
您可以使用PriorityQueue，在向该队列添加内容时，为每个项目赋予随机优先级。渲染总是可以取队列中的顶部元素，因为它已经被随机化了。在PriorityQueue中的"随机"位置插入(或者更好地说，具有随机优先级)真的很快。