数据结构(Java版)第五期：ArrayList与顺序表(下)

目录

一、用数组实现顺序表

一、用数组实现顺序表

我们提到过，顺序表是基于数组的封装，这次我们以int为例，用数组去实现一个顺序表。

```java
public class MyArrayList {
    private int[] arr;
    public MyArrayList(int capacity){//指定初始容量
        arr = new int[capacity];//这个顺序表依然是空的，还得使用add往里面添加有效元素
    }
}
```

既然存在有效与无效，那我们该如何区分呢？我们可以定义一个size变量。

```java
private int size;//规定前size个元素为有效元素
```

下面就是进行写出方法，比如增、删、查、改等。

```java
    //获取元素个数
    public int size(){
        return size;
    }

    //新增元素，尾插
    public void add(int val){

    }

    //任意位置新增元素
    public void add(int index,int val){

    }

    //根据下标获取元素
    public void get(int index){

    }

    //根据下标设置元素
    public void set(int index,int val){

    }

    //根据数组的值删除元素
    public void delete(int val){

    }

    //根据下标删除元素
    public int remove(int index,int val){

    }

    //判断元素是否存在
    public boolean contains(int val){

    }

    //查找元素所在位置
    public int indexOf(int index){

    }

    //删除所有元素
    public void clear(){

    }

    //打印操作，把ArrayList转成字符串

    @Override
    public String toString() {

    }
```

这里是一些主要的方法，如果我们想实现其他方法，也可以再新增。我们对方法进行了命名之后，下面就是进行实现。我们先来看新增元素的实现。我们需要把新增的元素放到最后的位置，下标为size。如果说size比arr.length的值要小，那么我们正常添加就可以，可如果我们size的值比arr.length要小，我们要先进行扩容。我们可以再写一个resize方法来扩容。

```java
    //新增元素，尾插
    public void add(int val){
        if(size == arr.length){
            resize();
        }
        arr[size] = val;
        size++;
    }
    private void resize(){//这个方法只有程序员才能调用
        //创建一个更长的数组，长度扩大到原来的1.5倍
        //这样就能保证我们每添加一个元素，长度够用
        int[] newArr = new int[(int)(arr.length * 1.5)];
        for (int i = 0; i < size; i++) {
            //原来数组的元素复制到新数组中
            newArr[i] = arr[i];
            //新数组代替旧数组，旧的数组会被垃圾回收给释放掉
            arr = newArr;
        }
    }

```

我们还要实现toString方法，方便我们后期打印这个顺序表。

```java
    @Override
    public String toString() {
        // 打印的格式形如: [1, 2, 3, 4]
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(arr[i]);
            if (i < size - 1) {
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
```

下面我们来进行一下测试，

```java
    public static void test(){
        MyArrayList list = new MyArrayList(6);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list.size);
        System.out.println(list);
    }

    public static void main(String[] args) {
        test();
    }
```

下面是调试结果

运行结果

下面我们进行对新增元素的实现，当我们插入一个新元素时，这个新元素之后的所有元素都要后移一个位置。那么此时我们的时间复杂度就是。

```java
 public void add(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 如果数组已经满了, 继续添加元素, 也是要先扩容
        if (size == arr.length) {
            resize();
        }
        // 搬运元素的操作. 从后往前, 依次把每个元素都往后搬运一个位置.
        // 如果元素本身的下标是 i, 就把这个元素赋值到 i+1 的位置上.
        // index 位置的元素也需要往后搬运一下, i >= index
        for (int i = size - 1; i >= index; i--) {
            arr[i + 1] = arr[i];
        }
        // 此时就相当于把 index 位置已经腾出来了. 把新元素放到 index 位置上就好了.
        arr[index] = val;
        // 不要忘记更新 size
        size++;
    }
```

有的老铁可能觉得这个方法有点麻烦，如果说我们直接插入的新元素，这个位置的旧元素直接后移到我们顺序表中的最后一个位置行不行，并且此时的时间复杂度就是。其实呢，对于我们的顺序表和链表这样的结构来说，它们都是“有序的”，如果我们把原有的顺序改变了，就不是原来的结构了。

```java
//根据下标获取元素
public int get(int index){
        if(index<0 || index>arr.length){
            throw new IndexOutOfBoundsException("下标越界"+index);
        }
        return arr[index];
    }

```

数组通过[]访问下标，时间复杂度是。Java的数组呢，本质是来源于C/C++，C/C++中数组访问下标时间复杂度同样也是。我们知道数组是一块连续存放的内存空间，通过过数组首元素和下标快速算出来对应元素的地址，根据这个地址来访问这个内存空间。内存的硬件设备具备一个特性，随机访问能力。

对于删除元素，也是要保证顺序表在有序的前提下，对于尾删的情况，直接进行size--就可以了，不必进行搬运。 但如果说，我们删除中间的某一个元素，当index==size时，尾插是可以的，但index>size的时候，就会出现异常。

```java
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
```


```java
    //根据下标删除元素
    public int remove(int index,int val){
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("下标越界: " + index);
        }
        //要删除的元素先保存起来，就不怕后期搬运的时候被覆盖
        int result = arr[index];
        if (index == size-1){
            //尾删
            size--;
            return result;
        }
        //一定要注意边界值，可以代入具体数字进行验证
        for (int i = index; i < size-1; i++) {
            arr[i] = arr[i+1];//进行向后搬运
        }
    }
```

仔细分析上面的代码时就会发现，当index为尾删的时候，for循环是进不去的，接下来进行的就是size--的操作。

```java
    public static void test2(){
        MyArrayList list = new MyArrayList(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.remove(0);
        System.out.println(list);
        list.remove(2);
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        list.remove(100);
        System.out.println(list);
    }
```

对于delete方法，我们需要先找到这个值所在的位置，找到之后，调用remove方法执行。

```java
        for (int i = 0; i < size; i++) {
            if(arr[i] == val){
                //找到了
                break;
            }
        }
```

这个for循环结束的条件有两个，i==size或者是arr[i]==val时，但由于我们这个i是for循环里面的局部变量，我们可以把i改成index，并作用再for循环之外。

```java
    //根据数组的值删除元素
    public void delete(int val){
        int index = 0;
        for (; index < size; index++) {
            if(arr[index] == val){
                //找到了
                break;
            }
        }
        for (int i = index; i < size-1; i++) {
            arr[i] = arr[i+1];//进行向后搬运
        }
    }
```

对于contains方法和IndexOf两个方法的代码逻辑非常相似，也比较简单，就不作过多讲解。

```java
    //判断元素是否存在
    public boolean contains(int val){
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return true;
            }
        }
        return false;
    }

    //查找元素所在位置
    public int indexOf(int val){
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }
```