0

In Java, when you do this:

alist[0].remove();

What happens to the rest of the array list. Do all of the objects move up one or do they stay the same and there is just an empty index at [0]?

If not, is there an efficient way of moving each object's index closer down by one?

To clarify what I mean by more effecient:

You could just remove the first index and then iterate through the ArrayList and delete each object and re-assign it to a new index, but this seems very ineffecient and it seems like there should be a way but I have looked through at the JavaDoc page for the ArrayList class and do not see anything that would accomplish what I am trying to do.

4

2 回答 2

5

假设您实际上是想问aList.remove(0)...

正如Oracle 所记录的

公共 E 删除(整数索引)

移除此列表中指定位置的元素。将任何后续元素向左移动(从它们的索引中减去 1)。

remove你需要的也是如此。但是,您可能认为实现效率不高,因为它需要的时间与列表中剩余的元素数量成正比。例如,如果您有一个包含 100 万个项目的列表,并且您删除了索引 0 处的项目,那么剩余的 999,999 个项目将需要移动到内存中。

于 2013-07-21T19:11:51.377 回答
1

忽略您发布的与 无关的代码ArrayList,如果您要查看源代码,ArrayList您会发现在调用ArrayList.remove(obj)它时会找到索引(或者如果使用remove(int)它已经知道)然后会:

System.arraycopy(elementData, index+1, elementData, index,
                          numMoved);

AnArrayList由一个数组支持,它将支持数组中的所有内容都向左移动。

在这种情况下,如果您正在使用,则查找为 O(1),remove(int)如果提供对象,则查找为 O(n),删除操作为 O(n)。

如果您要使用 aLinkedList查找是 O(n) 或 O(n) 但删除是 O(1) 因为它是一个双向链表。

选择数据结构时,重要的是要考虑如何使用它;总有取舍取决于您的使用模式。

于 2013-07-21T19:10:30.537 回答