数组

[bitfishxyz]

数组

我是学习Python和JS入门编程的，在学习数据结构的阶段，就在掉到坑里了。原因之一就是我很难理解数组这种数据结构。

在Python中的List或者JS中的Array，它们其实是一个非常复杂包装类，隐藏了真正的数组的特征，让我对数组这种结构产生了很多误解。

导致我在小白的时候一直有疑问：

• Array.sort() 不是可以直接让一个数组有序了吗，为什么还要学习排序算法呢?
• Array.pop() .push() .insert() 不是可以直接的修改数字吗，为什么还有什么这个、那个的时间复杂度？

好吧，现在看来这些想法有点可笑，为了避免有些同学有和我一样的误区，我们整理了数组这个结构的几个特点。

一个数组占用内存是连续的

这点很好理解，作为一种线性的数据结构，它需要占用连续的内存

数组中每个元素应该占用同样长度的内存

其实在C、Java这种偏底层的静态编程语言中，都是要求数组中的每个元素是同一个类型的。为什么有这样要求？

这是为了数组的随机访问。

假设一个数组中每个元素都是占用8个字节的内存，其中第一个元素在内存中的起始地址是0000 aaaa，那么请问这个数组中第7个元素的内存起始地址是多少？

很简单，应该是 0000 aaaa 向后数56个字节， 是这个地址0000 aae2，就是这么简单。

然是如果如果数组中允许每个元素占用不同大小的内存，会反生什么情况呢？ 但是你是我们就无法做到随机访问了。

这个有一个推论，一致第一个元素的第一，和某一元素的索引，就可以推断出
它的地址。

CPU访问内存中每个地址消耗的时间相同

这就是由计算机的构造原理决定了，访问@0000 0000 和 @ffff ffff 消耗的时间一样。
具体的原理我也不是很清楚，反正就是什么总线啊什么乱七八糟的概念。但是结论很很重要。

这个就是说，我们访问数组中第一个元素和最后一个元素消耗的时间是一样。。。。

结合上面一点，我们就是说数组支持随机访问。

数组容量固定

一但创建了一个数组，它的容量就确定了。
[1, 2, 3], 那么它在内存中就是占用12个字节。不能变化。

如果我想删除2这个元素，怎么把？
不能使不能直接删除，然后变成[1, 3]这样的，但是我们有三种办法

• 设置为0值， [1, 0, 3]
• [1, 3, 0]
• 创建一个新的数字，然后把1，3复制过去，变成[1, 3]

只有这三种方法。

小节

上面就是对数组这种数据结构的理解。然后就是学习数据结构的时候
建议使用C Java，不建议使用JS，Python

[bitfishxyz]

Java实现

Java中就是原生数组，我们就以Java语言为例，来测试下上面的步骤

这是我们数组

        String[] arr =  new String[3];
        arr[0] = "a";
        arr[1] = "b";
        arr[2] = "c";

现在我们想把索引为1的元素的值设置为"d"，我们该怎么做呢？

很简单，利用数组的随机访问原理，我们可以直接修改

        // 修改元素
        arr[1] = "d";

如果我们想删除索引为2的元素，我们该怎么办呢？
显然，数组的创建，它的大小不能再修改，我们只能重新创建一个数组

        // 删除索引为2的元素
        String[] arr2 = new String[arr.length - 1];
        arr2[0] = arr[0];
        arr2[1] = arr[1];

这样就行了。我们要创建一个新的数组，然后把原来数组的其他元素复制到新的数组中，
那么我们就是删除了原来的数组了。
现在我们可以把arr2看做是arr删除了一个元素后的新状态。

同理，如果我们想在索引为0的位置添加一个新的元素，我们可以

        // 在索引为0的位置添加一个元素e
        String[] arr3 = new String[arr2.length + 1];
        arr3[0] = "e";
        arr3[1] = arr2[0];
        arr3[2] = arr2[1];

长度为3的，如果想对它进行增删给查旧的按照我们执勤啊说的步骤，
所以我们可以写一个包装类，来包装上面的操作。

不过我们可以卡看到，Java的原生数组太底层了，用的时候不方便，
所以我们可以写一个包装类，来方便我们增删改查

通过Array类来包装

import lombok.Getter;
import lombok.ToString;

@ToString
public class Array<E> {
    private static int increaseCapacityTimes = 2;

    /**
     * 实际的容量
     */
    @Getter
    private int size;

    /**
     * 底层数组
     */
    private E[] data;

    public Array(int capacity){
        data = (E[])new Object[capacity];
    }
    public Array(){
        this(10);
    }

    /**
     * 底层数组的最大容量
     */
    public int getCapacity(){
        return data.length;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 添加底层数组容量
     */
    private void increaseCapacity(){
        E[] newData = (E[])new Object[data.length * increaseCapacityTimes];
        for (int i = 0; i < data.length; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 降低底层数组容量
     */
    private void decreaseCapacity(){
        E[] newData = (E[])new Object[data.length / 2 + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 修改数组的容量
     */
    private void resize(){
        if (size == data.length){
            increaseCapacity();
        }
        if (size <= data.length / 3 && data.length > 20){
            decreaseCapacity();
        }
    }

    /**
     * 假设数组为 [11, 22, 33, 44]
     * insert(99, 2)后，数组变为
     * [11, 22, 99, 33, 44]
     * 原始数组索引为[2, length)都要向后移动
     * 新插入原始的索引为2
     * @param e
     * @param index: 可以取到size
     */
    public void insert(E e, int index){
        resize();
        if (index > size || index < 0) {
            throw new IllegalArgumentException("索引应该在[0, size]之间");
        }
        for (int i = size; i > index; i--) {
            data[i] = data[i-1];
        }
        data[index] = e;
        size++;
    }
    public void addLast(E e){
        insert(e, size);
    }
    public void addFirst(E e){
        insert(e, 0);
    }
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    /**
     * 寻找当前元素的位置，如果不存在就返回-1
     * @param e
     * @return
     */
    public int indexOf(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除指定索引位置的元素，并将这个元素的值返回
     * @param index
     * @return
     *
     * data[size]这个位置的值还在，但是没有关系的
     */
    public E remove(int index){
        assertIndex(index);
        resize();
        E currentValue = data[index];
        for (int i = index; i < size - 1 ; i++) {
            data[i] = data[i + 1];
        }
        size--;
        // 释放资源
        data[size] = null;
        return currentValue;
    }
    public E removeLast(){
        return remove(size - 1);
    }
    public E removeFirst(){
        return remove(0);
    }

    public boolean removeElement(E e){
        int index = indexOf(e);
        if (index != -1) {
            remove(index);
            return true;
        }
        return false;
    }

    /**
     * 获得底层数组索引为index的位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        assertIndex(index);
        return data[index];
    }
    public E getLast(){
        return get(size - 1);
    }
    public E getFirst(){
        return get(0);
    }

    public void set(E e, int index){
        assertIndex(index);
        data[index] = e;
    }

    private void assertIndex(int index){
        if (index >= size || index < 0) {
            throw new IllegalArgumentException("索引应该在[0, size)之间");
        }
    }
}