插入阵列前面

Question

有没有办法在数组的前面插入一个元素？有人告诉我，除了使用圆形数组之外，还有一种方法。我们需要像检索和加法这样的操作来达到O(1(时间，所以像ArrayUtil这样的事情是不可能的。即。需要一个基元数组。

编辑：线程"Java 数组如何在开头添加元素"没有任何遵循原始数组的方法，解决方案都使用列表或其他东西，如 ArrayUtil。

Answer 1

Java 数组具有"固定"的大小。没有开箱即用的"添加"。添加总是意味着：增加数组的长度，因此：创建一个新数组并复制现有数据。

获得 O(1( 的唯一解决方案是查看一些"链表"，例如数组的实现，其中添加/插入元素只是关于调整"指针"。

Answer 2

在数组的开头插入需要将所有其他元素向右移动并删除最后一个元素。这意味着对于给定大小的数组，它在时间上是一致的(数组越长，花费的时间就越长(。如果要维护数组中已用条目的计数，则根据已用条目的数量，需要更长的时间(因为您不必移动未使用的条目(。(我认为这意味着它不符合您的 O(1( 要求，但我从未真正进入过 Big-O 符号......

听起来你可能想要一个链表，或者一个环形缓冲区。

Answer 3

由于 java 数组的大小是固定的，因此无论如何您都需要一个索引(以指示长度(。

您拒绝"循环"数组可能是一个错误。

final int N = 64;
String[] data = new String[N];
int start = 0;
int end = 0; // Exclusive.
int size() {
return (end - start + N) % N;
}
String get(int i) {
checkIndex(i);
int j = (start + i) % N;
return data[j];
}
void prepend(String s) {
checkNotFull();
start = (start - 1 + N) % N;
data[start] = s;
}

在一般情况下，通常使用Deque，ArrayDeque，LinkedList等数据结构。