Skip to content

Latest commit

 

History

History
 
 

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 

README.md

学习笔记

一、ArrayList学习总结

1. ArrayList大小和容量

如果使用无参构造函数创建ArrayList,大小size和初始容量都是0;

如果使用有参构造函数:当指定初始容量,就按照指定的初始容量;如果没有指定初始容量传递值进去,就根据实际size的大小为初始容量;

在无参构造函数初始化的ArrayList进行第一次add操作时,第一次会最少扩容10,如果第一次add进去的数值size大于10,就按照这个size扩容。

2. ArrayList扩容

当我们使用无参构造函数创建了一个ArrayList时,初始容量为0。当我们add进一个值时,此时的容量为10,size为1。然后接着添加数据时,扩容有两个情况要考虑: 当我们接着add进入10个值时,此时需要扩容,首先根据公式计算1.5倍是15,然后发现15已经可以容纳11个值了,就选择15作为扩容的容量; 当我们接着add进入15个值时,此时需要扩容,首先根据公式计算1.5倍是15,然后发现15无法容纳16个值,就会选择我们期望的容量16作为扩容的容量,这里的判断代码如下:

// newCapacity 本次扩容的大小,minCapacity 我们期望的数组最小大小
// 如果扩容后的值 < 我们的期望值,我们的期望值就等于本次扩容的大小
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

而且需要注意的是,扩容会消耗性能,因为扩容底层使用的是 System.arraycopy 方法,会把原数组的数据全部拷贝到新数组上,所以性能消耗比较严重。

3. ArrayList删除

3.1、为什么普通for循环无法删除干净(漏掉要删除的数据)?

普通for循环调用ArrayList的remove删除数据后,后面的数据会自动向前移。比如一个1,2,3,3,4的ArrayList,我们使用普通for循环,在删除下标为2的元素3后, 原本下标为3、4的元素会前移一位,下次循环时我们再遍历下标3时,这时候下标3对应的元素已经是4了,相当于漏掉了一个要删除的元素。

3.2、为什么增强for循环删除数据会报错?

因为增强 for 循环过程其实调用的就是迭代器的 next() 方法,当你调用 ArrayList的remove 方法进行删除时,modCount 的值会 +1,而这时候迭代器中的 expectedModCount 的值却没有变,导致在迭代器下次执行 next() 方法时,首先调用checkForComodification()判断时,会由于expectedModCount != modCount 报 ConcurrentModificationException 的错误。

二、LinkedList学习总结

底层是基于双向链表实现的,因此增加,删除效率较高,查询效率较慢;

查询的源码采用二分查找,在只能从头或尾进行查询的情况下是最优解值;

迭代器基于Java的 ListIterator来完成双向迭代;

存储同样数据,占用内存要高于ArrayList,但理论上没有长度限制,而ArrayList的容量最多为Interger的最大值;

删除数据时推荐使用迭代器删除,因为迭代器的remove加了很多前置限制,同时删除数据时会导致LinkedList的状态发生变化,它会更新cursor来同步这一变化;

非线程安全。

后续待补充--