Java ArrayList 实现

Question

我一直在尝试比较列表的定义和Java中的实现，因为我觉得它们不匹配。 列表数据结构的定义：列表或序列是一种抽象数据类型，实现了一个有序的值集合，其中相同的值可能会出现多次。[摘自：http://en.wikipedia.org/wiki/List_(abstract_data_type)]

现在，有序集合维护元素插入的顺序。

Java中列表的实现 -> ArrayList：根据这个实现，我有以下几点：

1. 如果我初始化一个大小为5的ArrayList，那么我不能直接在第5个位置插入元素，而不插入1、2、3、4位置的元素，因为这将违反排序原则。所以Java在这里会抛出异常，我完全同意。
2. ArrayList提供了像"set(int index, E element)"和"add(int index, E element)"这样的方法，使用它们我们可以替换列表中间的元素，也可以在列表中间插入新元素。我不理解这一点。这违背了排序原则，因为插入顺序没有得到维护。

我觉得第一点和第二点相互矛盾，第二点违反了排序原则，或者我可能漏掉了什么。

有人能否请解释一下我对List的理解有哪些错误？

- Lokesh

---

请检查正式定义，据我理解 ArrayList 不会违反它们。 - Thihara

你能指引我一些正式的定义吗？ - Lokesh

请检查维基百科链接。那里已经有了... - Thihara

请仔细阅读帖子！！我只是从维基百科上粘贴了定义。 - Lokesh

我指的不是人们可能会误解的定义...请参阅“抽象定义”部分。 - Thihara

@loki：我非常确定stan0已经正确回答了你的问题。你引用了维基百科中提到列表排序的部分，并将其解释为插入排序，但实际上维基百科文章中并没有提到这一点。Java列表接口中替换、添加和删除特定索引处元素的操作都在维基百科的“特征”段落中有所描述。 - jarnbjo

Answer 1

1. 这个定义并没有说列表的大小或者通过索引添加元素时会发生什么事情。它只是说元素的顺序不会“突然”改变。

   这和“集合”类型形成了对比，因为在添加新元素时元素的顺序可能会改变。如果你在一个5个元素的列表中的第二个位置插入一个元素，则第三个元素不会突然跳到列表的开头。

2. 这个定义也没有说明必须具备哪些操作，只是说明了可能具备哪些操作。为了使列表的操作更有效率，有一个能够在任何地方插入元素（当然要符合法律界限）的方法以及一种能够替换元素而不改变现有元素索引的方法特别有用。

   如果缺少第二个操作，那么替换元素将需要进行add()和remove()两个都很耗费资源的操作，取决于实现方式。

   同时，这两个操作清楚地说明了它们如何在应用时影响其他元素的排序。 set()不会改变其他元素的排序，而add()会递增插入点之后所有元素的索引。

- Aaron Digulla

---

当你说“元素的顺序不会突然改变”时，我们如何衡量突然的改变？ - Lokesh

@loki：你可以这样定义它：在一个操作之后，仍留在列表中的元素的相对顺序保持不变。 - nhahtdh

向集合中添加元素可能会改变所有元素的顺序，看起来就像有人把它们洗牌了一样。在列表中，只有插入点后面的元素会发生变化，而相对顺序始终保持不变：当我在位置2插入一个元素时，元素#2被移动到位置3，但它仍然在第一个元素之后和旧的#3之前。 - Aaron Digulla

Answer 2

有序的值集合并不意味着插入顺序。它意味着一堆项目被放置在某个地方，一个接一个地访问它们。

具有在特定索引处插入项目的能力使您对顺序有控制权。

- stan0

---

如果我按照那个定义去做，那么ArrayList应该允许我在连续的位置插入元素。因此，即使位置1和2为空，只要它们是连续的，我就应该被允许在3、4、5处插入。不是吗？ - Lokesh

其他语言（甚至实现自定义列表的Java库）当然可以允许具有非连续索引范围或以任意索引而不是0开始的连续索引范围的列表。然而，java.util.List的API文档暗示列表具有连续的索引范围，从0到length-1编号。 - jarnbjo

Answer 3

一个ArrayList有一个顺序，这就是它的意思。如果你在某个地方插入一个值，它仍然有一个顺序，即使它看起来很愚蠢。如果你想要一个有意义的顺序，那么你必须查看可比较的接口。

- Oliver Watkins

Answer 4

一个 ArrayList，就像任何一个 java.util.List 一样，维护元素插入顺序。

假设我们有一个空的 ArrayList。我们添加 A，然后是 B，再是 C。列表将如下所示：[A, B, C]。不是 [C, A, B] 或者 [A, C, B]。现在，如果我们在索引 1 插入 D，列表将如下所示：[A, D, B, C]。不是 [A, B, C, D] 或其他任何可能适用于其他类型的 Collection。

Java 的 List 不意味着人工元素排序，例如 Sorted 集合，也不意味着随机元素排序，例如某些集合，例如 HashSet 等等。

- Tadas S

Answer 5

您可以像XXXXXXX这样向列表中添加元素O。添加了元素后，您将拥有XXXXXXO。

如果您尝试在大于列表大小的位置上添加元素，则会出现空洞，如XXXXXX O。

add（position，element）用于在列表内添加元素，例如add（2，O）-> XXXOXX

列表不是像数组一样具有可能位置的字段，而是一个集合。

- Lukas Eichler

---

你是不是指在位置上使用 put？ - Menno

我同意你所谈论的整体概念。你会如何解释排序？ - Lokesh

put() 方法被 Map 使用，而不是 Collections。您可以通过实现 Compareable<T> 接口并定义排序值算法来进行排序。然后，您可以使用 Collections.sort(list) 对列表进行排序。 - Lukas Eichler

Answer 6

正如你所发现的，ArrayList 不保持顺序，并且具有随机的 get/set 方法。这是正确的。

我认为维基百科的定义是错误的，不完全正确，或者不适用于 Java 对 List 的理解，显然比 Ordered List 少一点。

如果你想在插入时进行排序，Java SE API 提供了 TreeSet，你必须在创建时提供一个 Comparator 或让要插入的元素实现 Comparable 接口。否则，元素将使用它们的自然排序进行排序。

在我看来，Java 的 ArrayList 只是一个受管理的数组，非常方便，适用于大多数用例。

- A4L