ArrayList
是数组的代表
概念
- 数组就是一块间断的内存空间
内存中申请一块内存空间。申请的这个空间是间断的。
特色
就是间断的,而且是固定大小的,并且外面寄存的值是同一个类型的,这就是数组汇合的特色。
- 内存空间间断
- 内存空间大小固定
-
寄存内容为同一类型
-
ArrayList
<>
申明的类型是什么就寄存什么类型- 没有
<>
申明,默认寄存的是Object
类型
-
一维数组
申明
-
Java 中能够应用 2 种形式来申明数组
-
dataType[] arrayRefVar
类型[] 变量名
-
dataTypa arrayRefVar[]
类型 变量名[]
[]
是数组的特有特色
创立
-
-
Java 中数组的创立形式同样有 2 种
-
arrayRefVar = new dataType[arraySize]
- 显示的通知程序,向
JVM
内存中申请了arraySize
长度的间断的内存空间 - 数组具体是多大,由
dataType
的类型来决定的
- 显示的通知程序,向
-
dataType[] arrayRefVar = {value0, value1, value2,...,valuek}
- 隐式的去创立,大括号外面有多少个元素,对应的长度就是多少
-
数组阐明
- Java 语言中提供的数组是用来存储固定大小的同类型元素
开始下标
-
数组下标从 0 开始
长度
-
数组长度为申明的
arraySize
最初下标
-
数组最初的元素下标为 数组长度 -1
arraySize-1
获取元素
-
数组外面的下标叫索引
获取下标元素
-
获取数组下标为
n
的值,表达式就是arrayRefVar[n]
- 获取下标为
3
的值,arrayRefVar[3]
- 获取下标为
获取第几个元素
-
获取数组第
m
个的值,表达式就是arrayRefVar[m-1]
- 获取数组内第
4
个值,表达式就是arrayRefVar[3]
- 获取数组内第
List 数组
- 就是
ArrayList
- 容许有反复的元素并且有先后放入秩序
ArrayList
类的底层是采纳动静数组进行数据管理的,反对下标拜访,增删元素不不便。
1. 动静数组扩容
2. 下标间接拜访
3. 增删不不便
申明
ArrayList 构造方法有 2 个:
- 一个是带参,申明时指定对应内存空间大小;
- 一个 是无参,申明时还没有指定内存空间大小,在第一次增加元素的时候,会指定内存空间大小,默认大小为 10。
指明长度
List arrList = new ArrayList(4);
对应有参构造方法源码:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//03、空集合创立
private static final Object[] EMPTY_ELEMENTDATA = {};
// 初始化创立 list
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
//01、element 初始化创立长度为 initialCapacity 的一个 object 类型的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity 0) {
//02、如果长度是 0 就创立默认的空集合
this.elementData = EMPTY_ELEMENTDATA;
} else {
//04、否则的话就抛异样
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
}
}
//Collection 是参数;List 接口和 HashSet 接口通通属于 Collection,Map 不属于 Collection 接口
//HashSet 接口传入也能够转为 ArrayList
public ArrayList(Collection<? extends E> c) {
//
Object[] a = c.toArray();
if ((size = a.length) != 0) {if (c.getClass() ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
}
- 申明的 int 大小,就是在内存中占用的空间大小
未知长度
// 多态申明
List arrList = new ArrayList();
对应无参构造方法源码:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//ArrayList 的大小,就是蕴含的元素数量
private int size;
//2、默认实现:就是 object 的一个数组 Object 的一维空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 数组缓冲区,Object[]数组类型的一个缓冲区
// 验证了对应的 ArrayList 底层是一个数组类型的缓冲区
//3、把这 object 数组赋值给整个的成员变量
//transient 序列化「不是程序内序列化的概念」,实现:当初运行一个在 jvm 内存中运行,当初想把在 jvm 内运行的放在磁盘上,下次间接应用这个去弄
transient Object[] elementData;
public ArrayList() {
//1、汇合底层的数组给它一个默认的实现
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
- 无参申明的状况下,只是在堆外面申明了一个地址及名称,没有真正的在栈外面申请内存空间的大小
-
只是申明了一个空数组,对应
size
值为 0为何 2 个构造方法?
场景:
想要存入的数组大小已知为 7,
有参
-
已知 数组长度,申明 list 的时候就申明大小
- 这样内存空间不会有节约
比方想要数组大小是 7,曾经晓得数组长度,
如果申明 list 的时候不申明大小,
那么默认在内存中 list 占用的空间是 10 个的大小空间,
这样对应有 3 个大小的空间其实是被节约掉的,
所以这个时候咱们就要用 int 参数的去申明。如果想要存入的数据长度大小是 30 的 list 数组,
不申明大小,那第一次 10,第二次 15,第三次 22,第四次 33,同样外面会有 3 个大小是被节约的
无参
- 无参申明数组时不会占用内存空间
- 在第一次增加元素时,申明内存空间占用 10 个
总结
-
数组自定义时,要思考以下几个因素:
- 数组名「name」
- 数组容量「capacity」
- 数组长度「size」
-
arrayList
底层是一个 数组- 有 2 个成员变量组成,一个是
[]
,一个是size
- 有 2 个成员变量组成,一个是
arrayList
数组的 初始容量是 10- 如果数组不够用,会进行扩容,会 1.5 大小的进行扩容
- 构造函数在 1.8 版本有 bug,在 1.9 版本解决掉了
-
size 作用
- 第一个作用就是指明数组以后有多少个元素,初始化没有给值的时候 size 指向的是 0,阐明是 0 个
- 第二个作用,咱们向数组中增加元素的时候,对应增加元素的下标地位是什么,能够用 size 示意
size 初始值是 0,对应默认的数组创立后要增加元素时,第一个 size 指针的地位也是 0
面试题一
6260652
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 空集合创立
private static final Object[] EMPTY_ELEMENTDATA = {};
// 把这 object 数组赋值给整个的成员变量
//transient 序列化「不是程序内序列化的概念」,实现:当初运行一个在 jvm 内存中运行,当初想把在 jvm 内运行的放在磁盘上,下次间接应用这个去弄
transient Object[] elementData;
//Collection 是参数;List 接口和 HashSet 接口通通属于 Collection,Map 不属于 Collection 接口
//HashSet 接口传入也能够转为 ArrayList
public ArrayList(Collection<? extends E> c) {
//
Object[] a = c.toArray();
if ((size = a.length) != 0) {if (c.getClass() ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
}
public class ArrayListDemo {public static void main(String[] args) {
//Integer 数组申明,隐士初始化
Integer[] array = {1,2};
//Integer 数组转换为 List
List<Integer> integerList = Arrays.asList(array);
//Object[] toArray();
Object[] objectArray = integerList.toArray();
System.out.println(objectArray.getClass() Object[].class);
//jdk8:false 有 bug,不会去返回导致的,所以用 jdk11 已解决
// jdk11:true
//Object[] toArray();
List<Integer> list = new ArrayList<>();
System.out.println(list.toArray().getClass() Object[].class);//true
}
}
增加元素
- 向数组内程序增加元素,复杂度是 O(1)级别的,指向这个地位,间接增加就能够
-
数组往指定地位上增加的时候,工夫复杂度 O(n),数组的特点就是增加比拟耗时
间接数组开端追加
add(E e)
-
add()
e
:要增加的元素对象,比方 66
-
modCount++
modCount
:列表在结构上被批改的次数- 数组内增加元素,会扭转原有数组
-
add(e, elementData, size);
-
增加元素之前看下数组的内存空间是否还有中央
elementData
:初始化时申明的数组s
:size
,初始化的值为 0elementData = grow()
:进行扩容
-
间接增加元素
-
如果数组的内存空间有空余,则间接 数组元素数量「
size
」加 1,数组长度「elementData.length
」不变-
elementData[s] = e;
s
就是数组元素数量size
e
要增加的元素,不须要扩容,间接赋值
-
size = s + 1;
- 数组元素数量多 1️
-
数组长度为 3,第 2 次增加元素 object,在 add 之前,size=1,add 增加间接 elementData[1] = object; size=2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 列表在结构上被批改的次数
protected transient int modCount = 0;
//ArrayList 蕴含的元素数量 严格来说不是长度大小
private int size;
public boolean add(E e) {
// 增加会批改数组
modCount++;
//01、首先确保有容量
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
//ArrayList 的大小 初始化以后数组的长度
if (s elementData.length)
// 扩容操作
elementData = grow();
elementData[s] = e;
size = s + 1;
}
}
指定地位增加
add(int index, E element)
想要在一个曾经创立好的数组内插入元素,首先咱们须要把对应插入元素的下标的内容空进去,须要进行一个元素转移,把 88 而后放进去,而后 size 指针指到下一个要增加元素的地位,并且阐明以后元素大小是多少,对应动态图如下:
-
rangeCheckForAdd(index);
- 先查看传入的数组下标是否有越界
- 超出则抛异样:
IndexOutOfBoundsException
{数组越界异样}
-
modCount++
modCount
:列表在结构上被批改的次数- 数组内增加元素,会扭转原有数组
- 如果数组的内存空间有空余
-
arraycopy
- 数组要插入元素后的元素通过 copy 来进行向后挪动,要插入元素的地位空进去
-
elementData[index] = element;
- 间接赋值要插入的元素到以后地位
- 间接 数组元素数量「
size
」加 1,数组长度「elementData.length
」不变
public void add(int index, E element) {rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
扩容操作
扩容怎么操作呢?
先申请一个新的内存空间,这个时候数组想扩多大就扩多大,
而后将原来的数组内容挪动到一个新的数组中,动静数组的一个动静扩容叫做一个伪扩容。栈中援用的内容只认 data,所以 data 进行一个从新指向就能够了,对应 newData 援用 就没用了。
对于咱们来说看到的还是 data,只不过对应的 data 指向了新的援用空间。
老的内存空间就干掉了,数组对应的物理地址援用,指向了新的内存空间。
-
s elementData.length
s
就是数组元素数量size
elementData.length
是 数组长度- 此时阐明数组占用的内存空间里没有闲暇空间,最初一个数组元素就在
数组长度 -1
的地位上 - 这时要增加元素的话,因为原始申请的内存空间没有了,须要扩容持续申请内存空间
-
grow(size + 1)
- 扩容
- 底层就是数组的复制
-
Arrays.copyOf(elementData, newCapacity(minCapacity));
- 把原有数组所在的内存空间的元素,复制到新扩容的内容空间外面
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { // 间接数组最初元素增加的扩容 private void add(E e, Object[] elementData, int s) { //ArrayList 的大小 初始化以后数组的长度 if (s elementData.length) // 扩容操作 elementData = grow(); elementData[s] = e; size = s + 1; } // 指定元素地位增加的扩容 public void add(int index, E element) { //... final int s; Object[] elementData; if ((s = size) (elementData = this.elementData).length) elementData = grow(); //... } private Object[] grow() {return grow(size + 1); } // 减少容量以确保它至多能够包容最小容量参数指定的元素数量。// 参数:minCapacity – 所需的最小容量 private Object[] grow(int minCapacity) { // 数组 = 复制一个新数组,对应要复制的数组 elementData,返回的正本的长度 return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); } }
-
grow(int minCapacity)
:- 数组拷贝到新数组中
具体扩容逻辑
-
newCapacity(minCapacity)
-
minCapacity
:size + 1
- 扩容的最小容量是 原来数组长度 +1
-
-
int oldCapacity = elementData.length;
- 扩容前数组长度
-
int newCapacity = oldCapacity + (oldCapacity >> 1);
- 扩容后数组长度
- 旧数组长度 + 0.5 倍的旧数组长度
- 每次扩容为 原数组的
1.5
倍
<< : 左移运算符,num << 1, 相当于 num 乘以 2
>> : 右移运算符,num >> 1, 相当于 num 除以 2
-
newCapacity - minCapacity <= 0
- 新容量 <= 最小容量
-
场景 1:
return minCapacity;
-
间接返回最小容量
原来数组容量为 1,则按 动静扩容 规定新数组容量为 1.5;间接扩容的最小容量是 2;那就间接返回最小容量
-
场景 2:
-
elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- 初始化数组,无参结构初始化数组
-
Math.max(DEFAULT_CAPACITY, minCapacity)
比拟最大的值为最新数组的容量- 如果增加元素对应数组大小小于 10 的时候,间接创立一个长度为 10 的数组。
ArrayList
都将扩大为DEFAULT_CAPACITY
「默认数组空间间接扩容大小为 10」
-
-
场景 3:
-
minCapacity < 0
- 最小容量 <0
-
抛异样:内存不足异样
OutOfMemoryError
-
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private int newCapacity(int minCapacity) {
// 旧容量 数组创立初始化的时候的容量
int oldCapacity = elementData.length;
// 新容量是 1.5 倍旧容量 oldCapacity >> 1 oldCapacity 除以 2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新容量 <= 最小容量
if (newCapacity - minCapacity <= 0) {
//
if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
//DEFAULT_CAPACITY = 10 默认初始容量
return Math.max(DEFAULT_CAPACITY, minCapacity);
// 如果最小容量 <0 内存不足异样
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 新容量 <= 最小容量 间接返回 最小容量
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
}
总结:
- 动静扩容数组 1.5 倍在数组长度大于 10 当前才真正失效。
删除元素
对应的删除,删除完对应下标元素后,须要把其它元素从后往前挪动。
把数组中索引为 1 的地位进行删除,对应咱们间接删除数据就能够。
然而数组是一个间断的内存空间,如果把 1 删除了对应的内存空间就不间断了,
所以要持续,把前面的数组元素往前挪动,进行一个元素的转移,
所以数组删除也不快,工夫复杂度也是 O(n)级别的。
-
Objects.checkIndex(index, size);
- 先查看下对应传入的下标是否数组越界
-
fastRemove
- 疾速删除
-
oldValue
-
返回 要删除的元素
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {public E remove(int index) {Objects.checkIndex(index, size); final Object[] es = elementData; @SuppressWarnings("unchecked") E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; } private void fastRemove(Object[] es, int i) { modCount++; // 新数组长度 final int newSize; // 有点相似循环操作 if ((newSize = size - 1) > i) // 源数组:es;源数组中的起始地位:i + 1;指标数组:es;// 指标数据中的起始地位:i;要复制的数组元素的数量:newSize - i // 将指定源数组中的数组从指定地位开始复制到指标数组的指定地位 System.arraycopy(es, i + 1, es, i, newSize - i); es[size = newSize] = null; } }
-
fastRemove(Object[] es, int i)
-
modCount
- 数组变动,所以自增
-
newSize
- 删除元素后新数组长度
size - 1
-
i
- 要删除的元素下标
-
newSize > i
- 阐明删除的不是最初一个元素,须要进行数组拷贝
-
拷贝长度为
newSize - i
数组长度是 6,删除下标为 3 的元素,则 newSize=5,数组拷贝往前挪动 2 个(5-3)
- 最初更新数组长度
总结:
- 数组删,工夫复杂度也是 O(n)级别的
获取元素 / 批改元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {public E get(int index) {Objects.checkIndex(index, size);
return elementData(index);
}
public E set(int index, E element) {Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
}
get()
办法去校验一下下标是否超出长度,超出就抛异样,没有超出就间接返回set()
办法同样也是先校验一下对应下标是否超出长度,如果超出就抛异样。如果没有就间接拿到这个下标内容,间接用传入的参数值替换掉
异样抛出状况
rangeCheckForAdd(index);
- add()办法指定 index 增加元素应用:
add(int index, E element)
-
传入下标和数组元素个数做比拟,下标只有大于数组个数抛 数组越界异样,下标等于数组长度不抛异样
private void rangeCheckForAdd(int index) {if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
Objects.checkIndex(index, size);
- remove(),get(),set() 应用
-
传入下标和数组元素个数做比拟,下标等于元素个数也抛数组越界异样
public static int checkIndex(int index, int length) {return Preconditions.checkIndex(index, length, null); }
public static <X extends RuntimeException> int checkIndex(int index, int length,BiFunction<String, List<Integer>, X> oobef) {if (index < 0 || index >= length) throw outOfBoundsCheckIndex(oobef, index, length); return index; }