ArrayList 与 Array 和 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).

我知道 Array 和 LinkedList 数据结构之间的区别，但是现在我已经开始使用 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 是开放的，我应该能够查看 Class 定义，但也没有想出如何去做.

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 文档:

From the java doc:

List 接口的可调整大小的数组实现.实现所有可选的列表操作，并允许所有元素，包括 null.在除了实现 List 接口，这个类还提供操作内部使用的数组大小的方法存储列表.(这个类大致相当于 Vector，除了它是不同步的.)大小、isEmpty、get、set、iterator 和listIterator 操作以恒定时间运行.添加操作运行在摊销常数时间内，即添加 n 个元素需要 O(n)时间.所有其他操作都在线性时间内运行(大约请讲).常数系数低于链表实现.

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 与 Array 和 List的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！