对比被选中的孩子们ArrayList、LinkedList、Vector

1. List概述

List是一个有序的元素序列。当我们谈论List时,最好将它与Set进行比较,Set是一组唯一且无序的元素。以下是Collection的类层次结构图。从层次结构图中,可以大致了解Java集合。

java-collection-hierarchy.jpeg

2. ArrayList vs. LinkedList vs. Vector

从层次结构图中,它们都实现了 List 接口。它们与使用非常相似。它们的主要区别在于它们的实现,这导致不同操作的不同性能。

数组列表实现为可调整大小的数组。随着向ArrayList添加更多元素,其大小会动态增加。可以使用get和set方法直接访问它的元素,因为ArrayList本质上是一个数组。

Vector 与ArrayList类似,但它是同步的。

如果您的程序是线程安全的,则ArrayList是更好的选择。随着更多元素的添加,Vector和ArrayList需要更多空间。Vector每次将其数组大小加倍,而ArrayList每次增加其大小的50%。然而,LinkedList也实现了Queue, 添加比ArrayList和Vector多了一些方法的接口,例如offer(),peek(),poll()等。

注意:ArrayList的默认初始容量非常小。构造具有更高初始容量的ArrayList是一个好习惯。这可以避免调整大小的成本。



3. ArrayList示例


 

4. LinkedList示例


 

如上面的例子所示,它们与使用类似。真正的区别在于它们的底层实现和它们的操作复杂性。



 

5. Vector

Vector几乎与ArrayList相同,不同之处在于Vector是同步的。因此,它的开销比ArrayList高。通常,大多数Java程序员使用ArrayList而不是Vector,因为它们可以自己显式同步。

6.  ArrayList与LinkedList的性能

时间复杂度比较如下:
arraylist-vs-linkedlist-complexity.png

1 代表时间快  n 代表时间慢

  • ArrayList对于任意添加/删除索引具有O(n)时间复杂度,但对于列表末尾的操作具有O(1)时间复杂度。
  • LinkedList对于任意添加/删除索引具有O(n)时间复杂度,但对于List的结尾/开始处的操作具有O(1)。

我使用以下代码来测试它们的性能:


 

输出是:(毫秒)

arraylist-vs-linkedlist1.png

总结

他们的表现差异很明显。LinkedList在添加和删除方面更快,但在get中更慢。根据复杂性表和测试结果,我们根据使用场景灵活选择使用ArrayList或LinkedList。简而言之,没有大量的随机访问,但有大量的添加删除操作那么 首选

LinkedList !