一. 了解List
为什么要先介绍List呢？因为ArrayList是一个类，它实现了List接口，要想学好ArrayList就必须先了解List
从数据结构的角度看，List就是一个线性表，可以保存n个具有相同类型元素的有限序列，在该序列中，可以进行增删查改以及变量等操作
List为一个接口，里面提供了许多方法，此处不一一介绍，想了解可以查看List的官方文档
List 的官方文档
🔦关于List的使用：
List是个接口不能实例化对象，所以必须有类来实现它，而ArrayList就实现了List接口
二. ArrayList的介绍
上图可以清楚的了解到ArrayList继承的类和实现的接口，可以结合底层代码了解
🪔说明：
🏷️ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
🏷️ArrayList实现了Cloneable接口，表明ArrayList可以clone
🏷️ArrayList实现了Serializable接口，表明ArrayList可以支持序列化
🏷️ArrayList底层是一段连续空间，可以动态扩容，是一个动态类型的顺序表
🎯这里注意一个问题：ArrayList与Vector的区别？（面试题可能会考）
Vector与ArrayList一样都实现了List接口，底层也是一段连续的空间，是一个动态类的顺序表，唯一的区别是Vector是线程安全的，可以在多线程下使用，而ArrayList是线程不安全的，只能在单线程下安全使用
Vector是线程安全的，是因为底层对重要方法使用了synchronized加锁，所以才保证了线程安全
Vector底层方法实现：
三. ArrayList的使用
1. ArrayList的构造方法
构造方法 解释
| 构造方法 | 解释 |
| ArrayList() | 无参构造 |
| ArrayList(int initalCapacity) | 参数表明顺序表的初始容量 |
| ArrayList(Collection<? extends E> c) | 使用其它的Collection集合构建ArrayList |
对构造方法的使用进行代码展示：
import java.util.ArrayList; import java.util.List; public class ArrayListTest { public static void main(String[] args) { List<Integer> list1 = new ArrayList<>(); //无参构造 List<String> list2 = new ArrayList<>(20); //使用初始容量值构造 list1.add(1); list1.add(2); list1.add(3); List<Integer> list3 = new ArrayList<>(list1); //使用已有集合构造 } }
2. ArrayList的常用方法
ArrayList的方法非常多，此处只展示常用方法
| 方法 | 说明 |
| boolean add(E e) | 尾插e |
| void add(int index , E e) | 将e插入index位置 |
| boolean addAll(Collection<? extends T> c) | 尾插集合c中的元素 |
| E remove(int index) | 删除index位置上的元素 |
| boolean remove(Object o) | 删除第一个遇到的元素o |
| E get(int index) | 或取index位置元素 |
| E set(int index , E e) | 将index位置元素设置为e |
| void clear() | 清空 |
| boolean contains(Object o) | 判断o是否在该集合中 |
| int indexOf(Object o) | 返回第一个o的下标 |
| int lastIndexOf(Object o) | 返回最后一个o的下标 |
| List<E> subList(int fromIndex , int toIndex) | 截取部分list |
2.1 ArrayList的插入操作
尾插：
import java.util.ArrayList; import java.util.List; public class ArrayListTest { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); for(int i : list){ System.out.print(i+" "); } } }
打印：1 ，2 ，3依次打印出来
将元素插入到指定位置：将9插入到下标为1的位置
list.add(1,9);
打印：顺序为1，9，2，3
尾插一个集合的所有元素：
List<Integer> list1 = new ArrayList<>(); //创建新线性表list1 list1.add(6); list1.add(8); list.addAll(list1); //将list1尾插到list中
打印结果：1，9，2，3，6，8
2.2 ArrayList的删除操作
删除指定位置元素：将下标为0的元素删除
list.remove(0);
打印：发现之前0下标的元素1被删除了
删除遇到的第一个元素：因为该方法参数是Object类型，所以参数得传入包装类型
Integer a = 3;
list.remove(a);
打印：发现元素3被删除了
2.3 获取指定下标元素
list.remove(a);
int b = list.get(2);
System.out.println(b);
打印：得到2下标对应的元素6
2.4 将指定下标元素设置为新值
将2下标对应的值设置为7：
list.set(2,7);
打印结果：发现原来下标为2的元素3被设置为了7
2.5 判断某个元素是否在线性表中
判断2是否在该线性表中：
boolean flag1 = list.contains(2);
打印：
判断5是否在该线性表中：
boolean flag2 = list.contains(5);
打印：
2.6 返回指定元素第一次和最后一次出现的下标
比如ArrayList中的元素序列为：9，2，7，8，2
打印元素2第一次出现的下标：
System.out.println(list.indexOf(2));
打印：
打印元素2最后一次出现的下标：
System.out.println(list.lastIndexOf(2));
打印：
2.7 ArrayList的清空操作
list.clear(); System.out.println(list.size());
打印：所有元素被清空，有效元素的个数就为0
3. ArrayList的遍历操作
3.1 for循环遍历
public class ArrayListTest2 { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("小王"); list.add("小张"); list.add(("小花")); for(int i = 0;i < list.size();i++){ System.out.print(list.get(i)+" "); } System.out.println(); } }
打印结果：
3.2 foreach遍历
for(String s : list){ System.out.print(s+" "); }
打印结果：
3.3 迭代器遍历
Iterator<String> iterator = list.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next()+" "); }
打印结果：
四. ArrayList底层的扩容机制
ArrayList是一个动态类型的顺序表，即在插入元素的时候会自动扩容，下面是扩容机制：
🕯️总结：
✨当使用无参的构造方法创建ArrayList，容量默认值10在第一次插入的时候才会初始化初始容量，而不是在创建的时候就初始化容量
✨在插入时，会检测是否真正需要扩容，如果需要，调用grow扩容
✨初步预估按照原容量的1.5倍扩容
✨如果用户所需大小超过预估的1.5倍，则按照用户所需大小扩容
✨真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
✨使用copyOf进行扩容
五. 模拟实现ArrayList(面试可能会要求写)
我们这里是模拟实现，所以实现基本功能即可
1. 构造方法
这里给两个构造方法，一个是默认无参的，一个是带有初始容量参数的，默认的容量为10，无参的构造方法中，调用有参的构造方法，不用做的像标准库中那么复杂
public class MyArrayList<E>{ private E[] elementData; private int size; private static final int DEFAULT_CAPACITY = 10; public MyArrayList(){ this(DEFAULT_CAPACITY); } public MyArrayList(int initCapacity){ if(initCapacity <= 0){ initCapacity = DEFAULT_CAPACITY; } elementData = (E[]) new Object[initCapacity]; } }
2. 插入方法add
先实现在指定位置插入的方法：
1. 判断参数index是否合法
2. 确认是否扩容
3. 将index和后面位置的元素统一往后搬移
4. 往index位置插入，size++
public void add(int index,E e){ if(index < 0 || index > size){ throw new ArrayIndexOutOfBoundsException("add：index越界"); } ensureCapacity(size); for(int i = size-1;i >= index;i--){ elementData[i+1] = elementData[i]; } elementData[index] = e; size++; }
尾插：
我们发现尾插就是在size的位置进行插入的，所以可以调用在指定位置插入的方法，提高代码的复用
public boolean add(E e){ add(size,e); return true; }
扩容：
在每次插入是需要检测是否扩容，如果需要则进行扩容
1. 获取旧的容量值
2. 判断size是否大于该容量值
3. 如果大于或者等于，说明需要扩容
4. 采用1.5倍方式更新容量值
public void ensureCapacity(int size){ int oldCapacity = elementData.length; if(size >= oldCapacity){ int newCapacity = oldCapacity + (oldCapacity>>1); elementData = Arrays.copyOf(elementData,newCapacity); } }
3. 删除方法remove
删除指定位置元素：
1. 判断index是否合法
2. 将index后的元素统一向前搬移一个长度
3. size--
public E remove(int index){ if(index < 0 || index >= size){ throw new ArrayIndexOutOfBoundsException("remove：index越界"); } E ret = elementData[index]; for(int i = index+1;i < size;i++){ elementData[i-1] = elementData[i]; } size--; return ret; }
删除指定元素：
1. 先判断该元素是否存在，这里可以调用后面要实现的indexOf方法，如果返回为-1，则不存在，其他的都存在
2. indexOf会返回元素下标，所以可以调用上面删除指定位置元素的方法，提高代码复用
public boolean remove(E e){ int index = indexOf(e); if(index == -1){ return false; } remove(index); return true; }
4. 查找元素下标方法indexOf,lastIndexOf
查找第一次出现元素的位置：
从头遍历，找到返回下标，找不到返回-1
public int indexOf(E e){ for(int i = 0;i < size;i++){ if(e.equals(elementData[i])){ return i; } } return -1; }
查找最后一次出现元素的位置：
public int lastIndexOf(E e){ for(int i = size-1;i >= 0;i--){ if(e.equals(elementData[i])){ return i; } } return -1; }
从最后向前遍历，找到返回下标，找不到返回-1
💡注意：上述比较的时候，用equals方法比较，不能用==比较
5. subList方法
1. 判断参数是否合法
2. 用要截取长度为参数，创建新的MyArrayList
3. 从截取的起始位置依次往新的list中添加元素直到截取的结束位置
MyArrayList<E> subList(int from,int to){ if(from > to){ throw new IllegalArgumentException("subList：非法参数，from>to"); } int newSize = to-from; MyArrayList<E> list = new MyArrayList<>(newSize); while(from < to){ list.add(elementData[from]); from++; } return list; }
✨注意：subList截取的范围为[from,to)，是左闭右开的
6. contains，get，set，size，clear方法
contains方法：
我们可以调用indexOf位置查找该元素下标，若为-1则不包含，否则包含
public boolean contains(E e){ return -1==indexOf(e); }
get方法：
先判断参数是否合法，合法就直接返回该位置元素
public E get(int index){ if(index < 0 || index >= size){ throw new ArrayIndexOutOfBoundsException("get：index越界"); } return elementData[index]; }
set方法：
先判断参数是否合法，合法就直接修改
public void set(int index,E e){ if(index < 0 || index >= size){ throw new ArrayIndexOutOfBoundsException("set：index越界"); } elementData[index] = e; }
size方法：
直接返回size即可
public int size(){ return size; }
clear方法：
将size置为0，并且从头遍历元素，将每个位置置为null
public void clear(){ size = 0; for(int i =0;i < size;i++){ elementData[i] = null; } }
7. 对MyArrayList进行测试
public static void main(String[] args) { MyArrayList<Integer> list = new MyArrayList<>(4); list.add(1); //尾插1 list.add(2); //尾插2 list.add(3); //尾插3 list.add(3,4); //在位置3插入4 System.out.println(list); System.out.println(list.get(2)); //输出下标为2的元素 list.set(0,5); //将位置0的元素设置为5 System.out.println(list); System.out.println(list.contains(4)); //判断是否包含4 System.out.println(list.contains(9)); //判断是否包含9 list.remove(0); //删除位置0的元素 System.out.println(list); list.remove((Integer) 4); //删除元素4 System.out.println(list); list.add(3); System.out.println(list.indexOf(3)); //输出第一个3的位置 System.out.println(list.lastIndexOf(3)); //输出最后一个3的位置 MyArrayList<Integer> list2 = list.subList(0,1); //截取部分List System.out.println(list2); list.clear(); //清空 System.out.println(list.size()); //看看是否清空 }
打印结果：满足基本使用
