数据结构之ArrayList与顺序表（上）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

顺序表的学习，点我

上面这篇博文是关于顺序表的基础知识，以及顺序表的实现。

手动实现顺序表的源码：

分析Java 8 的 ArrayList 的源码

字段：

构造方法：

ArrayList本身的扩容机制和分配内存机制

ArrayList常见操作

ArrayList的遍历

普通for循环遍历

for-each遍历

toString方法遍历

迭代器遍历

手动实现顺序表的源码：

下面是Java版的顺序表源码：

public class MyArraylist {
    public int[] elem;
    public int usedSize;//0
    //默认容量
    private static final int DEFAULT_SIZE = 10;

    public MyArraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }

    /**
     * 打印顺序表:
     *   根据usedSize判断即可
     */
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
        System.out.println();
    }

    // 新增元素,默认在数组最后新增
    public void add(int data) {
        // 增加元素之前得先判断数组是否已满
        if (isFull()) {
            expansion();
        }
        // 尾插数据不需要判断 pos 位置是否合法
        elem[this.usedSize++] = data;
    }

    // 扩容
    private void expansion() {
        // 原来数组的2倍扩容
        this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
    }

    /**
     * 判断当前的顺序表是不是满的！
     * @return true:满   false代表空
     */
    public boolean isFull() {
        // 判断这个数组的有效元素个数是否等于数组的长度
        return this.usedSize == this.elem.length;
    }


    private boolean checkPosInAdd(int pos) {
        if (pos < 0 || pos > this.usedSize) {
            return false;
        }
        return true;//合法
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) throws PosofAddException{
        if (!checkPosInAdd(pos)) {
            throw new PosofAddException("add(int pos, int data) " +
                    "pos位置不合法");
        }
        // 判断是否为尾插
        if (pos == this.usedSize) {
            add(data);
        }else {
            // 开始移除元素（从后往前移除）
            for (int i = this.usedSize; i > pos; i--) {
                this.elem[i] = this.elem[i-1];
            }
            // 开始插入数据
            this.elem[pos] = data;
            this.usedSize++;
        }
    }

    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        // 先判断这个数组是否有元素
        if (isEmpty()) {
            return false;
        }
        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;
    }

    // 获取 pos 位置的元素
    public int get(int pos) throws PosofGetException{
        if (pos < 0 || pos > this.usedSize) {
            throw new PosofGetException("get(int pos)" +
                    "pos位置不合法");
        }
        return this.elem[pos];
    }

    private boolean isEmpty() {
        // 有效数据个数为0，就是为空
        return this.usedSize == 0;
    }

    // 给 pos 位置的元素设为【更新为】 value
    public void set(int pos, int value) throws PosofSetException{
        // 先得判断这个 pos 位置是否合法
        if (pos < 0 || pos >= this.usedSize) {
            throw new PosofSetException("set(int pos, int value)" +
                    "要修改的位置不合法");
        }
        this.elem[pos] = value;
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) throws PosofRemoveException{
        int pos = indexOf(key); // 下标
        if (pos < 0) {
            throw new PosofRemoveException("remove(int key)" +
                    "没有您要删除的数据");
        }
        for (int i = pos; i < this.usedSize - 1; i++) {
            // 后一个位置往前覆盖
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

    // 获取顺序表长度
    public int size() {
        return this.usedSize;
    }

    // 清空顺序表
    public void clear() {
        // 由于存放的是基本数据类型，直接清空即可
        this.usedSize = 0;
        // 如果存放的是引用数据类型就得通过for循环遍历把数组的内容置为null
        // 注意：如果直接把数组置为null的话，就会存在安全问题，而且源码也是遍历的方式
    }
}

异常：

PosofAddException：

public class PosofAddException extends RuntimeException{
    public PosofAddException() {

    }
    public PosofAddException(String msg) {
        super(msg);
    }
}

PosofGetException：

public class PosofGetException extends RuntimeException{
    public PosofGetException() {

    }
    public PosofGetException(String msg) {
        super(msg);
    }
}

PosofSetException：

public class PosofSetException extends RuntimeException{
    public PosofSetException() {

    }
    public PosofSetException(String msg) {
        super(msg);
    }
}

PosofRemoveException：

public class PosofRemoveException extends RuntimeException{
    public PosofRemoveException() {

    }
    public PosofRemoveException(String msg) {
        super(msg);
    }
}

分析Java 8 的 ArrayList 的源码

实现了咱们自己写的顺序表了之后，就该来看Java本身的源码是怎么写的以及与我们的有什么不同？（注意：由于Java 17封装性太强，不好观看源码，因此下面的源码来自Java 8。）

字段：

elementData 就是我们自己实现的 elem 数组。

size 就是 usedSize ，也就是这个数组的有效元素的个数。

构造方法：

Java 8 实现的顺序表有三个构造方法。

带有一个 int 类型的参数的构造方法：

不带参数的构造方法：

带一个 Collection 类型的参数的构造方法：

下面的是其源码：

首先，我们得知道Collection 到底是这个啥？

根据上面这个图可以得知：Collection 是一个接口。

上面的参数先不看泛型，那就是Collection c 这个意味着只要实现了Collection 接口，就可以被当成实参传过来。而从上图的关系可知：ArrayList 继承了 AbstractLIst 这个抽象类，并且实现了LIst这个接口，而 LIst 这个接口拓展了 Collection 这个接口的功能。也就意味着 ArrayList 这个类实现了 Collection 这个接口。那么 ArrayList 就可以被当成参数传过来。

接下来，就是了解 <? extends E> ，？就可以当成是被传过来的 ArrayList 中的泛型，也就是说被传过来的 ArrayList 中的泛型要是 E 或者 E的子类。例如：

了解了这些，我们就来看源码吧。这个源码的大概意思是把传入的 ArrayList 中的元素给全部拷贝到原来的 ArrayList 的后面。

ArrayList本身的扩容机制和分配内存机制

既然我们在创建一个顺序表的时候，原本是空，那么当我们去增加元素的时候，扩容的机制又是如何呢？

上面是分析过程（可忽略），总之，得出了下面这个结论：

当顺序表为空时，我们如果去增加元素，就会初始化一个大小10的数组。并且数组在满了之后，会按照1.5倍的扩容方式来扩容。如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容。

ArrayList常见操作

ArrayList常用方法
boolean add(E e)	尾插e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	将c 中的元素进行尾插
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个o
E get(int index)	获取下标index位置元素
E set(int index, E element)	将下标 index 位置元素改为 element
void clear()	清空
boolean contains(Object o）	判断是否在顺序表中
int indexOf(Object o)	返回第一个o所在下标
int lastlndexOf(Object o)	返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex)	截取部分list

大部分方法，我们都很熟悉。因此这里只展示 addAll()方法和 subList 方法。

addAll () 方法可以实现 ArrayList 的带Collection 类型的参数的构造方法。

从上面打印的结果可以看出来，ArrayList 是重写了toString 方法的。

从这里我们就可以看出来，被分割的数组应该是下面这样：

ArrayList的遍历

普通for循环遍历

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i)+" ");
        }
    }
}

for-each遍历

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        for (Integer x : arrayList) {
            System.out.print(x+" ");
        }
    }
}

toString方法遍历

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        System.out.println(arrayList.toString());
    }
}

迭代器遍历

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        // 调用iterator方法生成一个迭代器，用Iterator<E>来接收
        Iterator<Integer> integerIterator = arrayList.iterator();
        // 如果下一个元素有值话，就进入while循环，并且打印下一个值，最后自己往后走
        while (integerIterator.hasNext()) {
            System.out.print(integerIterator.next()+" ");
        }
    }
}

只要是实现了 Iterator 接口就可以使用迭代器的方式来遍历。就是下面这张图：

好啦！本期数据结构之ArrayList与顺序表（上）的学习就到此结束啦！我们下一期再一起学习吧！