ArrayList的VS阵列和List [英] ArrayList vs Array and List

问题描述

我已经对编程相当多的，最近开始学习更纯净的计算机科学主题（工作面试）。

I've been programming for quite a bit and recently started learning more pure Computer Science topics (for a job interview).

我认识一个数组和链表数据结构之间的差异，但现在，我已经使用Java我看到这个ArrayList的，这我无法概念化开始了。

I know the difference between an Array and a LinkedList data structure, but now that I have started using Java I'm seeing this ArrayList, which I'm having trouble conceptualizing.

网页搜索只是真的我知道如何使用它们以及何时使用它们（每个利益），但没有什么能回答我的问题：

Web searches have only really shown me HOW to use them and WHEN to use them (benefits of each), but nothing can answer my question of:

什么是一个ArrayList？我的假设是，它是维持存储器引用的每个元素的列表，使得它也能够像阵列。

What is an ArrayList? My assumption is that it is a list that maintains memory references to each element, making it also able to act like an array.

我也有感觉，因为Java是开放的，我应该能看类定义，但还没有想出怎么做，但无论是。

I also have a feeling since Java is open, that I should be able to look at the Class definition, but haven't figured out how to do that yet either.

谢谢！

推荐答案

我喜欢把它看作是一个数据结构，可以让你享受两个世界中，快速进入指数像数组和无限生长的列表。当然，总有一些取舍。

I like to think of it as a data-structure that lets you enjoy both worlds, the quick-access to an index like with an array and the infinite growth of a list. Of course, there are always trade-offs.

的ArrayList 其实是一个包装到一个数组。每一阵列的大小结束时间，一个新的数组，两倍的大小，创建并都从原始阵列中的数据复制到新的。

ArrayList is actually a wrapper to an array. Every time the size of the array ends, a new array, twice the size, is created and all the data from the original array is copied to the new one.

从Java文档：

List接口的大小可变数组的实现。实现了所有
  可选列表操作，并允许所有元素，包括null。在
  除了实现List接口，此类提供
  方法来操作在内​​部使用的数组的大小
  存储列表。 （这个类是大致相当于矢量，除了
  这是不同步的。）的尺寸，的isEmpty，获取，设置，迭代器和
  操作的ListIterator在固定时间内运行即可。在添加操作运行
  在固定的时间里，即，添加n个元素需要O（N）
  时间即可。其他所有操作都以线性时间运行（粗略地
  请讲）。相比，对于恒定因数低
  LinkedList的执行情况。

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.) The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

每个ArrayList实例都有一个容量。容量的大小
  阵列用于存储列表中的元素。它始终是在
  至少一样大的列表的大小。作为元素被添加到一种
  ArrayList中，其容​​量会自动增加。生长的细节
  政策不超出事实添加元素都指定
  不断摊销的时间成本。

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

应用程序可以增加一个ArrayList实例的容量
  在使用ensureCapacity加入了大量的元素之前
  操作。这可能会降低增量再分配的数量

An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

这使得 O（1）作为最喜欢它的操作的访问将采取一个数组。在一段时间后，你需要为此付出性能的插入操作虽然花费更长的时间。

This allows O(1) access for most of the operations like it would take with an array. Once in a while you need to pay for this performance with an insert operation that takes much longer though.

这就是所谓摊销复杂性。每次操作只需要 O（1）抛开那些你需要数组的规模扩大一倍倍。在这些时候，你将支付的 O（N），但如果要分摊到n个操作，所用的平均时间仅为 O（1）而非 O（ N）

This is called amortized complexity. Each operation takes only O(1) aside for those times you need to double the size of the array. In those time you would pay O(n) but if you average it over n operations, the average time taken is only O(1) and not O(n).

让我们看一个例子：

我们拥有大小为100（N = 100）的数组。你让100的插入操作（不同的指数）和他们每个人只需要 O（1），当然，所有获得按索引操作还需要 O（1）（因为这是一个数组）。在101的插入，没有更多的阵列中更多的能力，使该ArrayList将创建一个新的阵列，200的尺寸，所有的值复制到它（ O（N）操作），然后插入第101项。直到您填写数组200个项目，所有的操作将采取的 O（1）

We have an array of size 100 (n=100). You make 100 insert operations (to different indices) and each of them takes only O(1), of course that all get-by-index operations also take O(1) (as this is an array). On the 101 insertion, there's no more more capacity in the array so the ArrayList will create a new array, the size of 200, copy all the values to it (O(n) operations) and then insert the 101st item. Until you fill out the array to 200 items, all of the operations would take O(1).

这篇关于ArrayList的VS阵列和List的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！