ArrayList和LinkedList的区别、优缺点以及应用场景

ArrayList和LinkedList的区别、优缺点以及应用场景

Scroll Down

ArrayList和LinkedList都是实现了List接口的容器类,用于存储一系列的对象引用。他们都可以对元素的增删改查进行操作,那么他们的区别、优缺点应用场景都有哪些呢?我们通过源码和数据结构来说明一下

ArrayList和LinkedList的大致区别如下:

  1. ArrayList是实现了基于动态数组的数据结构,LinkedList是基于链表结构。
  2. 对于随机访问的get和set方法,ArrayList要优于LinkedList,因为LinkedList要移动指针。
  3. 对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。

具体说明

ArrayList源码:

ArrayList和LinkedList1.png

在源码中课看到,ArrayList是实现了基于动态数组的数据结构,而数组是一段连续的内存空间,在内存中我们可以简单表示为下图样式

ArrayList和LinkedList2.png

因为数组在存储数据时是按顺序存储的,存储数据的内存也是连续的,所以他的特点就是寻址读取数据比较容易,插入和删除比较困难。简单解释一下为什么,在读取数据时,只需要告诉数组要从哪个位置(索引)取数据就可以了,数组会直接把你想要的位置的数据取出来给你。插入和删除比较困难是因为这些存储数据的内存是连续的,要插入和删除就需要变更整个数组中的数据的位置。举个例子:一个数组中编号0->1->2->3->4这五个内存地址中都存了数组的数据,但现在你需要往4中插入一个数据,那就代表着从4开始,后面的所有内存中的数据都要往后移一个位置,这可是很耗时的。所以,对于ArrayList,它在集合的末尾删除或添加元素所用的时间是一致的,但是在列表中间的部分添加或删除时所用时间就会大大增加。但是它在根据索引查找元素的时候速度很快。

LinkedList部分说明:

LinkedList底层是双向列表

// 双向链表的节点所对应的数据结构。
// 包含3部分:上一节点,下一节点,当前节点值。
     private static class Entry<E> {
         // 当前节点所包含的值
         E element;
         // 下一个节点
         Entry<E> next;
         // 上一个节点
         Entry<E> previous;
 
         /**
          * 链表节点的构造函数。
          * 参数说明:
          *   element  —— 节点所包含的数据
          *   next      —— 下一个节点
          *   previous —— 上一个节点
          */
         Entry(E element, Entry<E> next, Entry<E> previous) {
             this.element = element;
             this.next = next;
             this.previous = previous;
         }
     }

当需要在首位置插入元素时,first引用指向需要插入到链表中的节点对象,新的节点对象的next引用指向原先的首节点对象;

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

ArrayList和LinkedList的缺点如下:

  1. 对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象。
  2. 在ArrayList集合中添加或者删除一个元素时,当前的列表移动元素后面所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
  3. LinkedList集合不支持高效的随机访问(RandomAccess),因为可能产生二次项的行为。
  4. ArrayList的空间浪费主要体现在List列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

ArrayList和LinkedList的应用场景如下:

ArrayList使用在查询比较多,但是插入和删除比较少的情况,而LinkedList用在查询比较少而插入删除比较多的情况