数据结构-数组-特性及代码实现

学习笔记：数组的基本特性，对比容器与数组的利弊，将数组封装为ArrayList的代码实现。

1. 数组的基本特性

• 随机访问
  • 线性表
  • 连续的内存空间和相同类型的数据
• 连续存储
• 增删低效
  • 需要大量的数据搬移工作

在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多。比如：数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想。

JVM标记清除算法：
大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。
不足：
1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。
2.空间问题。会产生不连续的内存空间碎片。

2. 容器能否完全替代数组

针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector。

ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。

不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码，你会发现，相比之下，事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

当然，有些时候，用数组会更合适些。

1. Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
2. 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
3. 此外，当要表示多维数组时，用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList<object>> array。

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

3. 手动将数组封装为ArrayList的代码实现

将Array封装为ArrayList，最主要的目的就是为了屏蔽扩容、缩容的复杂性，让其自动地去扩容、缩容。这也是我们把ArrayList称为变长数组的原因。

在JDK源码中，扩容、缩容在方法trimToSize()中实现，它在数组存在空余位置时，缩容至与实际元素个数一致。而在我的实现中，选择缩容至已有元素的二倍大小。扩容、缩容操作在添加、删除元素的方法中实现。

另外，在编写代码时我发现，System.arraycopy()的方法参数虽然为index，但是实际使用时，该方法的参数可以==array.length，虽然这样已经越界1个元素，但只要最后一个参数（待复制元素个数）为0，就不会抛异常，也不会去访问越界的位置。其它情况都会抛异常。我猜想这样的好处是对于删除ArrayList最后一个元素时，不用单独讨论（调用了System.arraycopy()方法，此时的index+1是越界的，但由于最后一个参数size - index - 1 == 0，不会抛异常）。

MyArrayList.java代码实现

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author AnthonyCJ
 * @version 1.0
 * @description 自己手动实现ArrayList
 * @date 2022/12/01 9:52
 */
public class MyArrayList<E> implements Iterable<E> {
    // 真正存储数据
    private E[] data;
    // 记录当前数组中元素的个数
    private int size;
    // 默认初始容量
    private static final int INIT_CAP = 1;

    public MyArrayList() { this(INIT_CAP); }

    public MyArrayList(int initCapacity) {
        data = (E[]) new Object[initCapacity];
        size = 0;
    }

    /***** 增 *****/

    // 在数组尾部添加一个元素
    public void addLast(E e) {
        int cap = data.length;
        // 检验是否需要扩容
        if (size == cap) {
            resize(2 * cap);
        }
        // 在尾部插入元素
        data[size] = e;
        size++;
    }

    // 在 index 索引的位置添加一个元素 e
    public void add(int index, E e){
        // 检查索引越界（只能确定索引位置是否合法，与当前数组元素个数有关，与数组容量无关）
        checkPositionIndex(index);
        // 插入前检查数组容量是否够用，如果数组已满则扩容
        int cap = data.length;
        if (size == cap) {
            resize(2 * cap);
        }

        // 搬移数据 data[index..] -> data[index + 1]
        System.arraycopy(data, index,
                data, index + 1,
                size - index);
        // 插入新的元素
        data[index] = e;
        // 计数
        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    /***** 删 *****/

    // 删除数组的最后一个元素并返回
    public E removeLast() {
        // 1. 考虑数组是否为空
        if (size == 0) {
            throw new NoSuchElementException();
        }
        // 2. 考虑是否是否可以缩容
        int cap = data.length;
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[size - 1];  // 暂存待删除的元素

        // 3. 删除最后一个元素
        data[size - 1] = null;  // 使remove的元素被垃圾回收
        size--;

        return deletedVal;
    }

    // 删除 index 位置的元素并返回
    public E remove(int index) {
        // 检查索引越界
        checkElementIndex(index);

        // 考虑可否可以缩容
        int cap = data.length;
        if (size == cap / 4) {
            resize(cap / 2);
        }

        // 数据搬移
        E deletedVal = data[index];
        System.arraycopy(data, index + 1,
                data, index,
                size - index - 1);

        data[size - 1] = null;
        size--;

        return deletedVal;
    }


    /***** 查 *****/

    // 返回 index 位置对应的元素
    public E get(int index) {
        // 检查索引越界
        checkElementIndex(index);

        return data[index];
    }



    /***** 改 *****/
    // 将索引 index 的元素改为 e 并将旧的元素返回
    public E set(int index, E e) {
        checkElementIndex(index);
        E oldVal = data[index];
        data[index] = e;
        return oldVal;
    }

    /***** 工具函数 *****/

    public int size() { return size;}

    public boolean isEmpty() { return size == 0; }

    /***** 私有函数 *****/

    private boolean isElementIndex(int index) { return index >= 0 && index < size; }

    private boolean isPositionIndex(int index) { return index >=0 && index <= size; }

    /*
     * 检查 index 索引位置是否可以存在元素
     */
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    /*
     * 检查 index 索引位置是否可以添加元素，用于插入操作
     * 对应的位置可以理解是数组元素间隔的缝隙，所以比元素个数多一个
     * 插入时要保证插入后数组中的数据依然是连续存储的，中间不能有NULL值，所以用size判断而不是length
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    // 将数组 data 的容量改为 newCap
    private void resize(int newCap) {
        // 若当前数组存储的元素个数大于 newCap，则不做修改，防止数据丢失
        if (size > newCap) {
            return;
        }
        E[] tempData = (E[]) new Object[newCap];

        for (int i = 0; i < size; i++) {
            tempData[i] = data[i];
        }
        // System.arraycopy(data, 0, tempData, 0, size);
        data = tempData;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int p = 0;

            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public E next() {
                return data[p++];
            }
        };
    }

    private void display() {
        System.out.println("siz = " + size + ", cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }

    public static void main(String[] args) {

        /*
        // 测试System.arraycopy方法
        //arr.remove(2);
        System.arraycopy(arr.data, 3, arr.data, 2, 0);
        arr.display();*/

        // 初始容量设置为 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // 添加 5 个元素
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1, 9);
        arr.display();
        arr.addFirst(100);
        arr.display();
        int val = arr.removeLast();

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }
}