因为热爱坚持所以,因为热爱所以热爱。熬过你无戏可演的日子,终于换来了人生的春天,共勉!!!
1.ArrayList继承体系
ArrayList中又称动态数组,底层是基于数组实现的列表,与数组的区别在于,其具备动态扩展能力从继承体系图中可看出。 ArrayList中 :
公共类 ArrayList<E> 扩展 AbstractList<E>
实现List < E >、RandomAccess、Cloneable、java.io。可序列化{
...
}
复制代码
实现了List、RandomAccess、Cloneable、java.io.Serializable等接口
- 实现了 列表 ,具备基础的添加、删除、遍历等操作
- 实现了 RandomAccess ,拥有随机访问的能力
- 实现了 Cloneable ,可以被克隆(浅拷贝) list.clone()
- 实现了 Serializable ,可以被序列化
2. ArrayList 属性
/**
* 默认初始容量。
*默认容量
*/
私有静态最终 int DEFAULT_CAPACITY = 10 ;
/**
·共享空 阵列 实例用于为 空的情况。
* 空数组,如果上限的容量为0时使用
*/
私有静态最终对象[] EMPTY_ELEMENTDATA = {};
/**
·共享空 阵列 实例用于为 默认尺寸空实例。
* 我们将其与 EMPTY_ELEMENTDATA 区分开来,以了解添加第一个元素时要膨胀多少。
*默认空容量的数组,长度为0,第一个容量时间使用,一个时间会初始添加为默认容量大小
*/
私有静态最终对象[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*该阵列到其中的元件缓冲器的存储ArrayList中。
*容量的该ArrayList是长度的此阵列缓冲器。任何
*带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空ArrayList
* 将在添加第一个元素时扩展为DEFAULT_CAPACITY 。
* 集合中真正存储数据元素的数组容器
*/
瞬态对象[] elementData; // 非私有以简化嵌套类访问
/**
*大小的该ArrayList(数量的它包含的元素)。
*集合中元素的个数
* @串行
*/
私有整数大小;
复制代码
- DEFAULT_CAPACITY :集合的默认容量,默认为10,通过 new ArrayList() 创建List集合实例时的默认容量为10。
- EMPTY_ELEMENTDATA :空 数组 ,通过 new ArrayList(0) 创建List集合实例时用的是这个空 数组 。
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA :这个默认容量空数组,这种是通过new ArrayList()无参构造方法创建集合时用的是这个空数组,与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用空数组的会初始化为DEFAULT_CAPACITY (10)个元素。
- elementData 存储数据元素的数组,使用瞬态响应,该定位知识化。
- 大小 :存储数据元素的个数,元素数据数组的长度非存储数据元素的个数。\
3.ArrayList构造方法
- 有参构造 ArrayList(int initialCapacity)
/**
* 构造一个具有指定初始容量的空列表。
* 构造具有指定初始能力的空数组
*
* @param initialCapacity 列表初始容量列表的初始容量
* @throws IllegalArgumentException 如果指定的初始容量为负
*
*对应初始初始容量,如果大于0就初始化元素数据为大小,如果等于0就使用EMPTY_ELEMENTDATA空数组,
* 如果小于0 异常。
*/
// ArrayList(int initialCapacity)构造方法
public ArrayList ( int initialCapacity) {
if (initialCapacity > 0 ) {
this .elementData = new Object[initialCapacity];
} else if (initialCapacity == 0 ) {
this .elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException( "不合理的初识能力:" +
初始容量);
}
}
复制代码
- 无参构造ArrayList()
/**
* 构造一个初始容量为 10 的空列表。
* 构造一个最终能力为10的空数组
*
* 不传初始空,初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组,
* 会在添加第一个元素的时候扩容为默认的大小,即10。
*/
public ArrayList () {
this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
复制代码
- 有参构造ArrayList(Collection c)
/**
* 构造一个包含指定元素的列表
* 集合,按照集合返回的顺序
* 迭代器 。
* 把集合的元素初始化到ArrayList中
*
* @param c 其元素将被放入此列表的集合
* @throws NullPointerException 如果指定的集合为空
*/
public ArrayList(Collection<? extends E> c) {
// 将构造方法中的集合参数转换成数组
elementData = c.toArray();
if (( size = elementData.length) != 0 ) {
// 检查类型c.toArray()返回不是Object[],如果不是,重拷贝成Object[].class类型
if (elementData.getClass() != Object[]. class )
//
数组的创建与拷贝elementData = Arrays.copyOf(elementData, size , Object[]. class );
} else {
// 如果c是空的集合,则初始化为空数组EMPTY_ELEMENTDATA
this .elementData = EMPTY_ELEMENTDATA;
}
}
复制代码
4.ArrayList相关操作方法
添加操作
1.add(E e)添加元素到集合中添加元素到更新,平均时间复杂度为O(1):
/**
* 将指定的元素附加到此列表的末尾。
*添加元素到细节,平均时间复杂度为O(1)
* * @param e 要附加到此列表的元素
* @return <tt>true</tt> (由 { @link Collection#add}指定)
*/
public boolean add (E e) {
//每加入一个元素,minCapacity大小+1,并检查是否需要扩容
ensureCapacityInternal(size + 1 ); // 增加 modCount!!
// 把元素插入到最后一位
elementData[size++] = e;
返回 真;
}
// 计算最小容量
private static int calculateCapacity (Object[] elementData, int minCapacity) {
// 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 返回DEFAULT_CAPACITY 和minCapacity 的一方
返回Math.max( DEFAULTCAPACITY_EMPTY_ELEMENTDATA )最小容量);
}
返回minCapacity;
}
//检查是否需要扩容
private void ensureCapacityInternal ( int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity ( int minCapacity) {
modCount++; // 数组结构被修改的次数+1
// 有溢出意识的代码存储元素的数据长度减少需要的最大容量时
if (minCapacity - elementData.length > 0 )
// 扩容
增长(最小容量);
}
/**
*扩容
* 增加容量以确保它可以保持至少
* 由最小容量 arg 指定的元素数量
* 增加容量以确保能够尽可能增加容量参数指定的元素数量
* @param minCapacity 所需的最小容量
* /
私有 空隙 成长(INT minCapacity) {
//原来的容量
INT oldCapacity = elementData.length;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1 );
// 如果新容量发现比需要的容量还小,则需要的容量
只有 if (newCapacity - minCapacity < 0 )
newCapacity = minCapacity;
// 如果新容量已经超过最大容量了,则使用最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0 )
newCapacity = 巨大的Capacity(minCapacity);
// 以新容量复制出来一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 使用最大容量
private static int hugeCapacity ( int minCapacity) {
if (minCapacity < 0 ) // 溢出
throw new OutOfMemoryError();
返回(minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
复制代码
执行流程:
- 检查是否需要扩容;
- 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA则初始化容量大小为DEFAULT_CAPACITY;
- 新容量是老容量的1.5倍(oldCapacity + (oldCapacity >> 1)),如果加了这么多容量发现比需要的容量还小,那么就以需要的容量为基础;
- 创建新容量的数组并把老数组拷贝到新数组;
2.add(int index,E element)添加元素到指定位置添加元素到指定位置,平均时间复杂度为O(n):
/**
* 在此指定位置插入指定元素
* 列表。移动当前在该位置的元素(如果有)和
* 右边的任何后续元素(在它们的索引上加一)。
*添加元素到指定位置,平均时间添加度为O(n)。
* * @param index 指定元素要插入的索引
* @param element 要插入的元素
*抛出: IndexOutOfBoundsException异常{ @inheritDoc }
*/
public void add ( int index, E element) {
// 检查是否越界
rangeCheckForAdd(index);
//检查是否需要扩容
ensureCapacityInternal(size + 1 ); // 增加 modCount!!
// 将inex及其之后的元素往后挪位,则索引位置处就空出来了
// **进行了大小-索引索引次操作**
System.arraycopy(elementData, index, elementData, index + 1 ,
大小 - 索引);
// 将元素插入到索引的位置
元素数据[索引] = 元素;
// 元素数量增1
尺寸++;
}
/**
* add 和 addAll 使用的 rangeCheck 版本。
* add和addAll方法使用的rangeCheck版本
*/
// 检查是否越界
private void rangeCheckForAdd ( int index) {
if (index > size || index < 0 )
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
复制代码
执行流程:
- 检查是否越界;
- 检查是否需要扩容;
- 把插入位置后的元素都往后移动一位;
- 在插入位置插入的元素;
- 元素数量增1;
3.addAll(Collection c)添加所有集合参数中的所有元素求两个集合的并集:
/**
* 将指定集合中的所有元素追加到末尾
* 这个列表,按照它们返回的顺序
* 指定集合的迭代器。此操作的行为是
* undefined 如果指定的集合在操作时被修改
* 正在处理。(这意味着这个调用的行为是
* undefined 如果指定的集合是这个列表,并且这个
* 列表非空。)
* 将集合c中所有元素添加到当前ArrayList中
* * @param c 包含要添加到此列表的元素的集合
* @return <tt>true</tt> 如果此列表因调用而更改
* @throws NullPointerException 如果指定的集合为空
*/
public boolean addAll(Collection<? extends E> c) {
// 将集合c转为数组
Object[] a = c.toArray();
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal( size + numNew); // Increments modCount
// 将c中元素全部拷贝到数组的最后
System.arraycopy(a, 0 , elementData, size , numNew);
//集合中元素的大小增加Ç的大小
尺寸+ = numNew;
// 如果c不为空就返回true,否则返回false
return numNew!= 0 ;
}
复制代码
执行流程:
- 拷贝c中的元素到数组a中;
- 检查是否需要扩容;
- 把数组中的元素拷贝到元素数据的尾部;
访问操作
4.get(int index)获取指定位置的元素获取指定位置的元素,时间更新度为O(1)。
/**
* 返回此列表中指定位置的元素。
* * @param index 要返回的元素的索引
* @return列表中指定位置的元素
*抛出: IndexOutOfBoundsException异常{ @inheritDoc }
*/
public E get ( int index) {
// 检查是否越界
范围检查(索引);
// 返回数组索引位置的元素
return elementData(index);
}
/**
* 检查给定的索引是否在范围内。如果不是,则抛出一个适当的
* 运行时异常。此方法*不*检查索引是否为
* 否定:它总是在数组访问之前立即使用,
* 如果 index 为负,则抛出 ArrayIndexOutOfBoundsException。
*检查给定的索引是否在集合有效元素数量范围内
*/
private void rangeCheck ( int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings ( "unchecked" )
E elementData ( int index) {
return (E) elementData[index];
}
复制代码
执行流程:
- 检查是否越界,只检查是否越上界,如果越上界抛出IndexOutOfBounds异常异常,如果越下界抛出是ArrayIndexOutOfBoundsException异常。
- 返回索引位置处的元素;
删除操作
5.remove(int index)删除指定索引位置的元素,
删除指定位置的元素,时间复杂度为O(n)。
/**
* 删除此列表中指定位置的元素。
* 将任何后续元素向左移动(从它们的元素中减去一个
* 指数)。
*删除指定位置的元素,时间复杂度为O(n)。
* * @param index 要删除的元素的索引
* @return从列表中移除的元素
*抛出: IndexOutOfBoundsException异常{ @inheritDoc }
*/
public E remove ( int index) {
// 检查是否越界
范围检查(索引);
// 集合数组结构修改次数+1
modCount++;
// 获取索引位置的元素
E oldValue = elementData(index);
int numMoved = 大小 - 索引 - 1 ;
// 如果索引不是最后一位,则将索引之后的元素往前
移位if (numMoved > 0 )
// **进行了大小-索引索引-1次操作**
System.arraycopy(elementData, index + 1、元素数据、索引、
numMoved);
// 将最后一个元素删除,帮助GC
elementData[--size] = null ; // 清除让 GC 做它的工作
// 返回旧值
return oldValue;
}
复制代码
执行流程:
- 检查是否越界;
- 获取指定位置的元素;
- 如果删除的不是最后一位,则其他元素往前移一位;
- 将最后一个位置为null,方便GC回收;
- 返回删除的元素。
注意:从源码中结果,ArrayList 删除元素的时候并没有缩容。
6.remove(Object o)删除指定元素值的元素
删除指定元素值的元素,时间增加度为O(n)。
/**
* 从此列表中删除第一次出现的指定元素,
* 如果存在。如果列表不包含该元素,则为
* 不变。更正式地,删除具有最低索引的元素
* <tt>i</tt> 使得
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
*(如果存在这样的元素)。如果此列表,则返回 <tt>true</tt>
* 包含指定的元素(或等效地,如果此列表
* 因调用而更改)。
* 删除指定元素值的元素,时间增加度为O(n)。
* * @param o 要从此列表中删除的元素(如果存在)
* 要报告列表中删除的元素(如果存在的话)
* @return <tt>true</tt> 如果此列表包含指定的元素
*/
public boolean remove(Object o) {
if (o == null ) {
// 遍历整个数组,找到元素第一次出现的位置,标记其快速删除
for ( int index = 0 ; index < size ; index++ )
// 如果要删除的元素为null,则以null进行比较,使用==
if (elementData[index] == null ) {
快速删除(索引);
返回 真;
}
} else {
// 遍历整个数组,找到元素第一次出现的位置,标出其快速删除
for ( int index = 0 ; index < size ; index++)
// 如果要删除的元素不为空,则进行比较,使用equals()方法
if (o.equals(elementData[index])) {
快速删除(索引);
返回 真;
}
}
返回 假;
}
/*
* 跳过边界检查的私有删除方法并且不
* 返回移除的值。
* 专属的移除方法,最后检查检查,并且不会返回删除的值。
*/
private void fastRemove( int index) {
// 少了一个越界的检查
modCount++;
//如果index不是最后一位,则将index之后的元素往前挪位
int numMoved = size - index - 1 ;
如果(numMoved > 0 )
System.arraycopy(elementData, index + 1 , elementData, index,
numMoved);
// 将最后一个元素删除,帮助GC
elementData[-- size ] = null ; //清除让GC做它的工作
}
复制代码
执行流程:
- 找到第一个相同的元素值的元素;
- 删除快速,进行数组的移动动;
- 最后一个元素置为null,通过GC去处理
其他运算
7.retainAll(Collection c)两个求集合的交集\
/**
* 求两个集合的交集
* 仅保留此列表中包含在
* 指定集合。换句话说,从这个列表中删除所有
* 不包含在指定集合中的元素。
* * @param c 集合包含要保留在此列表中的元素
* @return { @code true} 如果此列表因调用而更改
* @throws ClassCastException 如果此列表的元素的类
* 与指定的集合不兼容
* (<a href="Collection.html#optional-restrictions">opti
* @throws NullPointerException 如果此列表包含空元素并且
* 指定的集合不允许空元素
* (<a href="Collection.html#optional-restrictions">opti
* 或者如果指定的集合为空
* @see Collection#contains(Object)
*/
public boolean retainAll (Collection<?> c) {
// 集合c不能为null
Objects.requireNonNull(c);
// 调用删除方法,组件填充true,表示删除不包含在c中的元素
return batchRemove(c, true );
}
/**
* 特殊删除元素
* 补充为真表示删除c中不包含的元素
*补为假表示删除c中包含的元素
* @param c
* @param补充
* @返回
* /
私有 布尔 batchRemove (集合C,<?>布尔补体) {
最终对象[] elementData中=此.elementData;
/**
* 使用两个手指同时遍历数组
* 读历史每次自增1,写动态动态元素的时候才加1
* 这样不需要额外的空间,只需要在已有的数组上操作就可以了
*/
int r = 0 , w = 0 ;
布尔修改 =假;
尝试{
//遍历整个数组,如果Ç中包含该元素,则把该元素放到写指针的位置(以补为准)
为(; R <大小; R ++)
如果(c.contains(elementData中[R] ) == 补)
elementData[w++] = elementData[r];
}最后{
//正常来说ř最后是等于大小的,除非c.contains()抛出了异常
,如果(R 1 =大小){
//如果c.contains()抛出了异常,则把未读的元素都拷贝到写指针之后
System.arraycopy(elementData, r,
元素数据,w,
尺寸 - r);
w += 尺寸 - r;
}
if (w != size) {
// 将写轨迹之后的元素置为空,帮助GC
for ( int i = w; i < size; i++)
elementData[i] = null ;
modCount += 大小 - w;
// 新大小等于写图的位置(因为每个写一次写就加1,所以新大小就写了一个轨迹的)
大小 = w;
修改 =真;
}
}
// 有修改返回true
return modified;
}
复制代码
执行流程:
- 遍历元素数据数组;
- 如果元素在c中,则把这个元素添加到元素数据数组的w位置标出位置往后移一位;
- 走完之后,之前的元素都接触到的,之后(接触到)的元素不是接触到的;
- 将w之后(包含)的元素置为null,方便GC回收;
8.removeAll(Collection c)求两个集合的单方向差集
求两个集合的单差集,只保留当前集合中不在c中的元素,不保留在c中不在当前集合中的元素。
/**
* 从此列表中删除包含在列表中的所有元素
* 指定集合。
* 集合中删除指定的集合中的所有元素。
*
* @param c 集合包含要从此列表中删除的元素
* @return { @code true} 如果此列表因调用而更改
* @throws ClassCastException 如果此列表的元素的类
* 与指定的集合不兼容
*(<a href="Collection.html#optional-restrictions">可选</a>)
* @throws NullPointerException 如果此列表包含空元素并且
* 指定的集合不允许空元素
*(<a href="Collection.html#optional-restrictions">可选</a>),
* 或者如果指定的集合为空
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection <? > c) {
//集合c不能为空
Objects.requireNonNull(c);
//调用时装删除方法,元素
填充cfalse,表示删除包含在中的return batchRemove(c, false );
}
复制代码
- 与retainAll(Collection c)方法类似,只是这里保留不在c中的元素。\
5.ArrayList所使用的toString()方法分析
我们都知道ArrayList集合是可以直接使用toStrin()的,那么我们来挖方法一下ArrayList的toString如何实现的:
在ArrayList源码中并没有直接的toString()方法,我们需要到其父类AbstractList的父类AbstractCollection中寻找:
/**
* 返回此集合的字符串表示形式。字符串
* 表示由集合中的元素列表组成
* 顺序由其迭代器返回,括在方括号中
* (<tt>"[]"</tt>)。相邻元素由字符分隔
* <tt>", "</tt>(逗号和空格)。元素被转换为字符串
* 通过 {@link String#valueOf(Object)}。
*
* @return 这个集合的字符串表示
*/
公共字符串 toString() {
Iterator<E> it = iterator(); //获取迭代器
,如果(it.hasNext()!)//如果为空直接返回
返回 “[]” ;
// StringBuilder 进行字符串排列
StringBuilder sb = new StringBuilder();
某人 追加( '[' );
for (;;) { // 无限循环 == while(true)
E e = it. 下一个(); // 迭代器 next 方法取元素,绘制发光后移
sb。追加(e == this ? "(this Collection)" : e); // 三元判断
if (!it.hasNext())
return sb. 追加( ']' ).toString(); //没有元素了,则拼接右括号
某人。追加(',')。追加( '' ); // 还有元素存在
}
}
复制代码
6.关于ArrayList的问题(重点)
1.LinkedList插入删除数据速度比ArrayList高吗?
从受访者数据结构上说:
- ArrayList是实现了基于动态数组的数据结构
- LinkedList基于链表的数据结构。
- 在 尾部 插入数据, 数据量时LinkedList比较快 ,因为 ArrayList要大扩容 ,当数据量快时ArrayList比较,因为ArrayList扩容是当前 容量*1.5 ,大容量扩容一次会提供很多空间, 当ArrayList不需容时效率比LinkedList高 ,因为直接元素扩展 不需新节点
- 在 首部插入数据 , LinkedList ,因为LinkedList遍历插入更快速的位置读取时间,而ArrayList需要数组所有元素进行一次System.arraycopy
- 插入位置 越往中间 , LinkedList 插入 效率越低 ,因为它遍历获取插入位置是从两头往中间搜索,索引越往中间遍历越久,因此ArrayList 插入效率可能会比LinkedList 高
- 插入 位置越往后 , ArrayList 效率移向后 ,因为 数组 复制后的数据少了,System.arraycopy 就快了,因此在首部插入数据LinkedList 效率比ArrayList 高,需要增加数据ArrayList 效率比LinkedList 高
- LinkedList 可以实现这是,栈等数据结构,它的优势
2.ArrayList 是线程安全的吗?
因此,得出结论,ArrayList 非线程安全的集合!如果需要保证线程安全
1.使用Vector集合,其是线程安全的,但是相对于ArrayList来说,效率比较低。
而 向量 相对于数组列表是一个生命安全的,就在于其add()为集合添加元素的:
// 可以引入Vector的add方法加上了synchronized 同步关键字
public synchronized void addElement (E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1 );
elementData[elementCount++] = obj;
}
复制代码
2.使用Collections.synchronizedList()
List < String > list = new ArrayList<>();
List < String >synchronizedList = Collections.synchronizedList(list);
复制代码
3.使用CopyOnWriteArrayList
CopyOnWriteArrayList< Integer >cowaList = new CopyOnWriteArrayList< Integer >();
复制代码
注意:什么情况下不用给ArrayList加同步锁呢?
,在单线程情况下第一次加锁,为问题考虑!
第二,当ArrayList作为局部变量的时候,不会加锁,因为局部变量是焦点,而我们上述例子作为成员变量来使用,成员变量的集合是需要所有线程共享的,这是需要加锁!
3.如何复制一个ArrayList到另外一个ArrayList中去呢?你能几种?
使用ArrayList构造方法,ArrayList(Collection<? extends E> c)
使用addAll(Collection<? extends E> c)方法
自己写循环去一个add()