1. 9IM首页
  2. 热点

ArrayList与LinkedList的区别

我们在分析Java容器之间的区别时,我们也可以从继承树,底层数据结构,线程安全,执行效率来进行分析。

1.底层使用的数据结构

  • Arraylist 底层使用的是Object数组,初始化时就会指向的会是一个static修饰的空数组,数组长度一开始为0,插入第一个元素时数组长度会初始化为10,之后每次数组空间不够进行扩容时都是增加为原来的1.5倍。ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)
  • LinkedList 底层使用的是双向链表数据结构,每个节点保存了指向前驱节点和后继结点的指针。初始化时,不执行任何操作,添加第一个元素时,再去构造链表中的节点。

2.是否保证线程安全:

ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全。

因为ArrayList的插入元素的方法就是裸奔的,直接将原数组index及后面的元素拷贝到index+1及后面的位置上,然后将index位置设置为插入的值,并发修改时保证不了数据安全性,所以也不允许并发修改,一旦检测到并发修改,会抛出ConcurrentModificationException异常。

//ArrayList的插入元素的方法
public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//将原数组index之后的元素拷贝到原数组index+1后面的位置上
        elementData[index] = element;
        size++;
}

3.插入和删除的复杂度:

  • ArrayList 采用数组存储,元素的物理存储地址是连续的,支持以O(1)的时间复杂度对元素快速访问。插入和删除元素后,需要将后面的元素进行移动,所以插入和删除元素的时间复杂度受元素位置的影响。复杂度是 O(n),
  • LinkedList 采用链表存储,所以不能快速随机访问。所以首尾插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)(如果是插入到中间位置还需要考虑寻找插入位置的时间复杂度)。而数组为近似 O(n)。

4.继承树

  • ArrayList继承于AbstractList抽象类,实现了List, RandomAccess, Cloneable, java.io.Serializable接口 。
  • LinkedList继承自AbstractSequentialList 实现List, Deque, Cloneable, java.io.Serializable接口。

AbstractSequentialList是AbstractList类的子类,实现了根据下标来访问元素的一些方法,主要是通过listIterator遍历获取特定元素。

List接口代表的是有序结合,与Set相反,List的元素是按照移动的顺序进行排列。

Cloneable接口代表类会重新父类Object的clone()方法,支持对实例对象的clone操作。

java.io.Serializable接口代表类支持序列化。

RandomAccess是一个标示性接口,代表ArrayList支持快速访问,而LinkedList不支持。

Deque接口是双端队列的意思,代表LinkedList支持两端元素插入和移除。

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/497.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注