ArrayList和LinkedList的区别

ArrayList和LinkedList的区别

ArrayList和linkedList的异同

• 一、ArrayList和linkedList的相同点
• 二、ArrayList和linkedList的区别
• • 1、数据及内部结构
  • • （1）ArrayList是基于(Array)动态数组的数据结构
    • （2）linkedList是基于(link)链表的结构
  • 2、扩容问题
  • • （1）ArrayList以数组复制的形式进行步长是0.5倍原容量的扩容
    • （2）不存在扩容问题
  • 3、线程安全问题
  • • （1）ArrayList是线程不安全的
    • （2）linkedList是线程安全的
  • 4、随机访问和增删的 *** 作效率不同
  • • （1）随机访问时，优先选择ArrayList数据结构
    • （2）增删 *** 作时，优先选择linkedList链表结构
  • 5、根据索引查找元素的速度不同
  • • （1）ArrayList根据索引查找元素时速度很快
    • （2）linkedList根据索引查找元素时速度较慢
  • 6、控件开销不同
  • • （1）ArrayList需要预留一定空间
    • （2）linkList需要存储节点信息以及节点指针
  • 7、推荐使用
  • • （1）末尾 *** 作+随机访问=ArrayList
    • （2）前面/中间 *** 作+有序访问=linkedList
    • （3）推荐用linkedList来实现队列和栈

一、ArrayList和linkedList的相同点

ArrayList和linkedList都是实现了List接口的容器类，用于存储一系列的对象引用，他们都可以对元素的增删改查进行 *** 作。

ArrayList、linkedList、Vector和Stack是List的四个实现类， List是一个接口，它继承与Collection接口，代表有序的队列。其中Vector是基于JDK1.0，虽然实现了同步，但是效率低，已经不用了，Stack继承与Vector。

二、ArrayList和linkedList的区别 1、数据及内部结构 （1）ArrayList是基于(Array)动态数组的数据结构

ArrayList内部使用数组的形式实现了存储，实现了RandomAccess接口，利用数组的下面进行元素的访问。

（2）linkedList是基于(link)链表的结构

linkedList内部使用双向链表的结构实现存储，linkedList有一个内部类作为存放元素的单元，里面有三个属性，用来存放元素本身以及前后2个单元的引用，另外linkedList内部还有一个header属性，用来标识起始位置，linkedList的第一个单元和最后一个单元都会指向header，因此形成了一个双向的链表结构。

2、扩容问题 （1）ArrayList以数组复制的形式进行步长是0.5倍原容量的扩容

因为是数组，所以ArrayList在初始化的时候，有初始大小10，插入新元素的时候，会判断是否需要扩容，步长是0.5倍原容量扩容的步长是0.5倍原容量，扩容方式是利用数组的复制，因此有一定的开销，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用

（2）不存在扩容问题

linkedList的方法和使用和ArrayList大致相同，由于linkedList是链表实现的，所以额外提供了在头部和尾部添加/删除元素的方法，也就没有扩容的问题了。 linkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用

3、线程安全问题 （1）ArrayList是线程不安全的

ArrayList是线程不安全的，性能相对较好。

（2）linkedList是线程安全的

linkedList是线程安全的，性能相对较低。

线程安全就是当某个线程访问某个资源，会将这个资源锁住，不允许其它线程访问。而线程不安全的时候就是每个线程都随意访问资源，不做处理，相对线程安全做的工作就少了，效率自然高些，但线程不安全就有可能导致多个线程访问同一个数据，这个数据可能出现错误。

4、随机访问和增删的 *** 作效率不同 （1）随机访问时，优先选择ArrayList数据结构

当随机访问List（get和set *** 作）时，ArrayList比linkedList的效率更高，因为linkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。故linkedList不支持高效的随机元素访问。

（2）增删 *** 作时，优先选择linkedList链表结构

当对数据进行增加和删除的 *** 作(add和remove *** 作)时，linkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删 *** 作时，会对 *** 作点之后所有数据的下标索引造成影响，需要进行数据的移动。

5、根据索引查找元素的速度不同 （1）ArrayList根据索引查找元素时速度很快

对于ArrayList，它在集合的末尾删除或添加元素所用的时间是一致的，但是在列表中间的部分添加或删除时所用时间就会大大增加。但是它在根据索引查找元素的时候速度很快。

（2）linkedList根据索引查找元素时速度较慢

对于linkedList则相反，它在插入、删除集合中任何位置的元素所花费的时间都是一样的，但是它根据索引查询一个元素的时候却比较慢。

6、控件开销不同 （1）ArrayList需要预留一定空间

ArrayList主要控件开销在于需要在List列表预留一定空间，容易造成空间浪费。在列表末尾增加一个元素所花的开销都是固定的，在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动，偶尔可能会导致对数组重新进行分配；

（2）linkList需要存储节点信息以及节点指针

linkList主要控件开销在于需要存储节点信息以及节点指针，空间花费较大，但集合中无论在哪个位置添加或者删除一个元素的开销都是固定的，它的每一个元素都需要消耗相当的空间

7、推荐使用 （1）末尾 *** 作+随机访问=ArrayList

当 *** 作是在一列数据的末尾添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能

（2）前面/中间 *** 作+有序访问=linkedList

当你的 *** 作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用linkedList了。

（3）推荐用linkedList来实现队列和栈

ArrayList和linkedList都可以实现栈、队列等数据结构，但linkedList本身实现了队列的接口，所以更推荐用linkedList来实现队列和栈。