1. Overview
1.概述
When it comes to collections, the Java standard library provides plenty of options to choose from. Among those options are two famous List implementations known as ArrayList and LinkedList, each with their own properties and use-cases.
在谈到集合时，Java标准库提供了大量可供选择的选项。在这些选项中，有两个著名的List实现，即ArrayList和LinkedList，每个都有自己的属性和使用情况。
In this tutorial, we’re going to see how these two are actually implemented. Then, we’ll evaluate different applications for each one.
在本教程中，我们将看到这两者是如何实际实现的。然后，我们将评估每一种的不同应用。
2. ArrayList
2.ArrayList
Internally, ArrayList is using an array to implement the List interface. As arrays are fixed size in Java, ArrayList creates an array with some initial capacity. Along the way, if we need to store more items than that default capacity, it will replace that array with a new and more spacious one.
在内部，ArrayList使用一个数组来实现List接口。由于数组在Java中是固定大小的，ArrayList创建了一个具有一定初始容量的数组。在此过程中，如果我们需要存储比默认容量更多的项目，它将用一个新的、更宽敞的数组来替换该数组。
To better understand its properties, let’s evaluate this data structure with respect to its three main operations: adding items, getting one by index and removing by index.
为了更好地理解它的属性，让我们就其三个主要操作来评估这个数据结构。添加项目，按索引获取一个和按索引删除。
2.1. Add
2.1. 添加
When we’re creating an empty ArrayList, it initializes its backing array with a default capacity (currently 10):
当我们创建一个空的ArrayList时，它用默认容量（目前是10）来初始化其支持数组。
Adding a new item while that array it not yet full is as simple as assigning that item to a specific array index. This array index is determined by the current array size since we’re practically appending to the list:
在数组还没有满的时候添加一个新的项目，就像把这个项目分配给一个特定的数组索引一样简单。这个数组索引是由当前数组的大小决定的，因为我们实际上是在向列表中追加。
backingArray[size] = newItem;
size++;So, in best and average cases, the time complexity for the add operation is O(1), which is pretty fast. As the backing array becomes full, however, the add implementation becomes less efficient:
因此，在最佳和平均情况下，添加操作的时间复杂性是O(1)，这是很快速的。然而，随着支持数组变满，添加操作的效率就会降低。
To add a new item, we should first initialize a brand new array with more capacity and copy all existing items to the new array. Only after copying current elements can we add the new item. Hence, the time complexity is O(n) in the worst case since we have to copy n elements first.
为了添加一个新的项目，我们应该首先初始化一个具有更多容量的全新数组，并将所有现有项目复制到新的数组中。只有在复制了当前元素之后，我们才能添加新项目。因此，在最坏的情况下，时间复杂度是O(n)，因为我们必须先复制n个元素。
Theoretically speaking, adding a new element runs in amortized constant time. That is, adding n elements requires O(n) time. However, some single additions may perform poorly because of the copy overhead.
从理论上讲，添加一个新的元素在摊销的恒定时间内运行。也就是说，添加n 元素需要O(n) 时间。然而，由于复制的开销，一些单一的添加可能表现得很差。
2.2. Access by Index
2.2.按索引访问
Accessing items by their indices is where the ArrayList really shines. To retrieve an item at index i, we just have to return the item residing at the ith index from the backing array. Consequently, the time complexity for access by index operation is always O(1).
通过索引访问项目是ArrayList真正的优势所在。要检索索引i处的项目，我们只需从支持数组中返回驻留在i第索引处的项目。因此，通过索引操作访问的时间复杂度总是O（1）。
2.3. Remove by Index
2.3.按索引删除
Suppose we’re going to remove the index 6 from our ArrayList, which corresponds to the element 15 in our backing array:
假设我们要从我们的ArrayList中移除索引6，它对应于我们的后援数组中的元素15。
After marking the desired element as deleted, we should move all elements after it back by one index. Obviously, the nearer the element to the start of the array, the more elements we should move. So the time complexity is O(1) at the best-case and O(n) on average and worst-cases.
在将所需的元素标记为删除后，我们应该将它之后的所有元素向后移动一个索引。显然，元素越接近数组的开始，我们应该移动的元素就越多。所以时间复杂度在最佳情况下是O(1)，在平均和最差情况下是O(n) 。
2.4. Applications and Limitations
2.4.应用和局限性
Usually, ArrayList is the default choice for many developers when they need a List implementation. As a matter of fact, it’s actually a sensible choice when the number of reads is far more than the number of writes.
通常，ArrayList是许多开发人员需要List实现时的默认选择。事实上，当读取的数量远远大于写入的数量时，它实际上是一个明智的选择。
Sometimes we need equally frequent reads and writes. If we do have an estimate of the maximum number of possible items, then it still makes sense to use ArrayList. If that’s the case, we can initialize the ArrayList with an initial capacity:
有时我们需要同样频繁的读和写。如果我们确实对可能的最大项目数有一个估计，那么使用ArrayList仍然有意义。如果是这样的话，我们可以用一个初始容量来初始化ArrayList。
int possibleUpperBound = 10_000;
List<String> items = new ArrayList<>(possibleUpperBound);This estimation may prevent lots of unnecessary copying and array allocations.
这种估计可以防止大量不必要的复制和阵列分配。
Moreover, arrays are indexed by int values in Java. So, it’s not possible to store more than 232 elements in a Java array and, consequently, in ArrayList.
此外，数组在Java中是由int values索引的。所以，在Java数组中不可能存储超过232的元素，因此，在ArrayList中也不可能。
3. LinkedList
3.LinkedList
LinkedList, as its name suggests, uses a collection of linked nodes to store and retrieve elements. For instance, here’s how the Java implementation looks after adding four elements:
LinkedList，正如其名称所示，使用链接节点的集合来存储和检索元素。例如，下面是添加四个元素后的Java实现的情况。
Each node maintains two pointers: one pointing to the next element and another referring to the previous one. Expanding on this, the doubly linked list has two pointers pointing to the first and last items.
每个节点都保持两个指针：一个指向下一个元素，另一个指向上一个元素。在此基础上扩展，双链式列表有两个指针，分别指向第一个和最后一个项目。
Again, let’s evaluate this implementation with respect to the same fundamental operations.
再一次，让我们针对相同的基本操作来评估这个实现。
3.1. Add
3.1. 添加
In order to add a new node, first, we should link the current last node to the new node:
为了添加一个新的节点，首先，我们应该将当前的最后一个节点链接到新的节点。
And then update the last pointer:
然后更新最后一个指针。
As both of these operations are trivial, the time complexity for the add operation is always O(1).
由于这两种操作都是微不足道的，所以加法操作的时间复杂度总是O(1)。。
3.2. Access by Index
3.2.按索引访问
LinkedList, as opposed to ArrayList, does not support fast random access. So, in order to find an element by index, we should traverse some portion of the list manually.
LinkedList，与ArrayList相反，不支持快速随机访问。因此，为了通过索引找到一个元素，我们应该遍历列表的某些部分 手动。
In the best case, when the requested item is near the start or end of the list, the time complexity would be as fast as O(1). However, in the average and worst-case scenarios, we may end up with an O(n) access time since we have to examine many nodes one after another.
在最好的情况下，当请求的项目接近列表的开始或结束时，时间复杂度将快至O(1)。然而，在平均和最坏的情况下，我们最终可能会得到O(n) 的访问时间，因为我们必须一个接一个地检查许多节点。
3.3. Remove by Index
3.3.按索引删除
In order to remove an item, we should first find the requested item and then un-link it from the list. Consequently, the access time determines the time complexity — that is, O(1) at best-case and O(n) on average and in worst-case scenarios.
为了删除一个项目，我们应该首先找到所请求的项目，然后从列表中取消它的链接。因此，访问时间决定了时间复杂度–即在最佳情况下是O(1)，在平均和最坏情况下是O(n)。
3.4. Applications
3.4.应用
LinkedLists are more suitable when the addition rate is much higher than the read rate.
LinkedLists在添加率远高于读取率时更适合。
Also, it can be used in read-heavy scenarios when most of the time we want the first or last element. It’s worth mentioning that LinkedList also implements the Deque interface – supporting efficient access to both ends of the collection.
此外，它还可用于重读场景，在大多数情况下，我们需要第一个或最后一个元素。值得一提的是，LinkedList 还实现了Deque接口–支持对集合两端的有效访问。
Generally, if we know their implementation differences, then we could easily choose one for a particular use-case.
一般来说，如果我们知道它们的实现差异，那么我们就可以很容易地为一个特定的用例选择一个。
For instance, let’s say that we’re going store a lot of time-series events in a list-like data structure. We know that we would receive bursts of events each second.
例如，假设我们要在一个类似列表的数据结构中存储大量的时间序列事件。我们知道，我们每秒都会收到突发的事件。
Also, we need to examine all events one after another periodically and provide some stats. For this use-case, LinkedList is a better choice because the addition rate is much higher than the read rate.
另外，我们需要定期地一个接一个地检查所有的事件，并提供一些统计信息。对于这个用例，LinkedList是一个更好的选择，因为添加率要比读取率高很多。
Also, we would read all the items, so we can’t beat the O(n) upper bound.
另外，我们会读取所有的项目，所以我们无法战胜O(n) 上界。
4. Conclusion
4.总结
In this tutorial, first, we took a dive into how ArrayList and LinkLists are implemented in Java.
在本教程中，首先，我们深入了解了ArrayList和LinkLists是如何在Java中实现的。
We also evaluated different use-cases for each one of these.
我们还评估了其中每一项的不同使用情况。