java - ArrayList or LinkedList or TreeMap 用什么？

Question

在我的问题中，我有一大组数字。在运行时，我想在这个排序的数字系列中插入一个数字，并获取插入数字的下一个(下一个升序)数字(所有内容都已排序)，然后删除插入的数字。

还有一个限制条件，有时我要插入的数字与我初始集合中的某个其他数字完全相等，在这种情况下我也想获取下一个数字。

我很困惑我是否应该使用 TreeMap(因为 TreeMap 总是排序的，但有一个键的开销)一个 LinkedList(因为输入和删除值变得更容易)或一个简单的数组列表？

我正在将这些数字加载到内存中并执行大量计算，我的平台是移动的，所以我想要一些高效的东西。有什么提示吗？到目前为止，我使用的是链表，虽然我没有遇到任何性能问题，但我想加快这个过程。

Answer 1

如果我对你的问题的理解正确，你真的不必插入数字来获取下一个数字，因为无论如何你都会删除它。在那种情况下，您可以使用简单的 ArrayList 本身来执行类似的操作以获得良好的性能

List<Integer> lst = new ArrayList<>();
lst.add(1);
lst.add(2);
lst.add(4);
lst.add(8);
lst.add(15);

// Collections.sort(lst); // assuming list is sorted

// your key 
int key = 7;

// binary search to look for position where it would be inserted.
// if negative number does not exist so next number would be at ' -pos - 1' 
// if positive number exists so next number would be at 'pos + 1' 
int pos = Collections.binarySearch(lst, key);
pos = pos < 0 ? -pos - 1 : pos + 1;

// check for out of bounds as search for last number would give index out of bounds
pos = pos == lst.size() ? pos - 1 : pos;

// your next number
System.out.println(lst.get(pos));