想学好ArrayList，看完这篇就够了

一. 了解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)尾插evoid add(int index , E e)将e插入index位置boolean addAll(Collection<? extends T> c)尾插集合c中的元素E remove(int index)删除index位置上的元素boolean remove(Object o)删除第一个遇到的元素oE get(int index)或取index位置元素E set(int index , E e)将index位置元素设置为evoid 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()); //看看是否清空
    }

打印结果：满足基本使用