数据结构之ArrayList与顺序表_arraylist实现的是顺序表吗

        ArrayList是一个实现List接口的类，底层是动态类型顺序表，本质也就是数组，动态主要体现在它的扩容机制。那么既然是底层是数组，那我们为什么不直接使用数组而是要使用ArrayList类呢？

        1.假设我们有这样一个数组：

        我们要计算数组有效元素个数，但我们是否可以知道有效的数据？如果是纯数组，0并不是有效数据，但是如果我们有效数据就是0，就无法单靠数组解决了，而定义顺序表，其中会定义size变量，用于有效数据的使用。当然，顺序表还定义了其他方法（增删查改），便于对数组进行操作。

        解决了ArrayList存在的意义我们接下来简单使用一下：

 public static void main(String[] args) {
        // ArrayList创建，推荐写法
        // 构造一个空的列表
        List<Integer> list1 = new ArrayList<>();
        // 构造一个具有10个容量的列表
        List<Integer> list2 = new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
        // list3构造好之后，与list中的元素一致
        ArrayList<Integer> list3 = new ArrayList<>(list2);
        System.out.println(list2);
    }

        这时我们产生第二个问题，动态具体体现在什么地方？这里就需要了解一下顺序表的扩容机制：

2.调用构造方法的顺序表容量问题

（1）调用无参构造方法（自动扩容机制）

ArrayList<Integer> list = new ArrayList<>();
//此时顺序表底层的数组大小默认为0
List.add(1);
//当第一次进行add时，此时大小才被分为了10，之后的扩容是1.5倍

         当调用无参构造方法时，此时顺序表底层的数组并没有被划分空间大小，我们对list对象进行add时，add方法内部首先调用方法ensureCapacityInternal，size默认值为0，+1后传入参数1，进入ensureCapacityInternal方法内部调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity))方法，calculateCapacity方法会进行if判断，如果是默认的object[]空间，则返回默认大小10，然后ensureExplicitCapacity方法进行if判断条件为真，调用grow函数进行扩容，grow方法扩容机制具体逻辑见上图，即第一次调用add方法默认扩容为10，之后再调用add方法当顺序表容量不足时进行1.5倍扩容。

（2）调用带参构造方法（参数就是容量）

ArrayList<Integer> list = new ArrayList<>(10);

 即传入的参数就是初始容量。

了解了扩容机制后，我来简单实现一下顺序表的底层逻辑：

import java.util.Arrays;
 
public class MyArrayList {
    public int[] elem;
    public int usedSize;
 
    public MyArrayList() {
        this.elem = new int[10];
    }
    // 打印顺序表
    public void mytoString() {
        for(int i = 0;i < this.usedSize;i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //判断数组是否是满的
        if(isFull()){
            //扩容2倍
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
            this.elem[this.usedSize] = data;
            this.usedSize++;
 
    }
    //判断数组是否是满的
    public boolean isFull() {
        if(this.usedSize == this.elem.length){
            return true;
        }
        return false;
    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        //不能是满的数组
        if(isFull()) {
            //扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        if(pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法!");
            return;
        }
        //通过将pos下标后面的元素向后移一位，再插入
        for(int i = usedSize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for(int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for(int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1;//数组没有-1下标
    }
    // 获取 pos 位置的元素
    public int get(int pos) {
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos位置不合法!");
            //return -1;//这里只是简单检测一下，如果要找的元素就是-1，实际业务处理需要抛异常(throw new RuntimeException("pos下标不合法!"))
            //一般是自定义异常，这里为了简便使用了超时异常
            throw new RuntimeException("pos下标不合法!");
        }
 
        return this.elem[pos];
    }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        if(pos < 0 || pos >= this.usedSize){
            System.out.println("pos位置不合法!");
            throw new RuntimeException("pos下标不合法!");
        }
        this.elem[pos] = value;//覆盖原来的值
    }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        //顺序表不能为空
        if(isEmpty()){
            System.out.println("空的,不能删除!");
            return;
        }
        //找
        int index = indexOf(toRemove);
        for(int i = index; i < this.usedSize-1; i++) {
            //注意i不能走到有效数据的最后一个，否则会访问越界
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
        //this.elem[this.usedSize] = null;//如果元素是引用类型，覆盖后最后一个有效元素要置空为null
    }
    //判断数组是非为空
    public boolean isEmpty() {
        if(usedSize == 0) {
            return true;
        }
        return false;
    }
    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }
    // 清空顺序表
    public void clear() {
        //如果是引用类型要置空，否则会发生内存泄漏
//        for (int i = 0; i < this.usedSize; i++) {
//            this.elem[i] = null;
//        }
        this.usedSize = 0;
    }
}

以上就是ArrayList的主要逻辑，供大家参考学习。