动态数组的实现

定义

1. 在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识。

2. 因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来。

3. 知道了数组的数据其实地址BaseAddress,就可以由公式BaseAddress+ i * size 计算出索引i元素的地址。

?* i 即索引，在java，C等语言都是从0开始。

* size 是每个元素占用字节，例如int 占4，double 占8.

性能

空间占用

java中数据结构为：

* 8字节markword

* 4字节class指针（压缩class指针的情况）

* 4 字节数组大小（决定了数组最大容量 2 ^ 32）?

* 数组元素 + 对齐字节（java中所有对象都是8字节1的整数倍 ^12? , 不足的要用对齐字节补足）

动态数组

package com.ma.test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/2119:51
 * @function
 * @comment
 */
public class DynamicArray implements Iterable<Integer> {

    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = new int[capacity];

    public void addLast(int element) {
        add(size, element);
    }

    public void add(int index, int element) {

        checkAndGrow();

        if (index >= 0 && index < size) {
            // 向后挪动，空出待插入位置
            System.arraycopy(array, index, array
                    , index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {

        if (size == 0) {
            array = new int[capacity];
            // 容量检查
        } else if (size == capacity) {
            // 进行扩容
            capacity += capacity >> 1;

            int[] newArray = new int[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
    }


    public int get(int index) {
        return array[index];
    }

    public void foreach(Consumer<Integer> consumer) {
        {
            for (int i = 0; i < size; i++) {
                consumer.accept(array[i]);
            }
        }
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

            @Override
            public boolean hasNext() {
                return i < size; // 有没有下一个元素
            }

            @Override
            public Integer next() {  // 并移动到下一个元素
                return array[i++];
            }
        };
    }

    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }


    public int remove(int index) {
        int removed = array[index];

        if (index < size - 1) {
            System.arraycopy(array, index + 1, array,
                    index, size - index - 1);
        }
        size--;
        return removed;
    }
}

测试

package com.ma.test;

/**
 * @author Mtz
 * @version 1.0
 * @2023/12/229:05
 * @function
 * @comment
 */
public class Test {
    public static void main(String[] args) {
        DynamicArray dynamicArray = new DynamicArray();
        dynamicArray.addLast(1);
        dynamicArray.addLast(2);
        dynamicArray.addLast(3);
        dynamicArray.addLast(4);

        dynamicArray.foreach((element)->{
            System.out.println(element);
        });

        for (Integer element : dynamicArray){
            System.out.println(element);
        }

        dynamicArray.stream().forEach(element->{
            System.out.println(element);
        });
    }
}