java - 用于连续添加和廉价删除的数据结构

Question

我正在读这篇文章blog post关于使用 Gnuplot 和 Cairo -terminal 制作动画，算法的计划很简单

• 将 png 图像保存到工作目录，并且
• 将最新视频保存到工作目录。

我想要更多的东西，以便用户在转换图像时也可以实时浏览图像:

数据并行模型 - 规则排列在数组中的数据结构

• 在某个界面中为用户提供一些列表，用户可以通过箭头按钮浏览
• 在此界面中，新图像将添加到列表末尾
• 用户还可以实时从流中删除不良图像

这可能在并行编程的数据并行模型中运行良好，即在数组中定期结构化的数据集。操作(添加、删除)可以对此数据进行操作，但独立于不同的进程。

为了简单起见，我们假设版本 1 中不需要进行高效搜索。但是，如果您提供的模型也可以做到这一点，我很乐意考虑它 - 我们将其称为版本 2。

我认为列表在这里不是一个好的数据结构，因为需要在数据结构的末尾进行删除和连续轻松添加的机会。由于删除，数据结构stack也无法工作。我认为某种树数据结构可以工作，因为那里的删除和搜索相当便宜。然而，数据并行模型中的简单数组就足够了。

语言

由于并行性，我认为 Java 是一个不错的选择。然而，任何语言和伪代码都可以。

前端

我的直觉是，前端这样的系统的要求应该是 qT 作为终端仿真器。

什么是更好的数据结构，可以实现廉价的删除和最后的连续添加？

Answer 1

Java LinkedList 似乎是您可以用于版本 1 的东西。您可以使用其单个参数 add() 在恒定时间内附加到列表。如果“实时”是指当图像在用户的显示器中并因此以某种方式指向时，也可以在恒定时间内删除它们。优化内存使用，并且无需像 Arraylist 那样重新实例化。任何在对象上实现的双向链表(而不是数组)都可以。

你的第二个版本不够清晰。