4

我一直在尝试比较列表的定义及其在 Java 中的实现，因为我觉得不匹配。

列表数据结构的定义：列表或序列是一种抽象数据类型，它实现了值的有序集合，其中相同的值可能出现多次。[取自：http://en.wikipedia.org/wiki/List_(abstract_data_type) ]

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

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

  1. 如果我初始化一个ArrayList大小为 5 的元素，那么我不能直接在第 5 个位置插入元素而不在位置 1、2、3、4 插入元素，因为这将违反排序原则。所以Java在这里给出了我完全同意的例外。
  2. ArrayList提供了诸如“set(int index, E element)”和“add(int index, E element)”之类的方法，我们可以使用它们替换列表中间的元素，也可以在列表中间插入新元素。我不明白。由于不维护插入顺序，因此违反了排序原则。

我觉得第 1 点和第 2 点相互冲突，而第 2 点违反了排序原则，或者我可能遗漏了一些东西。

有人可以解释一下我对List这里的理解哪里出错了吗？

4

6 回答 6

2

  1. 该定义没有说明列表的大小或按索引添加元素时会发生什么。它只是说元素的顺序不会“突然”改变。

    这与“set”类型形成对比，其中元素的顺序可以通过添加新元素来改变。如果在 5 元素列表的第二个位置插入一个元素，则第三个元素不会突然跳到列表的开头。

  2. 该定义也没有说必须有哪些操作，只说它可能有什么。对于列表的高效操作，有一种方法可以在任何地方插入元素（当然是在合法边界内），并且能够在不更改现有元素索引的情况下替换元素。

    如果缺少第二个操作，则替换元素将需要add()加上remove()这两个都是昂贵的操作，具体取决于实现。

    此外，这两个操作都清楚地解释了它们在应用时如何影响其他元素的顺序。在插入点之后增加所有元素的索引时，set()不会更改其他元素的顺序。add()

于 2013-04-26T10:11:20.590 回答
1

Arraylist 有一个顺序，这就是它的全部含义。如果你在某处插入一个值，它仍然有一个订单，即使它看起来很傻。如果您想要一个有意义的订单，那么您必须查看可比较的接口。

于 2013-04-26T10:27:07.220 回答
1

ordered collection of values并不意味着插入顺序。这意味着有一堆项目一个接一个地放置在某个地方，您可以按顺序访问它们。

能够在特定索引处插入项目使您可以控制顺序。

于 2013-04-26T10:14:02.447 回答
1

AnArrayList和 any 一样java.util.List，维护元素插入顺序。

假设我们有一个空的ArrayList. 我们添加 A，然后是 B，然后是 C。列表如下所示：[A, B, C]。不是[C, A, B]也不是[A, C, B]。现在，如果我们在索引 1 处插入 D，列表将如下所示[A, D, B, C]：不是或其他任何东西，这对于其他类型的s[A, B, C, D]来说是完全可能的。Collection

JavaList既不暗示像Sorted集合那样的人工元素排序，也不暗示像某些集合那样HashSet的随机元素排序。

于 2013-04-26T11:15:10.780 回答
0

您可以将元素 O 添加到类似的列表中XXXXXXX。使用添加的元素，您拥有XXXXXXO.

如果您尝试在大于列表大小的位置添加元素，则会出现类似XXXXXX O.

add(position, element) 用于在列表中添加元素，例如 add(2, O) ->XXXOXX

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

于 2013-04-26T10:07:44.713 回答
0

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

我会说wiki定义是错误的，不是完全正确的，或者不适用于Java理解的List，这显然比Ordered List

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

在我看来，JavaArrayList只是一个托管数组，它很方便，适合大多数用例。

于 2013-04-26T10:17:47.057 回答