ArrayList
Page content
ArrayList
简介
ArrayList是实现 List 接口的实现类，内部是一个大小可变的数组。
ArrayList 是一个用数组实现的集合，支持随机访问，元素有序且可以重复。
ArrayList 的好处是可以不用限定容器的大小，它会根据元素的增加而扩容。但是存储进去的数据类型都会变成Object类型，虽然每个元素有自己的index，但不像数组的下标可以更加方便的操作。
类定义
ArrayList定义如下：
1public class ArrayList<E> extends AbstractList<E>
2 implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 实现 RandomAccess 接口
这是一个标记接口，一般此标记接口用于 List 实现，以表明它们支持快速（通常是恒定时间）的随机访问。该接口的主要目的是允许通过算法改变其行为，以便在应用于随机或顺序访问列表时提供良好的性能。
比如在工具类Collections中，应用二分查找方法时判断是否实现了RandomAccess接口。
- 实现 Cloneable 接口
这个类是 java.lang.Cloneable，前面我们讲解深拷贝和浅拷贝的原理时，我们介绍了浅拷贝可以通过调用 Object.clone() 方法来实现，但是调用该方法的对象必须要实现 Cloneable 接口，否则会抛出 CloneNoSupportException异常。
Cloneable 和 RandomAccess 接口一样也是一个标记接口，接口内无任何方法体和常量的声明，也就是说如果想克隆对象，必须要实现 Cloneable 接口，表明该类是可以被克隆的。
- 实现 Serializable 接口
也是标记接口，表示能被序列化。
- 实现 List 接口
这个接口是 List 类集合的上层接口，定义了实现该接口的类都必须要实现的一组方法，如下所示，下面我们会对这一系列方法的实现做详细介绍。
1public interface List<E> extends Collection<E> {
2 int size();
3 boolean isEmpty();
4 boolean contains(Object o);
5 Iterator<E> iterator();
6 Object[] toArray();
7 <T> T[] toArray(T[] a);
8 boolean add(E e);
9 boolean remove(Object o);
10 boolean containsAll(Collection<?> c);
11 boolean addAll(Collection<? extends E> c);
12 boolean addAll(int index, Collection<? extends E> c);
13 boolean removeAll(Collection<?> c);
14 boolean retainAll(Collection<?> c);
15
16 default void replaceAll(UnaryOperator<E> operator) {
17 Objects.requireNonNull(operator);
18 final ListIterator<E> li = this.listIterator();
19 while (li.hasNext()) {
20 li.set(operator.apply(li.next()));
21 }
22 }
23
24 @SuppressWarnings({"unchecked", "rawtypes"})
25 default void sort(Comparator<? super E> c) {
26 Object[] a = this.toArray();
27 Arrays.sort(a, (Comparator) c);
28 ListIterator<E> i = this.listIterator();
29 for (Object e : a) {
30 i.next();
31 i.set((E) e);
32 }
33 }
34
35 void clear();
36 boolean equals(Object o);
37 int hashCode();
38 E get(int index);
39 E set(int index, E element);
40 void add(int index, E element);
41 E remove(int index);
42 int indexOf(Object o);
43 int lastIndexOf(Object o);
44 ListIterator<E> listIterator();
45 ListIterator<E> listIterator(int index);
46 List<E> subList(int fromIndex, int toIndex);
47
48 @Override
49 default Spliterator<E> spliterator() {
50 return Spliterators.spliterator(this, Spliterator.ORDERED);
51 }
52}
字段属性
1private static final long serialVersionUID = 8683452581122892189L;
2
3// 集合默认大小
4private static final int DEFAULT_CAPACITY = 10;
5
6// Object类型的空数组实例
7private static final Object[] EMPTY_ELEMENTDATA = {};
8
9// 这也是一个空的数组实例，和 EMPTY_ELEMENTDATA 空数组相比是用于了解添加元素时数组膨胀多少
10private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
11
12// 用来存储 ArrayList 集合的元素，集合的长度即这个数组的长度
13transient Object[] elementData;
14
15private int size;
构造函数
无参构造函数
1public ArrayList() {
2 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
3}
此无参构造函数将创建一个 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 声明的数组，注意此时初始容量是0，而不是 10。
- 注意：根据默认构造函数创建的集合
ArrayList list = new ArrayList();此时集合长度是0。
初始化集合大小构造函数
当大于0时，给定多少那就创建多大的数组；当等于0时，创建一个空数组；当小于0时，抛出异常。
1public ArrayList(int initialCapacity) {
2 if (initialCapacity > 0) {
3 this.elementData = new Object[initialCapacity];
4 } else if (initialCapacity == 0) {
5 this.elementData = EMPTY_ELEMENTDATA;
6 } else {
7 throw new IllegalArgumentException("Illegal Capacity: "+
8 initialCapacity);
9 }
10}
传入一个集合的构造函数
当我们想将一个集合转化为ArraList，可用此构造函数：
- 将已有的集合复制到 ArrayList 集合中去
1public ArrayList(Collection<? extends E> c) {
2 elementData = c.toArray(); // Object[] toArray();
3 if ((size = elementData.length) != 0) {
4 if (elementData.getClass() != Object[].class)
5 elementData = Arrays.copyOf(elementData, size, Object[].class);
6 } else {
7 this.elementData = EMPTY_ELEMENTDATA;
8 }
9}
添加元素
源码分析
ArrayList 集合是由数组构成的，那么向 ArrayList 中添加元素，也就是向数组赋值。一个数组的声明大小是固定的，而使用 ArrayList 时，能添加任意多个元素，这就涉及到数组的扩容。
扩容的核心方法就是调用Arrays.copyOf方法，创建一个更大的数组，然后将原数组元素拷贝过去即可。
1public boolean add(E e) {
2 ensureCapacityInternal(size + 1); // 确定集合的大小，如果集合满了，则要进行扩容操作
3 elementData[size++] = e;
4 return true;
5}
6
7private void ensureCapacityInternal(int minCapacity) {
8 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
9}
10private void ensureExplicitCapacity(int minCapacity) {
11 modCount++;
12 if (minCapacity - elementData.length > 0)
13 grow(minCapacity);
14}
15private static int calculateCapacity(Object[] elementData, int minCapacity) {
16 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
17 return Math.max(DEFAULT_CAPACITY, minCapacity);
18 }
19 return minCapacity;
20}
在 ensureExplicitCapacity 方法中，首先对修改次数modCount加1，这里的modCount给ArrayList的迭代器使用的，在并发操作被修改时，提供快速失败行为（保证modCount在迭代期间不变，否则抛出ConcurrentModificationException异常，可以查看源码865行）
接着判断minCapacity是否大于当前ArrayList内部数组长度，大于的话调用grow方法对内部数组elementData扩容，grow方法代码如下：
1private void grow(int minCapacity) {
2 int oldCapacity = elementData.length;
3 int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
4 if (newCapacity - minCapacity < 0)
5 newCapacity = minCapacity;
6 if (newCapacity - MAX_ARRAY_SIZE > 0)
7 newCapacity = hugeCapacity(minCapacity);
8 elementData = Arrays.copyOf(elementData, newCapacity);
9}
10
11private static int hugeCapacity(int minCapacity) {
12 if (minCapacity < 0) // overflow
13 throw new OutOfMemoryError();
14 return (minCapacity > MAX_ARRAY_SIZE) ?
15 Integer.MAX_VALUE :
16 MAX_ARRAY_SIZE;
17}
总结
- 当通过 ArrayList() 构造一个空集合，初始长度是为0的，第 1 次添加元素，会创建一个长度为10的数组，并将该元素赋值到数组的第一个位置。
- 第 2 次添加元素，集合不为空，而且由于集合的长度size+1是小于数组的长度10，所以直接添加元素到数组的第二个位置，不用扩容。
- 第 11 次添加元素，此时 size+1 = 11，而数组长度是10，这时候创建一个长度为10+10*0.5 = 15 的数组（扩容1.5倍），然后将原数组元素引用拷贝到新数组。并将第 11 次添加的元素赋值到新数组下标为10的位置。
- Integer.MAX_VALUE - 8 = 2147483639（21亿多），然后第 2147483639/1.5=1431655759（14亿多，这个数是要进行扩容） 次添加元素，为了防止溢出，此时会直接创建一个 1431655759+1 大小的数组，这样一直，每次添加一个元素，都只扩大一个范围。
- 即第14.31655759亿次添加元素时，它的1.5倍就基本是Integer.MAX_VALUE了，就不能再以1.5倍扩容了，而是每次只扩大一个范围。
- 第 Integer.MAX_VALUE - 7 次添加元素时，创建一个大小为 Integer.MAX_VALUE 的数组，再进行元素添加。
- 第 Integer.MAX_VALUE + 1 次添加元素时，抛出 OutOfMemoryError 异常。
注意：是可以向集合中添加 null 的，因为数组可以有 null 值存在。
1Object[] obj = {null,1};
2
3ArrayList list = new ArrayList();
4list.add(null);
5list.add(1);
6System.out.println(list.size()); // 2
删除元素
根据索引删除元素
remove(int index) 方法表示删除索引index处的元素，首先通过 rangeCheck(index) 方法判断给定索引的范围，超过集合大小则抛出异常；接着通过 System.arraycopy 方法对数组进行自身拷贝。
源码如下：
1public E remove(int index) {
2 rangeCheck(index);
3
4 modCount++;
5 E oldValue = elementData(index);
6
7 int numMoved = size - index - 1;
8 if (numMoved > 0)
9 System.arraycopy(elementData, index+1, elementData, index,
10 numMoved);
11 elementData[--size] = null; // clear to let GC do its work
12
13 return oldValue;
14}
直接删除指定元素
remove(Object o)方法是删除数组中从前往后第一次出现的该元素。然后通过System.arraycopy进行数组自身拷贝。
源码如下：
1public boolean remove(Object o) {
2 if (o == null) {
3 for (int index = 0; index < size; index++)
4 if (elementData[index] == null) {
5 fastRemove(index);
6 return true;
7 }
8 } else {
9 for (int index = 0; index < size; index++)
10 if (o.equals(elementData[index])) {
11 fastRemove(index);
12 return true;
13 }
14 }
15 return false;
16}
修改元素
通过调用 set(int index, E element) 方法在指定索引 index 处的元素替换为 element。并返回原数组的元素。
1public void set(E e) {
2 if (lastRet < 0)
3 throw new IllegalStateException();
4 checkForComodification();
5
6 try {
7 ArrayList.this.set(lastRet, e);
8 } catch (IndexOutOfBoundsException ex) {
9 throw new ConcurrentModificationException();
10 }
11}
通过调用 rangeCheck(index) 来检查索引合法性。
当索引为负数时，会抛出 java.lang.ArrayIndexOutOfBoundsException 异常；当索引大于集合长度时，会抛出 IndexOutOfBoundsException 异常。
1private void rangeCheck(int index) {
2 if (index < 0 || index >= this.size)
3 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
4}
查找元素
根据索引查找元素
源码：
1public E get(int index) {
2 rangeCheck(index);
3 return elementData(index);
4}
根据元素查找索引
返回索引是通过遍历整个数组实现的，且返回第一次出现该元素的下标，如果没有则返回 -1
源码：
1public int lastIndexOf(Object o) {
2 if (o == null) {
3 for (int i = size-1; i >= 0; i--)
4 if (elementData[i]==null)
5 return i;
6 } else {
7 for (int i = size-1; i >= 0; i--)
8 if (o.equals(elementData[i]))
9 return i;
10 }
11 return -1;
12}
此外， lastIndexOf(Object o) 方法是返回最后一次出现该元素的下标。
1public int lastIndexOf(Object o) {
2 if (o == null) {
3 for (int i = size-1; i >= 0; i--)
4 if (elementData[i]==null)
5 return i;
6 } else {
7 for (int i = size-1; i >= 0; i--)
8 if (o.equals(elementData[i]))
9 return i;
10 }
11 return -1;
12}
可见lastIndexOf(Object o) 方法是从后往前遍历的。
遍历集合
- 内容有点多，见原文
- 通过
get(int index)
1for(int i = 0 ; i < list.size() ; i++){
2 System.out.print(list.get(i)+" ");
3}
- 迭代器
iterator
1ArrayList<String> list = new ArrayList<>();
2// 添加元素的步骤省略...
3Iterator<String> it = list.iterator();
4while(it.hasNext()){
5 String str = it.next();
6 System.out.print(str+" ");
7}
SubList
在 ArrayList 中有这样一个方法：
1public List<E> subList(int fromIndex, int toIndex) {
2 subListRangeCheck(fromIndex, toIndex, size);
3 return new SubList(this, 0, fromIndex, toIndex);
4}
作用是返回从 fromIndex(包括) 开始的下标，到 toIndex(不包括) 结束的下标之间的元素视图。如下：
1ArrayList<String> list = new ArrayList<>();
2list.add("a");
3list.add("b");
4list.add("c");
5list.add("d");
6
7List<String> subList = list.subList(0, 1);
8for(String str : subList){
9 System.out.print(str + " "); // a b
10}
SubList类是 ArrayList 中的一个内部类。
注意：返回的是原集合的视图，也就是说，如果对 subList 出来的集合进行修改或新增操作，那么原始集合也会发生同样的操作。想要独立出来一个集合，解决办法如下：
1List<String> subList = new ArrayList<>(list.subList(0, 2));
trimToSize()
该方法用于回收多余的内存。trim是修剪的意思，也就是说一旦我们确定集合不再添加多余的元素之后，调用 trimToSize() 方法会将实现集合的数组大小调整为集合元素的大小。
1public void trimToSize() {
2 modCount++;
3 if (size < elementData.length) {
4 elementData = Arrays.copyOf(elementData, size);
5 }
6}
注意：该方法会花时间来复制数组元素，所以应该在确定不会添加元素之后再调用。
使用
1// Arraylist
2
3import java.util.ArrayList;
4import java.util.Iterator;
5import java.util.List;
6
7public class Main {
8 public static void main(String[] args) {
9 List<String> staffs = new ArrayList<String>();
10 List<String> corporation = new ArrayList<String>();
11 //添加数据
12 staffs.add("A");
13 staffs.add("B");
14 staffs.add("C");
15 corporation.add("Boss");
16
17 //在某个位置插入元素，此位置后的元素后移
18 staffs.add(1,"a");
19
20 staffs.set(1,"2");
21 staffs.get(1); //获取某位置的元素
22
23 staffs.indexOf("A");
24
25 staffs.size();
26 staffs.isEmpty();
27
28 corporation.addAll(staffs);//将staffs中的元素全部添加到corporation
29 corporation.addAll(0,staffs); //添加到指定位置
30
31 corporation.remove(" "); //直接删除元素
32 corporation.remove(2); //表示把下标为2对应的值删掉，后面的值向前移动
33
34 corporation.clear(); //清除所有数据
35
36 System.out.println(staffs.toString());
37
38 for(int i=0;i<staffs.size();i++) {
39 System.out.println(staffs.get(i)); //打印所有元素
40 }
41
42 System.out.println("----");
43 //另一种遍历方法：用迭代器方法。
44 //staffs.iterator()把数组中的值放到了迭代器中，然后在迭代器中遍历
45 Iterator<String> iterator = staffs.iterator();
46 while(iterator.hasNext()) {
47 System.out.println(iterator.next()); //下标后移，并且判断是否有数据了 iterator.next()就是值
48 }
49 }
50}
51
Arraylist_sort
1 // Arraylist_sort
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.Scanner;
6
7public class Arraylist_sort {
8 public static void main(String[] args) {
9 Scanner scan = new Scanner(System.in);
10 int n;
11 ArrayList al = new ArrayList();
12 System.out.println("请输入需要的个数");
13 n = scan.nextInt();
14 System.out.println("请逐一输入");
15 for (int i = 0; i < n; i++) {
16 al.add(i, scan.nextInt());
17 }
18 System.out.println("你输入的数字是：");
19 for (int i = 0; i < al.size(); i++) {
20 int temp = (int) al.get(i);
21 System.out.print(temp + " ");
22 }
23 Collections.sort(al); // 针对一个ArrayList内部的数据排序,默认从小到大排序
24 // Collections.sort(al,Collections.reverseOrder()); //从大到小
25 System.out.println();
26 System.out.println("经过排序后：");
27 for (int i = 0; i < al.size(); i++) {
28 int temp = (int) al.get(i);
29 System.out.print(temp + " ");
30 }
31
32 //Collections.sort() 方法对 ArrayList 的元素或者任何其他 List 的实现提供的可比较的元素进行排序，
33 //这意味着这些元素的类需要实现 java.lang 包中的 Comparable 接口。
34 }
35}
