动态数组

数组应该是我们在java中最先接触的数据结构了，在本章节中，我们尝试自己重新封装实现动态数组。

一、自定义数组及构造

public class Array {
    private int[] data;
    private int size;

    /**
     * 带参构造方法
     *
     * @param capacity
     */
    public Array(int capacity) {
        data = new int[capacity];
        size = 0;
    }

    /**
     * 无参构造，默认初始化容量为10
     */
    public Array() {
        this(10);
    }

    /**
     * 获取实际长度
     *
     * @return
     */
    public int getSize() {
        return size;
    }

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

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

二、插入方法

在指定位置插入元素，判断是否越界以及索引是否合法，在插入后记得维护size变量

/**
     * 在数组的第一个位置插入
     *
     * @param element
     */
    public void addFirst(int element) {
        add(0, element);
    }

    /**
     * 在数组末尾插入
     * @param element
     */
    public void addLast(int element) {
        add(size, element);
    }

    /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        //判断是否超出容量
        if (size == data.length) {
            throw new IllegalArgumentException("Add fail ,array is full");
        }
        //判断index是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is illegal ");
        }
        //从index开始元素依次后移
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        //将元素插入到指定位置
        data[index] = element;
        //维护size变量
        size++;
    }

三、查询、修改

/**
     * 获取index位置的元素
     *
     * @param index
     * @return
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        return data[index];
    }

    /**
     * 修改index位置的元素为element
     *
     * @param index
     */
    public void set(int index, int element) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal");
        }
        data[index] = element;
    }

    /**
     * 重写toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        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();
    }
}

四、包含、搜索与删除

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

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

    /**
     * 从数组中删除index位置的元素, 返回删除的元素
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Index is illegal");
        }
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        return data[index];
    }

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

    /**
     * 从数组中删除最后一个元素, 返回删除的元素
     *
     * @return
     */
    public int removeLast() {
        return remove(size - 1);
    }

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

    }