自己实现一个动态数组

发布于 2021-10-27  739 次阅读


好久之前就了解过动态数组了,这次自己来实现一个。

先上代码

    /**
     * 实现一个动态数组
     *
     * @author 杨深建
     */
public class ArrayImpl<T> implements ArrayInterface<T> {

    private int size; // 表示的是数组的大小
    private T[] data; // 定义一个数组

    public ArrayImpl(int capciaty) {
        data = (T[]) new Object[capciaty]; // 创建一个数组
        size = 0;
    }

    public ArrayImpl() {
        this(10);
    }

    /**
     * 获取数组的容量
     *
     * @return
     */
    @Override
    public int getCapciaty() {
        return data.length;
    }

    /**
     * 获取数组的大小
     *
     * @return
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断数组是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向数组的指定位置添加元素。
     *
     * @param index
     * @param element
     */
    @Override
    public void add(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        // 2、判断是否为满
        if (size == data.length) {
            resize(size*2);  //进行扩容操作
        }
        // 3、进行插入操作,数据迁移
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        // 4、进行赋值插入
        data[index] = element;
        // 5、元素个数加1
        size++;
    }

    /**
     * 进行扩容操作
     * @param i
     */
    private void resize(int index) {
        T  [] data2=(T[]) new  Object[index];
        for(int i=0;i<size;i++){  //进行赋值操作
            data2[i]=data[i];
        }
        data=data2;
    }

    /**
     * 在数组的头部插入元素
     */
    @Override
    public void addFirst(T element) {
        add(0, element);
    }

    /**
     *
     * 在数组中的尾部插入元素
     */
    @Override
    public void addLast(T element) {
        add(size, element);
    }

    /**
     * 获取index索引位置的元素
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        return data[index];
    }

    /**
     * 修改index索引位置的元素为e
     *
     * @param index
     * @param element
     */
    @Override
    public void set(int index, T element) {
        // 1、判断index 是否合法。
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        data[index] = element;
    }

    /**
     * 显示所有的数组元素
     */
    @Override
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(data[i]);
        }
    }

    /**
     * 查找数组中是否有元素e
     */
    @Override
    public boolean contains(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
     */
    @Override
    public int find(T e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 从数组中删除index位置的元素, 返回删除的元素
     */
    @Override
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index  is  illegal");
        }
        T res = data[index]; // 获取结果
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i]; // data[index]
        }
        size--;  //进行元素个数-1
        if(size == data.length/4 && data.length/2!=0)  resize(data.length/2);  //如果元素的个数小于容量的1/4 ,我们就进行缩容操作 到容量的1/2
        return res;
    }

    /**
     * 从数组中删除第一个元素, 返回删除的元素
     */
    @Override
    public T removeFirst() {
        T res = remove(0);
        return res;
    }

    /**
     * 从数组中删除最后一个元素, 返回删除的元素
     */

    @Override
    public T removeLast() {
        T res = remove(size - 1);
        return res;
    }

    /**
     * 从数组中删除元素e
     */
    @Override
    public void removeElement(T element) {
        int index = find(element);
        if (index != -1) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        //使用 线程不安全的StringBuilder 效率更高
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}


说明:我所采用的是for循环复制元素扩容,但这种扩容是有一些问题的
缺陷: 拷贝一部分元素需要计算索引,比较复杂
2.System.arraycopy()
3.Arrays.copyOf扩容

* 观察copyOf方法的源码:

* public static int[] copyOf(int[] original, int newLength) {

* int[] copy = new int[newLength];

* System.arraycopy(original, 0, copy, 0,

* Math.min(original.length, newLength));

* return copy;

* }

4.利用Object类中一个 clone 方法,该方法是真正意义上的复制数组(默认浅拷贝,如果覆写则是深拷贝)

复杂度的震荡

当同时思考addLast和removeLast操作的时候:

假如调用addLast触发resize扩容后调用removeLast显然也会调用resize进行缩容,这个操作如果反复执行就会导致复杂度的震荡,所以代码中removeLast方法中,并没有像addLast中那样直接让data.length/2,而是当数组内的元素等于四分之一容量的时候,才会执行缩容的操作,就可以解决复杂度的震荡

if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }

她喜欢所以就做咯