Java数据结构顺序表从零基础到精通进阶

public class MyArrayList {
    public int[] data;    // 存储数据
    public int size;    // 有效数据个数
}

public MyArrayList() {
    this.data = new int[10];   // 后面不够再增容
    this.size = 0;    // 初始无有效数据，size 为0
}

// 打印顺序表
public void display();
// 在 pos 位置增加元素
public void add(int pos, int num);
// 判断顺序表中是否包含某个元素
public boolean contains(int num);
// 查找某个元素所在位置
public int search(int key);
// 获取 pos 位置的元素
public int getPos(int pos);
// 将 pos 位置的元素值设为 value
public void setPos(int pos, int value);
//删除第一次出现的关键字key
public void remove(int key);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();

private void ensureCapacity() {
    if (this.size == this.data.length) {
        // 说明满了，该扩容了
        this.data = Arrays.copyOf(this.data, 2 * this.data.length);
    }
}

public void add(int pos, int num) {
    if (pos < 0 || pos > this.size) {    // 检验下表合法性
        throw new RuntimeException("ArrayIndexOutOfBoundsException : " + pos);
    }
    ensureCapacity();
    for (int i = this.size; i > pos; i--) {
        this.data[i] = this.data[i - 1];
    }
    this.data[pos] = num;
    this.size++;
}

public String printMyArrayList() {
    String str = "[";
    for (int i = 0; i < this.size - 1; i++) {   // for循环中的右边界应该用size而不用data.length
        str += this.data[i] + ", ";
    }
    str += this.data[this.size - 1];
    str += "]";
    return str;
}

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        myArrayList.add(4, 2);
        myArrayList.add(0, 100);   // 头插
        myArrayList.add(2, 666);   // 中间插
        System.out.println(myArrayList.printMyArrayList());
    }
}

public boolean contains(int num) {
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] == num) {
            return true;
        }
    }
    return false;
}

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.contains(3));
        System.out.println(myArrayList.contains(2));
        System.out.println(myArrayList.contains(0));
        System.out.println(myArrayList.contains(666));
    }
}

public int search(int key) {
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] == key) {
            return i;
        }
    }
    return -1;    // 不存在这个元素，返回-1
}

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.search(0));
        System.out.println(myArrayList.search(3));
        System.out.println(myArrayList.search(666));
    }
}

public int getPos(int pos) {
    if (pos < 0 || pos >= this.size) {
        throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
    }
    return this.data[pos];
}

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        System.out.println(myArrayList.getPos(0));
        System.out.println(myArrayList.getPos(3));
        System.out.println(myArrayList.getPos(1));
        System.out.println(myArrayList.getPos(6));
    }
}

public void setPos(int pos, int value) {
    if (pos < 0 || pos >= this.size) {     // size位置为无效元素
        throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
    }
    this.data[pos] = value;
}

public class UseArrayList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 0);
        myArrayList.add(1, 1);
        myArrayList.add(2, 2);
        myArrayList.add(3, 3);
        myArrayList.setPos(0, 666);
        myArrayList.setPos(3, 777);
        System.out.println(myArrayList.printMyArrayList());
    }
}

public void remove(int key) {
    int pos = search(key);
    if (pos == -1) {
        return;        // 若是这个数字不存在，则返回
    }
    for (int i = pos; i < this.size - 1; i++) {
        this.data[i] = this.data[i + 1];      // 从后往前挪，直接将要删除的数字覆盖掉
    }
    this.size--;
}

public int size() {
    return this.size;
}

public void clear() {
    this.size = 0;
}

public void removeAll(int key) {
    for (int i = 0; i < this.size; i++) {
        if (this.search(key) != -1) {
            remove(key);
        } else {
            return;
        }
    }
}

public void removeAllPlus(int key) {
    int[] newData = new int[this.data.length];    // 新数组长度应该和源数组长度相同
    int j = 0;
    for (int i = 0; i < this.size; i++) {
        if (this.data[i] != key) {
            newData[j] = this.data[i];
            j++;
        }
    }
    this.data = newData;
    this.size = j;
}

public void removeAllPlusPlus(int key) {
    int dest = 0;
    for (int src = 0; src < this.size; src++) {
        if (this.data[src] != key) {
            this.data[dest] = this.data[src];
            dest++;
        }
    }
    this.size = dest;
}