linkedlist区别 - java linkedlist arraylist




何时在Java中使用LinkedList over ArrayList? (20)

我一直只是一个人使用:

List<String> names = new ArrayList<>();

我使用接口作为可移植性的类型名称,因此当我问这些问题时,我可以重新编写代码。

何时应该使用LinkedList而不是ArrayList ,反之亦然?


1) 搜索:与LinkedList搜索操作相比,ArrayList搜索操作非常快。 ArrayList中的get(int index)给出O(1)的性能,而LinkedList性能为O(n)。

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

2)删除: LinkedList删除操作给出O(1)性能,而ArrayList给出可变性能:在最坏情况下(在删除第一个元素时为O(n))和在最佳情况下为O(1)(在删除最后一个元素时) 。

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

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

3)插入性能: LinkedList add方法给出O(1)性能,而ArrayList在最坏情况下给出O(n)。原因与删除时解释的相同。

4)内存开销: ArrayList维护索引和元素数据,而LinkedList维护元素数据和相邻节点的两个指针,因此LinkedList中的内存消耗相对较高。

一些相似之处这些类,内容如下之间:

ArrayList和LinkedList都是List接口的实现。它们都维护元素的插入顺序,这意味着在显示ArrayList和LinkedList元素时,结果集将具有将元素插入List的相同顺序。这两个类都是非同步的,可以使用Collections.synchronizedList方法显式同步。这些类返回的iterator和listIterator是快速失​​败的(如果在创建迭代器之后的任何时候对列表进行结构修改,除了通过迭代器自己的remove或add方法之外,迭代器将抛出ConcurrentModificationException)。

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

1)如上所述,与ArrayList(O(n))相比,insertList和remove操作在LinkedList中提供了良好的性能(O(1))。因此,如果在应用程序中需要频繁添加和删除,则LinkedList是最佳选择。

2)搜索(get方法)操作在ArrayList(O(1))中快速但在LinkedList(O(n))中没有,因此如果添加和删除操作较少且搜索操作要求较多,则ArrayList将是您最好的选择。


ArrayList就是你想要的。 LinkedList几乎总是(性能)错误。

为什么LinkedList糟糕:

  • 它使用大量小内存对象,因此会影响整个过程的性能。
  • 很多小对象都不利于缓存局部性。
  • 任何索引操作都需要遍历,即具有O(n)性能。 这在源代码中并不明显,导致算法O(n)比使用ArrayList时慢。
  • 获得良好的表现很棘手。
  • 即使big-O性能与ArrayList相同,它也可能会明显变慢。
  • 在源代码中看到LinkedList是很不耐烦的,因为它可能是错误的选择。

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

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


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

get很清楚。 对于ArrayList ,O(1),因为ArrayList允许使用索引进行随机访问。 对于LinkedList ,O(n),因为它需要首先找到索引。 注意:有不同版本的addremove

LinkedList在添加和删除方面更快,但在get中更慢。 简而言之,如果出现以下情况,应首选LinkedList

  1. 没有大量的随机访问元素
  2. 有大量的添加/删除操作

=== 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的图( addremove是第一种类型,即在列表末尾添加元素并删除列表中指定位置的元素。):


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

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

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

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

以下是在随机位置插入元素的基准测试结果。正如你所看到的-数组列表中,如果有效得多,虽然理论上在列表的中间每个插入都需要“移动” ñ后的数组中的元素(值越低越好):

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

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

这有两个主要原因:

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

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

DynamicIntArray,顺便说一句,是一个自定义的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创建。他的博客上可以找到更多数据


摘要 ArrayListArrayDeque在更多用例中比LinkedList更可取。 如果您不确定 - 只需从ArrayList开始。

LinkedListArrayList是List接口的两种不同实现。 LinkedList使用双向LinkedList实现它。 ArrayList使用动态重新调整大小的数组来实现它。

与标准链表和数组操作一样,各种方法将具有不同的算法运行时。

对于LinkedList<E>

  • get(int index)O(n) (平均n / 4步)
  • add(E element)O(1)
  • add(int index, E element)O(n) (平均n / 4步),但当index = 0O(1) <--- LinkedList<E>主要好处LinkedList<E>
  • remove(int index)O(n) (平均n / 4步)
  • Iterator.remove()O(1) 。 <--- LinkedList<E>主要好处
  • ListIterator.add(E element)O(1)这是LinkedList<E>的主要优点之一

注意:许多操作平均需要n / 4步,最佳情况下需要恒定步数(例如索引= 0),最坏情况下需要n / 2步(列表中间)

对于ArrayList<E>

  • get(int index)O(1) <--- ArrayList<E>主要好处
  • add(E element)O(1)摊销,但是O(n)最坏情况,因为必须调整和复制数组
  • add(int index, E element)O(n) (平均n / 2步)
  • remove(int index)O(n) (平均n / 2步)
  • Iterator.remove()O(n) (平均n / 2步)
  • ListIterator.add(E element)O(n) (平均n / 2步)

注意:许多操作平均需要n / 2步,最好的情况下是常数步(列表末尾),最坏情况下是n步(列表开头)

LinkedList<E>允许使用迭代器进行常量时间插入或删除,但只允许顺序访问元素。 换句话说,您可以向前或向后遍历列表,但在列表中查找位置需要的时间与列表的大小成比例。 Javadoc说“索引到列表中的操作将从开头或结尾遍历列表,以较近者为准” ,因此这些方法平均为O(n)n / 4步),但index = 0 O(1) index = 0

另一方面, ArrayList<E>允许快速随机读取访问,因此您可以在恒定时间内获取任何元素。 但是,除了末端之外的任何地方添加或移除都需要将所有后面的元素移位,以便打开或填补空白。 此外,如果添加的元素多于底层数组的容量,则会分配一个新数组(大小的1.5倍),并将旧数组复制到新数组,因此添加到ArrayListO(n)最坏的情况,但平均不变。

因此,根据您打算执行的操作,您应该相应地选择实现。 迭代任何一种List实际上同样便宜。 (迭代一个ArrayList在技​​术上更快,但除非你做的事情对性能非常敏感,否则你不应该担心这一点 - 它们都是常量。)

当您重用现有迭代器来插入和删除元素时,会出现使用LinkedList的主要好处。 然后,可以通过仅在本地更改列表,在O(1)中完成这些操作。 在数组列表中,需要移动 (即复制)数组的其余部分。 另一方面,在LinkedList意味着在最坏情况下遵循O(n)n / 2步)中的链接,而在ArrayList ,可以在数学上计算所需位置并在O(1)中访问。

当您从列表的头部添加或删除时,会出现使用LinkedList另一个好处,因为这些操作是O(1) ,而它们是ArrayList O(n) 。 请注意, ArrayDeque可能是LinkedList一个很好的替代品,用于添加和删除头部,但它不是List

此外,如果您有大型列表,请记住内存使用情况也不同。 LinkedList每个元素都有更多的开销,因为还存储了指向下一个和前一个元素的指针。 ArrayLists没有这种开销。 但是,无论是否实际添加了元素, ArrayLists都会占用为容量分配的内存。

ArrayList的默认初始容量非常小(Java 1.4中的10个 - 1.8)。 但由于底层实现是一个数组,因此如果添加大量元素,则必须调整数组大小。 当您知道要添加大量元素时,为了避免调整大小的高成本,请构造具有更高初始容量的ArrayList



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

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

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


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

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

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

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


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

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

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


让我们比较下面的参数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中,每个索引只保存实际对象(数据)。

Source


这取决于您将在列表上执行哪些操作。

ArrayList更快地访问索引值。插入或删除对象时要糟糕得多。

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


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

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


ArrayList扩展了AbstractList并实现了List接口。ArrayList是动态数组。
可以说它基本上是为了克服数组的缺点而创建

的.LinkedList类扩展了AbstractSequentialList并实现了List,Deque和Queue接口。
性能
arraylist.get()是O(1)而linkedlist.get()O(n)
arraylist.add()是O(1)并且linkedlist.add()0(1)
arraylist.contains()是O(n)并且linkedlist.contains()O(n)
arraylist.next()是O(1)并且linkedlist.next()O(1)
arraylist.remove()是O(n)而linkedlist.remove()是O(1)
在arraylist中
iterator.remove()是O(n)
而在链表中
iterator.remove()是O(1)


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

当然,GuavaImmutableList是你最好的朋友。


我在这里看到的其中一项测试只进行了一次测试。但我注意到你需要多次运行这些测试,最终它们的时间会收敛。基本上JVM需要预热。对于我的特定用例,我需要添加/删除项目到最后增加到约500项。在我的测试中LinkedList出现得更快,链接LinkedList大约50,000 NS并且ArrayList大约90,000 NS ...接受或接受。请参阅下面的代码。

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}

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

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



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

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


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

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







linked-list