Java ArrayList 底层方法自我实现

二、常见方法实现

ArrayList 的常见方法如下：

1. add(int data)：新增元素，添加在数组后面

public void add(int data) {
    // 判断顺序表是否满了
    if (isFull()) {
        // 扩容 grow();
        grow();
    }
    // 存储
    this.arr[this.usedSize] = data;
    this.usedSize++;
}

public boolean isFull() {
    return this.usedSize == this.arr.length;
}

public void grow() {
    this.arr = Arrays.copyOf(this.arr, 2 * this.arr.length);
}

添加元素时，要先检查数组是否已满（isFull() 通过比较数组的长度和元素个数），如果满了，就要进行扩容 grow()，这里是 copy 两倍的数组容量，然后再进行存储

2. add(int pos, int data): 再 pos 位置添加元素

public void add(int pos, int data) {
    // 检查是不是满的
    if (isFull()) {
        grow();
    }
    checkPos(pos, "add 方法执行的时候 pos 位置不合法");
    // 判断是不是放在 usedSize 位置
    if (pos == usedSize) {
        arr[pos] = data;
        usedSize++;
        return;
    }
    // 如果放在前面，就要移动数据
    for (int i = usedSize - 1; i >= pos; i--) {
        arr[i + 1] = arr[i];
    }
    arr[pos] = data;
    usedSize++;
}

private void checkPos(int pos, String msg) {
    if (pos < 0 || pos > usedSize) {
        throw new PosIllegalityException(msg);
    }
}

还是先要检查容量是否已满 isFull()，满了就要进行扩容 grow()，然后添加时，要先检查 pos 位置是否合法，如上图，pos < 0 || pos > usedSize 就是不合法的，在这个范围则会抛出我们自定义的 PosIllegalityException 异常，正常情况下进行添加：将 pos 位置及后面的元素统统向后移动一个位置，为要添加的元素腾出位置，然后有效数据 usedSize++

3. contains(int toFind)：判断是否包含某个元素

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (arr[i] == toFind) {
            return true;
        }
    }
    return false;
}

使用 for 循环遍历整个数组，if 语句判断当前元素是否是你要找的元素 toFind，是返回 true，不是返回 false

4. indexOf(int toFind): 查找某个元素对应的位置

public int indexOf(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if (arr[i] == toFind) {
            return i;
        }
    }
    return -1;
}

同理：使用 for 循环遍历整个数组，if 语句判断当前元素是否是你要找的元素 toFind，是返回对应元素的下标 i，不是返回 -1

5. get(int pos): 获取 pos 位置的元素

public int get(int pos) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }
    checkPos(pos, "get 方法的 pos 位置不合法");
    return arr[pos];
}

private void checkPos(int pos, String msg) {
    if (pos < 0 || pos >= usedSize) {
        throw new PosIllegalityException(msg);
    }
}

public boolean isEmpty() {
    return usedSize == 0;
}

获取元素，先检查 pos 位置是否为空 isEmpty()，如果为空，抛出我们的自定义异常 EmptyListException，然后检查 pos 位置是否合法 pos<0 || pos >= usedSize 这个范围就是不合法的，抛出我们的自定义异常 PosIllegalityException,最后就可以返回 pos 位置的元素

6. set(int pos, int value)：给 pos 位置的元素设为 value

public void set(int pos, int value) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }
    checkPos(pos, "set 方法执行的时候 pos 位置不合法" + pos);
    arr[pos] = value;
}

替换时要先检查是否为空 isEmpty()，为空抛出自定义异常 EmptyListException,不为空检查 pos 位置是否合法，最后将给定的值替换指定的数组元素

7. remove(int toRemove)：删除第一次出现的关键字 key

public void remove(int toRemove) {
    if (isEmpty()) {
        throw new EmptyListException("当前顺序表为空");
    }
    // 查找要删除数据的下标
    int index = indexOf(toRemove);
    if (index == -1) {
        System.out.println("没有你要删除的数据");
        return;
    }
    for (int i = index; i < usedSize - 1; i++) {
        arr[i] = arr[i + 1];
    }
    usedSize--;
    // arr[usedSize] = null;如果是引用类型，需要手动置空
}

还是先检查是否为空，然后可以通过 indexOf(toRemove) 查找要删除的元素，如果 index == -1，则没有你要删除的元素，如果有，进行覆盖删除，让后面的元素逐一向前移动一个位置直到你要，直到覆盖掉你要删除的元素，最后将有效元素 usedSize–

8. size()：获取顺序表长度

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

9. clear()：清空顺序表

public void clear() {
    for (int i = 0; i < this.usedSize; i++) {
        arr[i] = 0;
    }
    usedSize = 0;
}

三、总结

这篇文章只是从深度的实现了一下 ArrayList 提供的一系列方法，以便于更好地去理解和使用 ArrayList，让我们认识到了，数据结构的学习和使用，要考虑到所有方面，对我们的逻辑思维能力要求很高，同样也会提高我们这方面的能力，相关的其他内容后面会详细道来