ArrayList与LinkedList

ArrayList底层数据结构为名为elementData的Object数组,它实现了List接口,
继承了 实现了List接口 的抽象类 AbstractList,
实现了RandomAccess:支持快速随机访问,根据下标获取元素。
Cloneable:可以使用Object.Clone方法。
Serializable:可以进行序列化和反序列化。

1.ArrayList默认长度为10,最大长度为 Integer.MAX_VALUE – 8。

//==============================
2.ArrayList有三种构造方法,一个无参和两个有参,无参构造方法在调用时并不会设置容量为10,而是在有add操作时才会设置容量。有参方法,一个是指定容量大小的,一个是传入 Collection<? extend E> c ,第一步elementData获得c的地址,第二步判断elementData的长度,如果大于0,构造方法会将其用Arrays.copyof(目标数组,被返回副本的长度,被返回副本的类型)深拷贝存进elementData,如果等于0,则elementData将成为默认的容量为0的数组。

//==============================
3.扩容为1.5倍扩容,维护一个minarray_size和一个maxarray_size,每次有add相关的操作时,minarray_size都会被设置为当前ArrayList.size()+1,当minarray_size大于容量时会通过grow()方法进行扩容,当需要的最小容量大于了 Integer.MAX_VALUE – 8,那么ArrayList的容量将被直接设置为Integer.MAX_VALUE。

//==============================
4.add或remove时都是基于下标操作的,每次改动ArrayList时,都会调用***System.copy(原数组,起始位置,新数组,起始位置,操作元素个数)***方法,将需要移动位置的所有元素进行移位操作,并且使size加或减,再使结构改动计数modCount增加。
//==============================
5.list1.retainAll(Collection<?> c),list1.retainAll(list.2),从List1中删除不在list2/不是c的元素。
//==============================
6.进行删除替换操作的时候,方法是有返回值的,返回值为被删除/替换的元素。
//==============================
7.因为arrayList实现了RandomAccess,根据下标访问,所以遍历时尽量用for循环。
//==============================
8.clear方法是for循环从前往后遍历所有元素,将它们全置为null,并且设置size=0。

//======================================
//======================================
//======================================
***LinkedList***底层为一个双向链表,

实现了List接口可以有队列的操作,
实现了Deque接口有双端队列操作,
实现了Cloneable可用Object.clone(),
实现了Serializable可以进行序列化和反序列化。

1.插入替换删除都要用到LinkedList的查找方法node(int index),node方法有个折半查询的优化,index小于当前链表中元素的一半,就从前往后遍历,否则就从后往前。

2.增删查改在源码中除了默认的尾插、getFirst、getLast、remove(Object o)之外,其他情况均是要用到索引 index 的。

3.增删的操作都是双向的,需要改变前后节点的关系,所以每次都得有引用来记录目标节点前后节点。每次结构性改动,都会使结构改动计数modCount增加。

3.LinkedList的toArray()方法是新建一个大小为链表size的Object[]。

4.clear方法是从前往后遍历,将每一个节点的前后引用和元素都置为null,使size=0。

5.进行删除替换操作的时候,方法是有返回值的,返回值为被删除/替换的元素。

//===============================================================================================

总结其区别就是,ArrayList底层是数组,LinkedList是双向链表,改查操作ArrayList更快(RandomAccess优势),增删操作LinkedList更快(Deque优势)。

本文地址:https://blog.csdn.net/rushrush1/article/details/107691536

(0)
上一篇 2022年3月21日
下一篇 2022年3月21日

相关推荐