跳至主要內容

 

labuladong约 1657 字大约 6 分钟

几个关键点

下面我会直接给出一个简单的动态数组代码实现,包含了基本的增删查改功能。这里先给出几个关键点,等会你看代码的时候可以着重注意一下。

关键点一、自动扩缩容

在上一章 数组基础 中只提到了数组添加元素时可能需要扩容,并没有提到缩容。

在实际使用动态数组时,缩容也是重要的优化手段。比方说一个动态数组开辟了能够存储 1000 个元素的连续内存空间,但是实际只存了 10 个元素,那就有 990 个空间是空闲的。为了避免资源浪费,我们其实可以适当缩小存储空间,这就是缩容。

我们这里就实现一个简单的扩缩容的策略:

  • 当数组元素个数达到底层静态数组的容量上限时,扩容为原来的 2 倍;
  • 当数组元素个数缩减到底层静态数组的容量的 1/4 时,缩容为原来的 1/2。

关键点二、索引越界的检查

下面的代码实现中,有两个检查越界的方法,分别是 checkElementIndexcheckPositionIndex,你可以看到它俩的区别仅仅在于 index < sizeindex <= size

为什么 checkPositionIndex 可以允许 index == size 呢,因为这个 checkPositionIndex 是专门用来处理在数组中插入元素的情况。

比方说有这样一个 nums 数组,对于每个元素来说,合法的索引一定是 index < size

nums = [5, 6, 7, 8]
index   0  1  2  3

但如果是要在数组中插入新元素,那么新元素可能的插入位置并不是元素的索引,而是索引之间的空隙:

nums = [ | 5 | 6 | 7 | 8 | ]
index    0   1   2   3   4

这些空隙都是合法的插入位置,所以说 index == size 也是合法的。这就是 checkPositionIndexcheckElementIndex 的区别。

关键点三、删除元素谨防内存泄漏

单从算法的角度,其实并不需要关心被删掉的元素应该如何处理,但是具体到代码实现,我们需要注意可能出现的内存泄漏。

在我给出的代码实现中,删除元素时,我都会把被删除的元素置为 null,以 Java 为例:

// 删
public E removeLast() {
    E deletedVal = data[size - 1];
    // 删除最后一个元素
    // 必须给最后一个元素置为 null,否则会内存泄漏
    data[size - 1] = null;
    size--;

    return deletedVal;
}

Java 的垃圾回收机制是基于引用计数的,如果一个对象没有被引用,那么这个对象占用的内存才会被释放;否则,垃圾回收器会认为这个对象还在使用中,就不会释放这个对象占用的内存。

如果你不执行 data[size - 1] = null 这行代码,那么 data[size - 1] 这个引用就会一直存在,这个对象的内存就一直不会被释放,进而造成内存泄漏。

其他带垃圾回收功能的语言应该也是类似的,你可以具体了解一下你使用的编程语言的垃圾回收机制,这是写出无 bug 代码的基本要求。

其他细节优化

下面的代码当然不会是一个很完善的实现,会有不少可以进一步优化的点。比方说,我是用 for 循环复制数组数据的,实际上这种方式复制的效率比较差,大部分编程语言会提供更高效的数组复制方法,比如 Java 的 System.arraycopy

不过它再怎么优化,本质上也是要搬移数据,时间复杂度都是 O(n)。本文的重点在于让你理解数组增删查改 API 的基本实现思路以及时间复杂度,如果对这些细节感兴趣,可以找到编程语言标准库的源码深入研究。

动态数组代码实现

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyArrayList<E> {
    // 真正存储数据的底层数组
    private E[] data;
    // 记录当前元素个数
    private int size;
    // 默认初始容量
    private static final int INIT_CAP = 1;

    public MyArrayList() {
        this(INIT_CAP);
    }

    public MyArrayList(int initCapacity) {
        data = (E[]) new Object[initCapacity];
        size = 0;
    }

    // 增
    public void addLast(E e) {
        int cap = data.length;
        // 看 data 数组容量够不够
        if (size == cap) {
            resize(2 * cap);
        }
        // 在尾部插入元素
        data[size] = e;
        size++;
    }

    public void add(int index, E e) {
        // 检查索引越界
        checkPositionIndex(index);

        int cap = data.length;
        // 看 data 数组容量够不够
        if (size == cap) {
            resize(2 * cap);
        }

        // 搬移数据 data[index..] -> data[index+1..]
        // 给新元素腾出位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        // 插入新元素
        data[index] = e;

        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    // 删
    public E removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        int cap = data.length;
        // 可以缩容,节约空间
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[size - 1];
        // 删除最后一个元素
        // 必须给最后一个元素置为 null,否则会内存泄漏
        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E remove(int index) {
        // 检查索引越界
        checkElementIndex(index);

        int cap = data.length;
        // 可以缩容,节约空间
        if (size == cap / 4) {
            resize(cap / 2);
        }

        E deletedVal = data[index];

        // 搬移数据 data[index+1..] -> data[index..]
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }

        data[size - 1] = null;
        size--;

        return deletedVal;
    }

    public E removeFirst() {
        return remove(0);
    }

    // 查
    public E get(int index) {
        // 检查索引越界
        checkElementIndex(index);

        return data[index];
    }

    // 改
    public E set(int index, E element) {
        // 检查索引越界
        checkElementIndex(index);
        // 修改数据
        E oldVal = data[index];
        data[index] = element;
        return oldVal;
    }

    // 工具方法
    public int size() {
        return size;
    }

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

    // 将 data 的容量改为 newCap
    private void resize(int newCap) {
        if (size > newCap) {
            return;
        }
        E[] temp = (E[]) new Object[newCap];

        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }

        data = temp;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    /**
     * 检查 index 索引位置是否可以存在元素
     */
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    /**
     * 检查 index 索引位置是否可以添加元素
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }

    private void display() {
        System.out.println("size = " + size + " cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }


    public static void main(String[] args) {
        // 初始容量设置为 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // 添加 5 个元素
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }

        arr.remove(3);
        arr.add(1, 9);
        arr.addFirst(100);
        int val = arr.removeLast();

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }

}
上次编辑于: