哪一个运行得更快，ArrayList或LinkedList？
List li = new LinkedList(); for (int i = 0; i < 100; i++) { li.add(i); } long start1 = System.nanoTime(); li.get(57); long end1 = System.nanoTime(); long diff1 = end1-start1; System.out.println("Time taken by LinkedList = "+diff1); List al = new ArrayList(); for (int i = 0; i < 100; i++) { al.add(i); } 我在两个列表上执行的操作，当我打印出所用的时间时，ArrayList总是比LinkedList运行得更快。 有人可以解释哪个时间表现更好吗？ 如果代码中有问题，请告诉我。 谢谢！
如果必须执行大量插入和不频繁查找，请使用LinkedList 。 如果执行的查找次数多于插入次数，请使用ArrayList 。
原因如下 – ArrayList由具有初始容量的数组支持。 因此，如果您继续将项目插入列表中，则必须重新调整其数组容量以容纳新插入的项目，如果执行索引特定插入，它可能还必须移动现有项目。 另一方面， LinkedList由LinkedList支持，其中创建项总是在恒定时间内执行 – 创建项并将其分配到列表的末尾。 这里没有重新调整。
现在要从ArrayList获取一个项目，它总是需要一段时间，因为它可以在一个恒定的时间内轻松索引后备数组。 但是从LinkedList获取项目可能会导致您遍历整个链接列表以查找项目节点。 因此，在这种情况下，它执行的次数少于ArrayList 。
从上面的讨论中，您可以看到，当您有更多插入操作时， LinkedList将始终优于ArrayList因为后者具有与插入相关联的内部resize成本 ，而前者则没有。 另一方面，如果你有不频繁的插入和频繁的查找， ArrayList将总是胜过LinkedList因为对于后者你可能必须遍历整个链表结构才能找到所需的项目，而前者将能够快速找到你的项目使用恒定时间的数组索引。
当您处理大量物品（例如，数千件物品）时，所有上述效果都将可见并影响您的应用程序的性能。 对于较少的项目，性能差异不太明显。
现在，关于你的代码，你有一些严重的问题。 对于初学者，你使用的是原始类型，这很糟糕，因为你失去了generics所提供的所有类型安全性。 编写新代码时，应始终使用Collection API的通用版本。 因此，更改您的代码如下 –
List li = new LinkedList (); for (int i = 0; i < 100; i++) { li.add(i); } long start1 = System.nanoTime(); li.get(57); long end1 = System.nanoTime(); long diff1 = end1 - start1; System.out.println("Time taken by LinkedList = "+diff1); List al = new ArrayList (); for (int i = 0; i < 100; i++) { al.add(i); }
请参阅Effective Java ， 第23项：不要在新代码中使用原始类型以获取详细说明。
编辑
从评论中的讨论中可以明显看出，如果你需要在列表中间或随机位置插入元素，那么ArrayList在性能方面优于LinkedList ，因为前者将使用memcpy来移动非常快的元素，后者必须遍历到所需的索引才能正确插入新元素，这个元素较慢。 因此对于随机插入， ArrayList也优于LinkedList 。 LinkedList优于ArrayList的唯一情况是，如果您只在列表的末尾插入，并且有很多这些插入。
在读取方面，数组列表总是比链接列表快。 ArrayList基本上是数组实现，并且为数组分配的内存是顺序的，因此读取速度更快。 但是当你使用列表需要在列表之间插入或删除时，链接列表更快。 因为它只需要在节点之间添加链接。 在这两种情况下，数组列表会更慢。用法可以是：
ArrayList – 更快的读取操作，列表之间的插入和删除更慢。 链表 – 与数组列表相比，读操作速度慢但列表之间的插入，删除速度更快。
ArrayList由数组支持， LinkedList支持的Node与refernece链接。
因此，对ArrayList操作是对ArrayList非常有效的操作。 添加操作以分摊的常量时间运行，即添加n个元素需要O(n)时间。 所有其他操作都以线性时间运行（粗略地说）。 与LinkedList实现相比，常数因子较低。
并且在LinkedList所有操作都按照双链表的预期执行。 索引到列表中的操作将从开头或结尾遍历列表，以较接近指定索引为准。
阅读更多文档 –
- 数组列表
- 链表
链接列表将在添加每个元素时创建新节点，而不在数组列表中。
如果您知道初始大小然后在创建时将其传递给ArrayList，它可以避免像新ArrayList（100）那样重建数组;