-1

谁能清楚地告诉我为什么？

ArrayList中读取很简单，（我们可以通过它的数组索引访问），为什么不是linkedList

在 arrayList 中插入元素很难我听说为什么？容易在linkedList 为什么？

删除数组列表中的元素很难为什么？容易在linkedList 为什么？

我知道一些关于数组的事情，但是在linkedXXX中发生了什么

谢谢你。

4

2 回答 2

3

在 ArrayList 中，你在内存中保存了一个引用数组，也就是说，你有一个内存位置。当您请求 ArrayList 的第一个元素时，您只需访问内存位置。当您访问第 10 个元素时，您访问的内存位置是引用大小的 10 倍。

在 LinkedList 中，您有一个元素，该元素具有对下一个元素的引用。下一个引用下一个，依此类推。如您所见，如果不逐个获取下一个元素，就无法直接访问 LinkedList 中的第 10 个元素。

所以，你的问题：

在 arrayList 中插入元素是 touch 我听说为什么？容易在linkedList 为什么？

将元素插入 ArrayList 有两个问题：

  1. 当您将一个元素放在位置 3 时，您需要首先从位置 3 开始移动每个元素并将它们向右移动一次（3 变为 4，4 变为 5，等等...），以便 3 变为空，您可以放入新元素

  2. 如果支持 ArrayList 的数组已满，则需要创建一个新数组！这是非常昂贵的，因为您需要重新分配内存，然后将所有元素复制到新数组中，并销毁旧数组。

另一方面，在 Linkedlist 中，您转到指向 2 的元素 1，然后转到 2。在 2 中，有对旧元素 3 的引用，您将其临时存储在其他地方。您将其替换为对新元素的引用，然后在新元素中，将 next 指向旧的 3。因此，这样做成本更低。

删除arraylist中的元素是触摸为什么？容易在linkedList 为什么？

与插入类似的原因。在 ArrayList 中，您必须再次将所有元素向下移动，在 LinkedList 中，一旦您位于元素 2，您将其下一个点指向 4，瞧，3 被删除。

如果您要以随机顺序访问元素，但为了完整性， ArrayLists 非常棒，但存在添加和减去的问题。LinkedLists 非常适合添加和删除，但获取不是第一个或最后一个元素需要额外的成本。所以总会有取舍！

于 2012-06-11T08:09:44.527 回答
2

ArrayList 由一个数组支持，该数组不能增长或缩小，也不能插入或删除元素。因此插入和删除是昂贵的操作，因为必须创建一个新数组并将现有值从一个数组复制到另一个数组。但是数组可以通过索引访问，所以这里的随机访问要快得多。

LinkedList 由节点对象组成，这些节点对象在一个方向或两个方向上具有彼此的指针（是的，我知道）。删除这些节点之一或插入一个新节点非常便宜，但要获得节点 nr。12345，你必须从头开始，遍历 12344 个节点，这意味着这里的随机访问非常昂贵。注意：Java LinkedList 不仅是 List，顺便说一句，它还实现了Queue和Deque接口。

我认为两者都同样适合简单的迭代，但底层机制完全不同。

于 2012-06-11T08:11:02.333 回答