动态数组

• 动态数组的ADT实现
• 实现动态数组代码

动态数组的ADT实现

• 添加元素: add(int index, E e)
• 向头部添加元素: addFirst(E e)
• 向尾部添加元素: addLast(E e)
• 扩容: resize(int i)
• 设置(修改)固定位置的元素: set(int index, E e)
• 获取指定位置的元素: E get(int index)
• 是否包含元素: int contains(E e)
• 移除元素: E remove(int index)
• 移除头部元素: removeFrist()
• 移除尾部元素: removeLast()

---

实现动态数组代码

public class MyArrayList<E> {

    private E[] data;
    private int size;
    private int defaultSize = 10;
    private int expansionFactor = 2;

    public MyArrayList () {
        this.data = (E[]) new Object[defaultSize];
        this.size = 0;
    }

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

    public void add(int index, E e){

        // 判断添加的索引是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add element`s index is illegal");
        }

        // 判断是否需要扩容
        if (size >= this.data.length) {
            resize(this.data.length * expansionFactor);
        }

        // 挪动元素位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 添加元素
        data[index] = e;
        size++;
    }

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

    public void addLast(E e){
        add(size,e);
    }

    /**
     * 容量调整机制
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < size; i++) {
            newData[i] = this.data[i];
        }
        data = newData;
    }

    /**
     * 设置(修改)固定位置的元素
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("element`s index is illegal");
        }
        data[index] = e;
    }

    /**
     * 获取指定位置的元素
     * @param index
     * @return
     */
    public E get (int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("element`s index is illegal");
        }

        return data[index];
    }

    /**
     * 获取最后一个元素
     * @return
     */
    public Object getLast() {
        return get(size - 1);
    }

    /**
     * 是否包含元素
     * @param e
     * @return
     */
    public int contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i] == null) {
                return 1;
            }
            if (data[i] == e) {
                return 1;
            }
        }
        return -1;
    }

    /**
     * 查找元素在数组中的第一个出现的位置索引
     * @param e
     * @return
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i] == e) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找指定元素在数组中的位置
     * @param e
     * @return
     */
    public int[] findAll(E e) {
        StringBuilder element = new StringBuilder();

        for (int i = 0; i < size; i++) {
            if (data[i] == e) {
                element.append(i + ",");
            }
        }

        if (element.length() < 0) {
            throw new IllegalArgumentException("数组中不存在[" + e + "]这个元素");
        }

        String[] split = element.toString().split(",");

        int[] indexs = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            indexs[i] = Integer.valueOf(split[i]);
        }
        return indexs;
    }

    /**
     * 移除指定索引的元素
     * @param index
     * @return
     */
    public E remove(int index) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("element`s index is illegal");

        E tempData = get(index);

        // 移动数组元素
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }

        size--;
        data[size] = null; // help gc

        // 判断是否需要缩容, Lazy的方式进行缩容
        // this.data.length / 2 != 0 是为了 当data.length为1的时候, 1/2 = 0
        if (size == this.data.length / 4 && this.data.length / 2 != 0) {
            resize(this.data.length / 2);
        }

        return tempData;
    }

    /**
     * 移除头部元素
     * @return
     */
    public E removeFrist(){
        return remove(0);
    }

    /**
     * 移除尾部元素
     * @return
     */
    public E removeLast(){
        return remove(size-1);
    }

    /**
     * 移除所有指定元素
     * @param e
     * @return
     */
    public void removeAll(E e) {
        int[] all = findAll(e);
        if (all.length < 0) {
            throw new IllegalArgumentException("element is doesn't exist");
        }

        for (int i = 0; i < all.length; i++) {
            remove(i);
        }
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpety() {
        return size == 0 ? true : false;
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

    @Override
    public String toString() {
        return "MyArrayList{" +
                "data=" + Arrays.toString(data) +
                ", size=" + size +
                ", defaultSize=" + defaultSize +
                '}';
    }

}

以上为动态数组的实现过程, 并且可以用来实现以数组为基础的其他一维数据结构, 比如栈, 队列, 集合(Set), 映射(Map)等....