数据结构篇01、动态数组

我们通过使用java中的静态数组封装一个动态数组，底层的核心原理类似于java标准库中的ArrayList；

1、构造函数与常规函数

定义一个静态数组data和一个容量size；

定义三个构造方法，一个传入容量capacity，一个无参构造方法默认容量为10，最后一个传入另一个数组作为参数；

swap函数用于交换数组中i和j索引处的元素；

public class Array<E> {

    private E[] data;
    private int size;

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }
    
    //将数组作为构造函数的参数
    public Array(E[] arr){
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];
        size = arr.length;
    }
    
    //交换数组中索引i和j位置的元素
    public void swap(int i, int j){

        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }
    、、、
}
复制代码

定义三个常规函数，分别是获取数组的容量、获取数组元素个数、判断数组是否为空；

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

// 获取数组中的元素个数
public int getSize(){
    return size;
}

// 返回数组是否为空
public boolean isEmpty(){
    return size == 0;
}
复制代码

2、添加元素

定义添加元素的函数，在index索引处插入新元素e；需要注意的地方是当数组满了的时候，需要动态扩容，resize函数如下所示；在数组的index索引处插入元素，需要把index后的元素全部往后移动一位，因此时间复杂度是O(n);

同时定义addLast和addFirst表示在数组尾和数组头添加元素；

// 在index索引的位置插入一个新元素e
public void add(int index, E e){

    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

    //容量扩容为两倍
    if(size == data.length)
        resize(2 * data.length);

    for(int i = size - 1; i >= index ; i --)
        data[i + 1] = data[i];

    data[index] = e;

    size ++;
}

// 向所有元素后添加一个新元素
public void addLast(E e){
    add(size, e);
}

// 在所有元素前添加一个新元素
public void addFirst(E e){
    add(0, e);
}

// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){

    E[] newData = (E[])new Object[newCapacity];
    for(int i = 0 ; i < size ; i ++)
        newData[i] = data[i];
    data = newData;
}
复制代码

3、查找和修改元素

get和set函数如下所示，直接通过索引操作即可，时间复杂度为O(1)；

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

// 修改index索引位置的元素为e
public void set(int index, E e){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Set failed. Index is illegal.");
    data[index] = e;
}
复制代码

contains和find函数如下所示，此时需要遍历数组进行查询，时间复杂度为O(n);

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

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

4、删除元素

remove函数如下所示，删除index索引处的元素，需要将index索引及后面的元素往前移动一位，因此时间复杂度为O(n);同时需要注意我们在删除完元素后如果元素个数仅为容量的四分之一，那么我们缩容为容量的一半；

removeFirst和removeLast函数表示删除数组头和数组尾的元素；

removeElement表示删除元素e，先通过元素查找索引，然后调用remove删除索引；

// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

    E ret = data[index];
    for(int i = index + 1 ; i < size ; i ++)
        data[i - 1] = data[i];
    size --;
    data[size] = null; // loitering objects != memory leak

    //缩容
    if(size == data.length / 4 && data.length / 2 != 0)
        resize(data.length / 2);
    return ret;
}

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

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

// 从数组中删除元素e
public void removeElement(E e){
    int index = find(e);
    if(index != -1)
        remove(index);
}
复制代码

最后是toString函数，打印动态数组的内容，便于查看；

@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();
}
复制代码

下面是整个类的源码：

public class Array<E> {

    private E[] data;
    private int size;

    // 构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

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

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        //容量扩容为两倍
        if(size == data.length)
            resize(2 * data.length);

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

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

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

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

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

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

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

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

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

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

    @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();
    }

    // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }
}
复制代码