实现顺序表

1.顺序表的底层是数组。（既然顺序表的底层是数组，那你要顺序表干嘛？就用数组不行吗？）

当前这个数组中有多少个有效数据，不要自己数，让程序来。

实际上数组没有赋值的时候，默认是0，所以此刻数组应该是这样的：

 错误示例：（当数组元素为0时候就跳出循环，并且打印count）

public class Test1 {
    public static void main(String[] args) {
        int count = 0;
        int[] arr = new int[10];
        for (int i = 0; i < 3; i++) {
            arr[i] = i + 1;
        }
 
        for (int i : arr) {
            System.out.print(i + " ");
        }
 
        //计算一下有效数据的个数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                count++;
            }
            if (arr[i] == 0) {
                break;
            }
        }
 
        System.out.println();
        System.out.println("有效数据个数为：" + count);
    }
}

那么问题又来了：

这样的话，有效数据是6。上面的代码就错了，有效数据还是3。 

正确的做法，放入一个计数一个！（这样的话，编码比较繁琐，10个数的话还好说，如何数据量大的话，就靠数组难实现，这时候体现出数据结构的重要性，这是一个造轮子的过程，很多函数可以自己实现，比较灵活，轮子造好后，我们就可以重复使用）

我们先不用顺序表实现一下上面的例子：

public class Test1 {
    public static void main(String[] args) {
        int count = 0;
        int[] arr = new int[10];
        for (int i = 0; i < 3; i++) {
            count++;
            arr[i] = i + 1;
        }
 
        arr[5] = 3;
        count++;
 
        for (int i : arr) {
            System.out.print(i + " ");
        }
 
 
        System.out.println();
        System.out.println("有效数据个数为：" + count);
    }
}
//打印
//1 2 3 0 0 3 0 0 0 0 
//有效数据个数为：4
//

最后我们先实现一下顺序表，在解决上述问题。

import java.util.Arrays;
 
public class MyArrayList {
    private int[] elem;
    private int usedSize;
    private static int capacity = 10;
 
    public MyArrayList() {
        this.elem = new int[capacity];
    }
 
    public boolean isFull() {
        if (this.usedSize == capacity) {
            return true;
        }
        return false;
    }
 
    public void add(int pos, int data) {
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法");
            return;
        }
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * capacity);
            capacity *= 2;
        }
        for (int i = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }
 
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
 
    public boolean isEmpty() {
        if (this.usedSize == 0) {
            return true;
        }
        return false;
    }
 
    public boolean contains(int toFind) {
        if (isEmpty()) {
            return false;
        }
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }
 
    public int search(int toFind) {
        if (isEmpty()) {
            return -1;
        }
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
 
    public int getPos(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("顺序表为空！");
        }
        if (pos < 0 || pos >= this.usedSize) {
            throw new RuntimeException("pos不合法");
        }
        return this.elem[pos];
    }
 
    public int size() {
        return this.usedSize;
    }
 
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos位置不合法！");
            return;
        }
        this.elem[pos] = value;
    }
 
    public void remove(int toRemove) {
        if (isEmpty()) {
            return;
        }
 
        int index = search(toRemove);
 
        if (index == -1) {
            System.out.println("没有你要删除的数字！");
        }
 
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        this.usedSize--;
    }
 
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0;
    }
 
 
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 1);
        myArrayList.add(1, 2);
        myArrayList.add(2, 3);
        myArrayList.add(3, 4);
        System.out.println(myArrayList.size());
        myArrayList.display();
        System.out.println(myArrayList.contains(3));
        System.out.println(myArrayList.contains(2));
        System.out.println(myArrayList.search(5));
        System.out.println(myArrayList.search(2));
        System.out.println(myArrayList.getPos(0));
        System.out.println(myArrayList.usedSize);
        myArrayList.display();
        myArrayList.remove(1);
        myArrayList.remove(2);
        myArrayList.display();
        myArrayList.remove(4);
        myArrayList.display();
        myArrayList.clear();
        System.out.println("==============");
        myArrayList.display();
    }
}

使用myArrayList.usedSize即可解决上述问题。

顺序表的 增 删 查 改 的时间复杂度：

增：O  (N)

删：O  (N)

查:  （给定关键字） O (N)        (给定下标）O  (1)

改：(给定下标)   O  (1)

顺序表的一些缺点：

增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。

增容一般是2倍增长，势必会有一定的空间浪费。

链表会解决上述问题。