何时在Java中使用LinkedList而不是ArrayList？

作为一个在大规模SOA Web服务上进行操作性能工程大约十年的人,我更喜欢LinkedList相对于ArrayList的行为.虽然LinkedList的稳态吞吐量更差,因此可能会导致购买更多硬件 - ArrayList在压力下的行为可能导致集群中的应用程序在近乎同步的情况下扩展其阵列,并且对于大型阵列可能导致缺乏响应性在应用程序和停电,而在压力下,这是灾难性的行为.

同样,您可以从默认的吞吐量终身垃圾收集器中获得更好的应用程序吞吐量,但是一旦获得具有10GB堆的Java应用程序,您可以在完整的GC期间锁定应用程序25秒,这会导致SOA应用程序超时和失败如果太频繁发生,你的SLA就会受到影响.即使CMS收集器占用更多资源并且无法实现相同的原始吞吐量,但它是一个更好的选择,因为它具有更可预测和更小的延迟.

如果性能的全部意思是吞吐量而您可以忽略延迟,那么ArrayList只是性能的更好选择.根据我的工作经验,我不能忽视最坏情况的延迟.

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

算法:Big-Oh表示法

ArrayLists适用于一次性写入多次读取或appender,但在前面或中间添加/删除时效果不佳.

是的,我知道,这是一个古老的问题,但我会投入两分钱:

在性能方面,LinkedList 几乎总是错误的选择.有一些非常具体的算法需要一个LinkedList,但那些非常非常罕见,并且算法通常特别依赖于LinkedList能够相对快速地插入和删除列表中间的元素,一旦你在那里导航使用ListIterator.

有一个常见的用例,其中LinkedList优于ArrayList:队列的那个.但是,如果您的目标是性能,而不是LinkedList,您还应该考虑使用ArrayBlockingQueue(如果您可以提前确定队列大小的上限,并且可以预先分配所有内存),或者此CircularArrayList实现.(是的,它是从2001年开始的,所以你需要对它进行一般化,但我的性能比率与刚刚在最近的JVM中引用的内容相当)

这是一个效率问题.LinkedList添加和删​​除元素的速度很快,但访问特定元素的速度很慢.ArrayList访问特定元素的速度很快,但添加到任何一端都很慢,特别是在中间删除速度很慢.

Array和ArrayList vs LinkedList vs Vector的内容更加深入, Linked List也是如此.

正确或不正确:请在本地执行测试并自行决定!

编辑/删除速度LinkedList比ArrayList.

ArrayListArray在大批量应用中,需要大小翻倍的后备版本更糟糕.

下面是每个操作的单位测试结果.时间以纳秒为单位.

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

这是代码:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);
        List arrayList = new ArrayList(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);

        watch.start();
        List linkedList = new LinkedList();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List arrayList = new ArrayList(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List linkedList = new LinkedList();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);
        List arrayList = new ArrayList(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);
        List linkedList = new LinkedList();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);
        List arrayList = new ArrayList(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List linkedList = new LinkedList();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List stringList = Arrays.asList(strings);
        List arrayList = new ArrayList(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List linkedList = new LinkedList();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

ArrayList本质上是一个数组.LinkedList实现为双链表.

该get是相当清楚的.O(1)for ArrayList,因为ArrayList允许使用索引进行随机访问.O(n)for LinkedList,因为它需要先找到索引.注意:有不同版本的add和remove.

LinkedList添加和删​​除速度更快,但获取速度更慢.简而言之,LinkedList如果:

没有大量的随机访问元素

有大量的添加/删除操作

=== ArrayList ===

添加(E e)

在ArrayList的末尾添加

需要内存调整成本.

O(n)最差,O(1)摊销

add(int index,E element)

添加到特定的索引位置

需要转移和可能的内存调整成本

上)

remove(int index)

删除指定的元素

需要转移和可能的内存调整成本

上)

删除(对象o)

从此列表中删除指定元素的第一个匹配项

需要首先搜索元素,然后转移和可能的内存调整大小成本

上)

=== LinkedList ===

添加(E e)

添加到列表的末尾

O(1)

add(int index,E element)

插入指定位置

需要先找到位置

上)

去掉()

删除列表的第一个元素

O(1)

remove(int index)

删除具有指定索引的元素

需要先找到元素

上)

删除(对象o)

删除指定元素的第一个匹配项

需要先找到元素

上)

这是programcreek.com中的一个图(add并且remove是第一个类型,即在列表末尾添加一个元素并删除列表中指定位置的元素.):

LinkedList的作者Joshua Bloch:

有没有人真正使用LinkedList？我写了它,我从来没用过它.

链接:https://twitter.com/joshbloch/status/583813919019573248

我很抱歉答案不像其他答案那样提供信息,但我认为这将是最有趣和不言自明的.

ArrayList随机访问,而LinkedList扩展和删除元素真的很便宜.对于大多数情况,ArrayList很好.

除非您创建了大型列表并测量了瓶颈,否则您可能永远不必担心差异.

如果你的代码有add(0)和remove(0),使用a LinkedList和它更漂亮addFirst()和removeFirst()方法.否则,请使用ArrayList.

当然,番石榴的ImmutableList是你最好的朋友.

TL;由于现代计算机体系结构的DR,ArrayList对于几乎任何可能的用例都将显着提高效率 - 因此LinkedList除了一些非常独特和极端的情况之外应该避免.

理论上,LinkedList有一个O(1) add(E element)

在列表中间添加元素应该非常有效.

实践是非常不同的,因为LinkedList是Cache Hostile Data结构.从性能POV - 很少有LinkedList可能比Cache友好的 表现更好的情况ArrayList.

以下是在随机位置插入元素的基准测试结果.正如您所看到的 - 数组列表如果效率更高,尽管理论上列表中间的每个插入都需要"移动" 数组中较晚的n个元素(较低的值更好):

使用更新一代的硬件(更大,更高效的缓存) - 结果更具决定性:

LinkedList需要更多时间来完成相同的工作.源 代码

这有两个主要原因:

主要是 - 节点的节点LinkedList随机分散在内存中.RAM("随机存取存储器")实际上并不是随机的,需要将存储器块提取到缓存.此操作需要时间,并且当此类提取频繁发生时 - 缓存中的内存页面需要一直更换 - >缓存未命中 - >缓存效率不高. ArrayList元素存储在连续内存中 - 这正是现代CPU架构所优化的内容.

LinkedList保持后退/前进指针所需的辅助,这意味着与存储的每个值相比,存储器消耗的3倍ArrayList.

DynamicIntArray,btw,是一个自定义的ArrayList实现,保存Int(基本类型)而不是对象 - 因此所有数据实际上都是相邻存储的 - 因此效率更高.

要记住的关键要素是获取内存块的成本比访问单个内存单元的成本更重要.这就是为什么读取器1MB的顺序存储器比从不同的存储器块读取这些数据量快x400倍的原因:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

来源:每个程序员都应该知道的延迟数

为了更清楚地说明这一点,请检查在列表开头添加元素的基准.这是一个用例,从理论上讲,它LinkedList应该真正发光,并且ArrayList应该会出现糟糕甚至更糟糕的结果:

注意:这是C++ Std lib的基准测试,但我之前的经验表明C++和Java结果非常相似.源代码

复制顺序大量内存是由现代CPU优化的操作 - 改变理论并实际制作,再次ArrayList/ Vector更高效

致谢:此处发布的所有基准测试均由KjellHedström创建.他的博客上可以找到更多数据

我知道这是一个老帖子,但老实说,我不敢相信没人提到这个LinkedList工具Deque.只需看看Deque(和Queue)中的方法; 如果你想要一个公平的比较,尝试运行LinkedList反对ArrayDeque,做一个功能的功能比较.

这是在两个大O符号ArrayList和LinkedList也CopyOnWrite-ArrayList:

数组列表

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

链表

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

写入时复制-的ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

基于这些,你必须决定选择什么.:)

让我们比较下面的参数LinkedList和ArrayList:

1.实施

ArrayList是列表接口的可调整大小的数组实现,而

LinkedList是列表界面的双向链表实现.

2.表现

get(int index)或搜索操作

ArrayList get(int index)操作以恒定时间运行,即O(1)while

LinkedList get(int index)操作运行时间为O(n).

ArrayList比LinkedList更快的原因是ArrayList使用基于索引的系统作为其元素,因为它在内部使用数组数据结构,另一方面,

LinkedList不为其元素提供基于索引的访问,因为它从开头或结尾(以较近者为准)进行迭代,以检索指定元素索引处的节点.

insert()或add(Object)操作

与ArrayList相比,LinkedList中的插入通常很快.在LinkedList中添加或插入是O(1)操作.

在ArrayList中,如果数组是完整的,即最坏的情况,则需要额外调整数组大小和将元素复制到新数组的成本,这使得在ArrayList O(n)中添加运算的运行时,否则它是O(1) .

remove(int)操作

LinkedList中的删除操作通常与ArrayList相同,即O(n).

在LinkedList中,有两个重载的删除方法.一个是remove(),没有任何参数删除列表的头部并在恒定时间O(1)中运行.LinkedList中另一个重载的remove方法是remove(int)或remove(Object),它删除作为参数传递的Object或int.此方法遍历LinkedList,直到找到Object并将其与原始列表取消链接.因此,此方法运行时为O(n).

在ArrayList中, remove(int)方法涉及将元素从旧数组复制到新更新的数组,因此其运行时为O(n).

3.反向迭代器

LinkedList可以使用descendingIterator()while在反向迭代

ArrayList中没有descendingIterator(),所以我们需要编写自己的代码来反向迭代ArrayList.

4.初始容量

如果构造函数没有重载,则ArrayList会创建一个初始容量为10的空列表

LinkedList 仅构造没有任何初始容量的空列表.

5.内存开销

与ArrayList相比,LinkedList中的内存开销更多,因为LinkedList中的节点需要维护下一个节点和上一个节点的地址.而

在ArrayList中, 每个索引只保存实际对象(数据).

资源

基于我在特定列表上执行的操作的时间复杂性,我通常使用一个.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

除了上面的其他好的参数,你应该注意ArrayListimplements RandomAccess接口,而LinkedList实现Queue.

因此,它们以某种方式解决了稍微不同的问题,效率和行为的差异(参见他们的方法列表).

这取决于你将在List上做更多的操作.

ArrayList访问索引值的速度更快.插入或删除对象时要糟糕得多.

要了解更多信息,请阅读任何讨论数组和链接列表之间差异的文章.

请参阅Java教程 - 列表实现.

数组列表本质上是一个数组,其中包含添加项等的方法(您应该使用通用列表).它是可以通过索引器访问的项目集合(例如[0]).它意味着从一个项目到下一个项目的进展.

链表指定从一个项目到下一个项目的进展(项目a - >项目b).您可以使用数组列表获得相同的效果,但链接列表绝对说明了应该跟随前一个项目的项目.

链表的一个重要特征(我在另一个答案中没有读到)是两个列表的串联.对于数组,这是O(n)(一些重新分配的开销),链接列表只有O(1)或O(2);-)

重要:对于Java来说,LinkedList这不是真的!请参阅Java中的链表是否有快速连接方法？

我已经阅读了响应,但有一种情况我总是在ArrayList上使用LinkedList,我想分享以听取意见:

每次我有一个返回从DB获得的数据列表的方法时,我总是使用LinkedList.

我的理由是因为不可能确切地知道我得到了多少结果,所以不会浪费内存(如在ArrayList中容量和实际元素数量之间的差异),并且没有浪费时间去尝试复制容量.

至于ArrayList,我同意至少你应该总是使用具有初始容量的构造函数,以尽可能地减少数组的重复.

ArrayList和LinkedList各有利弊.

与使用指向下一个节点的指针的LinkedList相比,ArrayList使用连续的内存地址.因此,当您想要查找ArrayList中的元素比使用LinkedList进行n次迭代更快时.

另一方面,LinkedList中的插入和删除更容易,因为您只需更改指针,而ArrayList意味着使用shift操作进行任何插入或删除.

如果您的应用程序中有频繁的检索操作,请使用ArrayList.如果频繁插入和删除,请使用LinkedList.

ArrayList中的操作get(i)比LinkedList快,因为:
ArrayList: List接口的Resizable-array实现
LinkedList: List和Deque接口的双链表实现

索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准.

ArrayList和LinkedList这两个工具List interface 和他们的方法和结果几乎是相同的.然而,它们之间几乎没有差异,这取决于要求,使一个优于另一个.

ArrayList与LinkedList

1)与Search: ArrayList搜索操作相比,LinkedList搜索操作非常快.get(int index)in ArrayList赋予性能O(1)同时LinkedList表现O(n).

Reason: ArrayList维护其元素的基于索引的系统,因为它隐式使用数组数据结构,这使得搜索列表中的元素更快.另一方面LinkedList实现双向链表,这需要遍历所有元素以搜索元素.

2)Deletion: LinkedList删除操作提供O(1)性能同时ArrayList提供可变性能:O(n)在最坏的情况下(在删除第一个元素时)和O(1)最好的情况下(删除最后一个元素时).

结论:与ArrayList相比,LinkedList元素删除更快.

原因:LinkedList的每个元素都维护着两个指针(地址),这些指针指向列表中的两个邻居元素.因此,移除仅需要改变将要移除的节点的两个相邻节点(元素)中的指针位置.在In ArrayList中,需要移动所有元素以填充由remove元素创建的空间.

3)Inserts Performance: LinkedList添加方法给出O(1)的性能,同时ArrayList使O(n)在最坏的情况.原因与删除说明相同.

4)Memory Overhead: ArrayList维护索引和元素数据,同时LinkedList维护元素数据和邻居节点的两个指针

因此,LinkedList中的内存消耗相对较高.

这些类之间几乎没有相似之处,如下所示:

ArrayList和LinkedList都是List接口的实现.

它们都维护元素的插入顺序,这意味着在显示ArrayList和LinkedList元素时,结果集将具有将元素插入List的相同顺序.

这两个类都是非同步的,可以使用Collections.synchronizedList方法显式同步.

在iterator与listIterator返回的这些类fail-fast(如果名单在任何时间从结构上修改创建迭代器之后,以任何方式,除了通过iterator’s自身的remove或add方法,迭代器都将throw一ConcurrentModificationException).

何时使用LinkedList以及何时使用ArrayList？

由于插入上述解释和删除操作提供良好的性能(O(1))在LinkedList相比ArrayList(O(n)).

因此,如果在应用程序中需要频繁添加和删除,则LinkedList是最佳选择.

Search(get method)操作很快Arraylist (O(1))但不在LinkedList (O(n))

因此,如果添加和删除操作较少以及搜索操作要求较多,则ArrayList将是您最好的选择.

1）基础数据结构

ArrayList和LinkedList之间的第一个区别在于，ArrayList由Array支持，而LinkedList由LinkedList支持。这将导致性能上的进一步差异。

2）LinkedList实现双端队列

ArrayList和LinkedList之间的另一个区别是，除了List接口之外，LinkedList还实现了Deque接口，该接口为add（）和poll（）以及其他几个Deque函数提供了先进先出操作。3）在ArrayList中添加元素如果不触发Array的大小调整，则在ArrayList中添加元素是O（1）操作，在这种情况下，它变为O（log（n）），另一方面，在LinkedList是O（1）操作，因为它不需要任何导航。

4）从某个位置移除元素

为了从特定索引中删除元素（例如，通过调用remove（index）），ArrayList执行复制操作，使其接近O（n），而LinkedList需要遍历该点，这也使其变为O（n / 2） ，因为它可以根据接近度从任一方向来回移动。

5）遍历ArrayList或LinkedList

迭代是LinkedList和ArrayList的O（n）操作，其中n是元素的数量。

6）从位置检索元素

get（index）操作在ArrayList中为O（1），而在LinkedList中为O（n / 2），因为它需要遍历直到该条目。不过，在Big O表示法中，O（n / 2）只是O（n），因为我们忽略了那里的常数。

7）记忆

LinkedList使用包装对象Entry，这是一个用于存储数据的静态嵌套类，以及下一个和上一个两个节点，而ArrayList仅将数据存储在Array中。

因此，对于ArrayList而言，内存需求似乎比LinkedList少，除了Array在将内容从一个Array复制到另一Array时执行调整大小操作的情况。

如果Array足够大，则此时可能会占用大量内存并触发垃圾回收，这会减慢响应时间。

从ArrayList与LinkedList之间的所有上述差异来看，在几乎所有情况下，ArrayList都是比LinkedList更好的选择，除非您经常执行add（）操作而不是remove（）或get（）。

与ArrayList相比，修改链接列表要容易得多，尤其是在从开始或结束添加或删除元素的情况下，因为链接列表在内部保留了这些位置的引用，并且可以在O（1）时间内访问它们。

换句话说，您无需遍历链表即可到达要添加元素的位置，在这种情况下，加法变为O（n）操作。例如，在链接列表的中间插入或删除元素。

我认为，将ArrayList而不是LinkedList用作Java中的大多数实际用途。