数据结构(Java实现)：ArrayList

1.ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.ArrayList构造方法分析

ArrayList有三个构造方法

1.无参的构造方法

首先我们看到一个elementData为ArrayList定义好的一个数组，默认为空，指数一个数组引用。然后看到DEFAULTCAPACITY_EMPTY_ELEMENTDATA

可以看到并没有给数组分配内存。

2.带一个int参数的构造方法（可以给ArrayList设置一个初始容量）

先看到if判断语句，当传入参数大于0时，直接分配一个参数大小的空间

传入参数等于0时与无参构造方法一样，并不会给数组分配空间

传入参数小于0就会抛出一个异常

3.带一个类型变量参数的构造方法

我们先对传入的参数进行解析Collection<? extends E> c

这样我们就可以传入一个ArrayList变量，举例如下

public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>();
        arrayList.add(10);
        arrayList.add(20);
        
        ArrayList<Integer> arrayList1=new ArrayList<>(arrayList);
        /*传入一个ArrayList变量，这个参数需要满足了下几个条件才能够传递
        *1.ArrayList实现了Collection接口
        *2.参数类型是arrayList1指定的泛型本身“Integer”
        */
    }
1
2
3
4
5
6
7
8
9
10
11

3.ArrayList的add方法以及扩容机制

看到上面的add方法，左边的add方法通过调用右边的add方法进行数据的插入操作，下面我们重点来讲解左边这个add方法

首先看到if判断语句，当数据的数量等于数组的长度就会调用grow方法进行扩容。

grow方法又调用了另一个grow方法

先看到if里面的判断语句，oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA当数组容量初始为DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空）的时候进入else语句elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];给数组分配空间为DEFAULT_CAPACITY和minCapacity的最大值

看到DEFAULT_CAPACITY的值为10，所以当数组初始空间为空时就会给数组分配一个容量为10的内存。正常进入if语句就会触发ArrayList的扩容机制



扩容的空间大概是原来的1.5倍，通过一步一步调用上面的方法（了解）

4.ArrayList常用方法

举例如下

public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("测试课程");
System.out.println(list);
// 获取list中有效元素个数
System.out.println(list.size());
// 获取和设置index位置上的元素，注意index必须介于[0, size)间
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
list.add(1, "Java数据结构");
System.out.println(list);
// 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
list.remove("JVM");
System.out.println(list);
// 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
list.remove(list.size()-1);
System.out.println(list);
// 检测list中是否包含指定元素，包含返回true，否则返回false
if(list.contains("测试课程")){
list.add("测试课程");
}
// 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
List<String> ret = list.subList(0, 4);
System.out.println(ret);
list.clear();
System.out.println(list.size());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

5.ArrayList遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意：

1. ArrayList最长使用的遍历方式是：for循环+下标 以及 foreach
2. 迭代器是设计模式的一种，后序容器使用更多，在进行详细介绍

6.ArrayList的缺陷

由于ArrayList底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。
为解决这个问题，java集合中又引入了LinkedList，即链表结构。下面一篇文章将详细讲解链表结构，大家可以关注一下。