动态数组

动态数组
- API介绍
- 方法实现

API介绍

数组是一种根据下标操作的数据结构，它的查询速度很快，但是它有缺点，那就是数组的容量一旦在创建时确定，就不能进行更改，所以为了克服这一缺点，我们实现一个自己的数组，并除此以外，还会实现一些方法，包括以下

add(int index, E e)
- 向指定index添加元素e
get(int index)
- 获得指定index的元素
remove(int index)
- 删除指定index的元素并返回该元素
set(int index, E e)
- 更改index处的元素为e
getSize()
- 返回数组中元素的个数
contains(E e)
- 查询数组是否包含元素e
isEmpty()
- 查看数组是否为空(是否有元素)
find(E e)
- 返回数组中元素e第一次出现的index，若没有元素e，则返回-1

新建一个Array类，它含有两个私有成员变量

E[] data
- 用以保存数据
int size
- 用以记录数组中元素的个数

除此以外还有两个构造方法

Array(int capacity)
- 设定数组的容量
Array()
- 容量默认为10

public class Array<E> {
    private E[] data;
    private int size;
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }
    public Array() {
        this(10);
    }
}

现在我们来实现上面提到的方法。

方法实现

首先来实现getSize()方法，这个是返回数组元素的个数的，我们直接返回size即可

public int getSize() {
    return size;
}

isEmpty()是为了查看数组中是否还有元素，如果size为0的话说明数组为空，所以我们返回size == 0即可

public boolean isEmpty() {
    return size == 0;
}

现在来实现add(int index, E e)方法，该方法的实现是将index后面的元素都向后移动一位，然后在index处插入元素e
动态数组 - 图1

public void add(int index, E e) {
    //对inex进行验证 如果不符合规范则抛出异常
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("参数错误");
    }
    //将元素向后移动
    for (int i = size; i > index; i--) {
        data[i] = data[i - 1];
    }
    //在index处插入元素e
    data[index] = e;
    //数组中元素个数+1
    size++;
}

根据这个方法，我们可以很快的实现addFirst(E e)和addLast(E e)方法，这两个方法一个是在数组头添加元素，一个是在数组的末尾添加一个元素

public void addLast(E e) {
    //在index = size处添加元素 即在数组末尾添加一个元素
    add(size,e);
}
public void addFirst(E e) {
    //在index = 0处添加一个元素 即在数组头添加一个元素
    add(0,e);
}

下面来实现remove(int index)方法，该方法是删除index处的元素，并将该元素返回，以添加的操作相反，删除是将后面的元素向前移动，覆盖掉index处的元素即可删除
动态数组 - 图2

public E remove(int index) {
    //参数检查
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("参数错误");
    }
    //获得index处的元素用以返回
    E e = data[index];
    //将元素从后向前移一个
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i+1];
    }
    //数组中元素个数-1
    size --;
    //返回删除的元素
    return e;
}

同理，根据这个方法我们可以快速的实现removeLast()和removeFirst()方法

public E removeLast() {
    return remove(size -1);
}
public E removeFirst() {
    return remove(0);
}

我们可以添加一个删除指定元素的方法removeElement(E e)，我们会遍历数组，如果发现有元素等于该元素，那么删除该元素并退出方法，所以这个方法只删除第一个元素e，并不是数组所有的元素e

public void removeElement(E e) {
    //遍历数组
    for (int i = 0; i < size; i++) {
        //如果找到等于该元素的元素
        if (e.equals(data[i])) {
            //删除该元素
            remove(i);
            //退出方法
            return;
        }
    }
}

下面实现contains(E e)方法，这个方法的思路同删除指定元素相似，遍历数组，如果找到元素与指定元素相同，那么返回true，如果遍历完数组还没有找到与之相等的元素，那么返回false

public boolean contains(E e) {
    //遍历数组
    for (int i = 0; i < size; i++) {
        //如果找到元素，那么返回true
        if (data[i].equals(e)) {
            return true;
        }
    }
    //如果遍历完所有数组没有找到，那么返回false
    return false;
}

find(E e)方法的实现也是遍历数组，如果找到了元素，那么返回下标，如果遍历完数组都没有找到，那么返回-1

public int find(E e) {
    //遍历数组
    for (int i = 0; i < size; i++) {
        //找到元素则返回下标
        if (data[i].equals(e)) {
            return i;
        }
    }
    //如果遍历完数组都没有找到，返回-1
    return -1;
}

下面实现get(int index)和set(int index, E e)，这两个方法的实现及其简单，直接上代码

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("参数错误");
    }
    return data[index];
}
public void set(int index, E e) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("参数错误");
    }
    data[index] = e;
}

我们可以根据get方法实现getLast()和getFirst()方法

public E getFirst() {
    return get(0);
}
public E getLast() {
    return get(size - 1);
}

现在我们已经实现了API中提到的所有的方法，但是我们还是没有解决数组容量固定的问题，为了解决这个问题，我们需要实现一个resize(int newCapacity)，它的作用是改变数组的容量大小，这样当数组的容量不足时，我们调用该方法就可以将数组进行扩容，或者当数组中有大量空间空闲时，我们可以缩小数组的容量，代码如下

private void resize(int newCapacity) {
    //创建一个新容量的数组
    E[] temp = (E[]) new Object[newCapacity];
    //将数组中的数据全部放入新数组中
    for (int i =0; i < size; i++) {
        temp[i] = data[i];
    }
    //改变数组指针指向
    data = temp;
}

现在我们改变add(int index, E e)和remove(int index)方法，我们会在添加元素和删除元素时检查数组的容量，以便对数组进行扩容或者缩容

public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("参数错误");
    }
    //如果数组容量满了 那么将数组的容量扩为原来的两倍
    if (size == data.length) {
        resize(data.length * 2);
    }
    for (int i = size; i > index; i--) {
        data[i] = data[i - 1];
    }
    data[index] = e;
    size++;
}

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("参数错误");
    }
    E e = data[index];
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i+1];
    }
    size --;
    //如果数组中的元素个数为数组容量的1/4，那么容量变为原来的1/2
    //思考一下为什么是1/4 提示：复杂度震荡
    if (size == data.length/4) {
        resize(data.length/2);
    }
    return e;
}

为了方便的打印Array类，我们重写toString()方法如下

public String toString() {
    StringBuilder str = new StringBuilder();
    str.append("size " + size);
    str.append(" capacity " + data.length);
    str.append("\n[");
    for (int i = 0; i < size; i++) {
        if (i == size - 1) {
            str.append(data[i].toString());
        } else {
            str.append(data[i].toString() + ", ");
        }
    }
    str.append("]");
    return str.toString();
}

至此，我们已经完全实现了Array，它的容量没有限制，并且提供了很多的方法供用户调用，我们将使用该类来实现其它的基本的数据结构。下面贴出完整的代码

public class Array<E> {
    private E[] data;
    private int size;
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }
    public Array() {
        this(10);
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public void addLast(E e) {
        add(size,e);
    }
    public void addFirst(E e) {
        add(0,e);
    }
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("参数错误");
        }
        if (size == data.length) {
            resize(data.length * 2);
        }
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = e;
        size++;
    }
    public E removeLast() {
        return remove(size -1);
    }
    public E removeFirst() {
        return remove(0);
    }
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数错误");
        }
        E e = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i+1];
        }
        size --;
        if (size == data.length/4) {
            resize(data.length/2);
        }
        return e;
    }
    public void removeElement(E e) {
        for (int i = 0; i < size; i++) {
            if (e.equals(data[i])) {
                remove(i);
                return;
            }
        }
    }
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }
    private void resize(int newCapacity) {
        E[] temp = (E[]) new Object[newCapacity];
        for (int i =0; i < size; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数错误");
        }
        return data[index];
    }
    public E getFirst() {
        return get(0);
    }
    public E getLast() {
        return get(size - 1);
    }
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数错误");
        }
        data[index] = e;
    }
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("size " + size);
        str.append(" capacity " + data.length);
        str.append("\n[");
        for (int i = 0; i < size; i++) {
            if (i == size - 1) {
                str.append(data[i].toString());
            } else {
                str.append(data[i].toString() + ", ");
            }
        }
        str.append("]");
        return str.toString();
    }
}