数据结构基础–数组实现[JAVA]

1数组的概念

数组是有限个相同类型的变量所组成的有序集合，数组的存储结构如下：

2数组的存储结构：

3数组的特点：

数组在内存中是顺序存储的，因此数组可以直接通过下标访问元素，读取速度较快，但插入和删除元素为了保证删除后的元素仍然是紧密相连的 ，会导致大量元素被迫移动，影响效率，因此数组适合：读操作多，写操作少的场景 数组在内存中的存储结构：灰色：已被占用 绿色：空闲内存

此时如果删除元素8，其后的7，9，1都需要前移来保证元素是连续连接的。

4数组的基本操作有：

了解了数组的底层存储结构，来看一下数组的基本操作：

1. 读取元素 读取元素相对简单，由于数组元素是连续的，我们可以直接访问下标来获得元素值。
2. 更新元素 更新元素也是直接访问元素下标就可以对元素值进行更新
3. 插入元素 插入元素需要注意，被插入元素位置及其之后的元素要后移
4. 删除元素 删除元素需要注意，被删除元素后面的元素需要前移

5代码实现

本次以实现一个整型数组为例，来实现数组的增删改查操作。

首先定义MyArray类和构造函数，

class MyArray{
    private int[] arr;//储存元素
    private int size;//记录元素个数
    //有参构造函数，参数为数组总容量
    public MyArray(int capacity) {
        arr = new int[capacity];
        size=0;
        }
    //不传入参数，则默认容量为10
    public MyArray(){
        this(10);
    }
    }

2. 实现插入操作

        public void add(int index,int element){
        //如果size等于capacity，则说明数组已满
        if (size==arr.length){
            throw new IllegalArgumentException("数组已满");
        }
//        判断访问下标是否超出范围
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
//        将index所在的元素及index后面的元素后移
        for (int i = size-1;i>=index;i--){
            arr[i+1]=arr[i];
        }
//        设置新元素
        arr[index] = element;
        size+=1;
        }

例如在index=5的位置插入元素4，步骤如下，首先7，9，1元素后移，然后将元素4插入这里还给出了在数组头部和尾部添加元素的接口，本身还是调用add(id,e)函数。

//        在数组头添加元素
    public void addFist(int element){
        add(0,element);
    }
//    在数组尾添加元素
    public void addLast(int element){
        add(size,element);
    }

3. 访问元素

访问元素比较简单，直接按照下标访问即可

public int get(int index){
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
        return arr[index];
        }

4. 更改元素值

和访问元素类似，通过下标访问要修改的元素，修改即可

public void set(int index,int element){
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
        arr[index]=element;
    }

5. 删除元素

public int remove(int index){
//        判断下标是否越界
        if (index<0||index>=size){
            throw new IllegalArgumentException("超过下标");
        }
//        返回删除的元素值
        int element = arr[index];
//        将待删除元素下标及之后的元素向前移动一位
        for (int i=index+1;i<size;i++){
            arr[i-1]=arr[i];
        }
        //元素数减1
        size--;
        return element;
    }

例如删除index=4的元素8，步骤如下，首先7，9，1元素以次前移一位，然后size–；这里还给出了在数组头部和尾部删除元素的接口，本身还是调用remove(index)函数。

 public int removeFist(){
        return remove(0);
    }
    public int removeLast(){
        return remove(size-1);
    }

6. 为了更方便的输出数组，重写了toString()函数

@Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %dn", size, arr.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(arr[i]);
            if (i != size)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
}

6最后，完整代码如下：

class MyArray{
    private int[] arr;
    private int size;
    //有参构造函数，参数为数组总容量
    public MyArray(int capacity) {
        arr = new int[capacity];
        size=0;
        }
    //不传入参数，则默认容量为10
    public MyArray(){
        this(10);
    }

    public void add(int index,int element){
        //如果size等于capacity，则说明数组已满
        if (this.size==arr.length){
            throw new IllegalArgumentException("数组已满");
        }
//        判断访问下标是否超出范围
        if (index<0||index>this.size){
            throw new IllegalArgumentException("超过下标");
        }
//        将index所在的元素及index后面的元素后移
        for (int i = this.size-1;i>=index;i--){
            arr[i+1]=arr[i];
        }
//        设置新元素
        arr[index] = element;
        this.size+=1;
        }
//        在数组头添加元素
    public void addFist(int element){
        add(0,element);
    }
//    在数组尾添加元素
    public void addLast(int element){
        add(this.size,element);
    }

    public int get(int index){
        if (index<0||index>this.size){
            throw new IllegalArgumentException("超过下标");
        }
        return arr[index];
        }
    public void set(int index,int element){
        if (index<0||index>size){
            throw new IllegalArgumentException("超过下标");
        }
        arr[index]=element;
    }
    public int remove(int index){
//        判断下标是否越界
        if (index<0||index>=size){
            throw new IllegalArgumentException("超过下标");
        }
//        返回删除的元素值
        int element = arr[index];
//        将待删除元素下标及之后的元素向前移动一位
        for (int i=index+1;i<size;i++){
            arr[i-1]=arr[i];
        }
        size--;
        return element;
    }
    public int removeFist(){
        return remove(0);
    }
    public int removeLast(){
        return remove(size-1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %dn", size, arr.length));
        res.append('[');
        for (int i = 0; i < size; i++) {
            res.append(arr[i]);
            if (i != size)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
}
}

7简单测试

public static void main(String[] args){
        MyArray arr = new MyArray(5);
        arr.add(0,1);
        arr.add(0,2);
        arr.add(0,3);
        arr.add(0,3);
        System.out.println(arr.toString());
        arr.set(3,4);
        System.out.println(arr.toString());
        arr.remove(0);
        System.out.println(arr.toString());
    }

输出结果：

Array: size = 4, capacity = 5
[3, 3, 2, 1, ]
Array: size = 4, capacity = 5
[3, 3, 2, 4, ]
Array: size = 3, capacity = 5
[3, 2, 4, ]