我们在分析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支持两端元素插入和移除。
原创文章,作者:王先生。,如若转载,请注明出处:https://www.9im.cn/497.html