掌握这些,你也能徒手实现ArrayList、Vector和Stack

今天我们要学习的,是数组这种数据结构在JDK集合中的应用。

数组作为最简单的一种线性结构,操作也比较简单。虽说简单,但它却是编程语言底层实现不可缺少的。

它的特点是,按索引随机查找快,插入和删除比较慢。因为按照索引可以直接定位到某个元素,而插入或删除通常会涉及到数据的迁移。

数组的元素前后之间是连续存储的,因此有利于CPU进行缓存,从而提高访问速度。

在JDK的集合中,ArrayList、Vector和Stack的底层存储结构,都是数组。

接下来,我们就从数组的基本操作开始,一步步实现我们的目标。

数组的基本操作

数组主要有三个基本操作:查找、插入和删除。

定义数组

/** 创建一个数组 */
int[] elementData = new int[10];

/** 数组已存储的元素个数 */
int size = 0;

简单操作

添加

/**
 * 添加. 将新元素添加到数组尾部.
 */
public void add(int e) {
    elementData[size++] = e;
}

查找

/**
 * 查找. 获取指定索引位置的元素
 */
public int get(int index) {
    return elementData[index];
}

复杂操作

插入

/**
 * 插入.
 * 1.指定索引位置及之后的所有元素先往后移动1位; 
 * 2.将新元素插入到指定索引位置.
 */
public void add(int index, int e) {
    // 1.index及之后的元素后移1位. index移动到index+1的位置,移动的数量为size-index个.
    System.arraycopy(elementData, index, elementData, index + 1, size - index);

    // 2.保存元素,已存储数量加1
    elementData[size++] = e;
}

删除

/**
 * 删除. 删除指定索引位置的元素,指定索引位置后面的所有元素往前移动1位.
 */
public void remove(int index) {
    // 1.计算出需要往前移动的元素个数.
    // index+1代表区间[0,index]的数量,size-(index+1)代表index之后元素的个数.
    int numMoved = size - index - 1;

    // 2.将index后面的所有元素往前移动1位.
    // 伪代码:for (numMoved) elementData[index]=elementData[index+1];
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

    // 3.已存储数量减1
    size--;
}

扩展操作

更新

/**
 * 更新. 更新指定索引位置的元素,并返回旧值.
 */
public int set(int index, int newValue) {
    int oldValue = elementData[index];
    elementData[index] = newValue;
    return oldValue;
}

查找元素

/**
 * 查找元素. 返回首次出现的索引位置,如果元素不存在则返回 -1.
 */
public int indexOf(int o) {
    for (int i = 0; i < size; i++)
        if (o == elementData[i])
            return i;
    return -1;
}

扩容

/**
 * 默认进行2倍扩容.
 */
private void resize() {
    if (size == elementData.length) {
        // 1.按2倍大小创建新数组,并将已存储的数据迁移到新数组
        int[] copy = new int[size * 2];
        System.arraycopy(elementData, 0, copy, 0, elementData.length);

        // 2.使用扩容后的新数组替换旧数组
        elementData = copy;
    }
}

扩展知识

实现System.arraycopy

/**
 * System.arraycopy的简化实现.
 */
public void arraycopy(int[] src, int srcPos, int[] dest, int destPos, int length) {
    for (int i = 0; i < length; i++) {
        dest[destPos++] = src[srcPos++];
    }
}

小结

通过以上内容,我们可以了解到,数组稍微复杂一点的操作是插入、删除和扩容

共同点如下:

1.从哪里开始移动,往哪个方向移动?

插入1个元素

  • 指定索引位置及之后(>=index)的所有元素先往后移动1位;
  • 再将新元素插入到指定索引位置.

删除1个元素

  • 指定索引位置后面(>index)的所有元素往前移动1位. 这样,指定索引位置的元素被覆盖,相当于删除掉了。

2.需要移动多少个元素?

插入需要移动的元素个数为:size – index

删除需要移动的元素个数为:size – (index + 1)

3.移动数据

根据前面2点得到的开始移动索引位置和移动个数,循环移动数据。

虽然可以自己实现数据的移动,但借助于System.arraycopy()更加高效。因为高性能的JVM都会将System.arraycopy()实现为intrinsic方法,也就是说,JVM内部会提供一套更高效的实现。

实现ArrayList

将上面数组的这些操作组合起来,就可以实现ArrayList的核心功能了。

主要思路如下:

  • 入参如果涉及到索引index,则先进行索引范围合法性检查(rangeCheck);
  • 添加或插入数据时,先进行容量检查和扩容(resize);
  • 将int类型使用泛型E代替,以支持泛型类型值
  • 删除时将最后一个元素置为null,以便于GC(elementData[–size] = null)
  • indexOf对元素的比较,使用equals代替等于号
  • 是否包含指定元素:boolean contains(Object o) {return indexOf(o) >= 0;};
  • 返回列表大小:public int size() {return size;};
  • 列表是否为空:boolean isEmpty() {return size == 0;};

实现Vector

Vector的实现基本和ArrayList是一样的,主要区别是Vector是线程安全的

Vector实现线程安全的方法很简单,就是在ArrayList的基础之上,一视同仁对每个方法都加上同步原语synchronized

简单粗暴的结果,就是在高并发的情况下效率比较低下,因此一般也比较少使用。

实现Stack

Stack继承了Vector,简单复用了Vector的相关方法。并基于这些方法,封装了栈的入栈出栈操作。

可想而知,Stack的相关操作也是线程安全的,效率依赖于Vector的实现。

数组索引位置0代表栈底,索引位置 size-1 代表栈顶。

获取栈顶元素peek()

相当于查找索引号为 size-1 的元素:get(size – 1)

入栈push()

将元素推入栈顶,即将元素添加到数组尾部:add(e)

出栈pop()

栈顶元素出栈,即删除数组的最后一个元素:remove(size – 1)

总结

写到这里,我们来总结一下掌握本篇内容的核心步骤:

  1. 学会数组的基本操作,重点是插入、删除和扩容;
  2. 基于数组的基本操作,完善并实现ArrayList;
  3. 在ArrayList的基础之上,对所有方法加上同步原语synchronized,实现Vector;
  4. 继承Vector,利用几个基本方法,实现Stack的入栈出栈操作。

通过以上几个步骤,能够更加高效的学习,更好的理解ArrayList、Vector和Stack这几个类的实现原理。

那么,现在就只差最后一步了:打开电脑,开始徒手实现吧^_^

最后,附上我对ArrayList的简化实现:

/**
 * java.util.ArrayList的核心实现.
 *
 * @param <E>
 */
public class MyArrayList<E> {

    /** 用于存储元素的数组. 其大小,即为底层存储的容量. */
    private Object[] elementData;
    /** 已存储元素的个数 */
    private int size;

    /**
     * 默认构造函数
     */
    public MyArrayList() {
        this(10);
    }

    /**
     * 构造函数
     * 
     * @param initialCapacity 初始化容量
     */
    public MyArrayList(int initialCapacity) {
        this.elementData = new Object[initialCapacity];
    }

    /**
     * 添加元素
     * 
     * @param e
     * @return
     */
    public boolean add(E e) {
        // 1.检查容量与扩容
        resize();
        // 2.保存元素,已存储数量加1
        elementData[size++] = e;
        return true;
    }

    /**
     * 插入. 将元素插入到指定索引位置,索引位置及之后的元素往后移动1位
     * 
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        // 1.索引范围检查
        rangeCheckForAdd(index);
        // 2.检查容量与扩容
        resize();
        // 3.index及之后的元素后移1位
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 4.保存元素,已存储数量加1
        elementData[size++] = e;
    }

    /**
     * 获取指定索引位置的元素
     * 
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E get(int index) {
        // 1.索引范围检查
        rangeCheck(index);
        // 2.返回元素
        return (E) elementData[index];
    }

    /**
     * 更新指定索引位置的元素,同时返回旧值.
     * 
     * @param index
     * @param element
     * @return
     */
    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        // 1.索引范围检查
        rangeCheck(index);
        // 2.暂存旧值,在最后返回
        E oldValue = (E) elementData[index];
        // 3.更新指定索引位置的数量
        elementData[index] = element;

        return oldValue;
    }

    /**
     * 删除指定索引位置的元素,并返回该元素
     * 
     * @param index
     * @return
     */
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        // 1.索引范围检查
        rangeCheck(index);
        // 2.获取待删除后返回的元素
        E oldValue = (E) elementData[index];
        // 3.将index后面的所有元素往前移动1位
        // 计算出需要往前移动的元素个数. index+1代表区间0~index的数量,size-(index+1)代表index之后元素的个数.
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将[index+1, size)区间的numMoved个元素往前移动1位
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        // 4.已存储数量减1. 同时末尾元素设置为null,便于GC.
        elementData[--size] = null;

        return oldValue;
    }

    /**
     * 是否包含指定元素
     * 
     * @param o
     * @return
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * 返回首次出现指定元素的索引位置. 如果元素不存在则返回 -1.
     * 
     * @param o
     * @return
     */
    public int indexOf(Object o) {
        // 从前往后遍历
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
        return -1;
    }

    /**
     * 返回最后一次出现指定元素的索引位置. 如果元素不存在则返回 -1.
     * 
     * @param o
     * @return
     */
    public int lastIndexOf(Object o) {
        // 从后往前遍历
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
        return -1;
    }

    /**
     * 以数组形式返回列表的所有元素,支持泛型
     * 
     * @param a
     * @return
     */
    public <T> T[] toArray(T[] a) {
        System.arraycopy(elementData, 0, a, 0, size);
        return a;
    }

    /**
     * 返回列表大小
     * 
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 列表是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 索引范围检查
     * 
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("size: " + size + ", index: " + index);
    }

    /**
     * 索引范围检查
     * 
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("size: " + size + ", index: " + index);
    }

    /**
     * 检查数组存储空间是否已满,如果满了进行1.5倍扩容.
     */
    private void resize() {
        if (size == elementData.length) {
            // 1.默认按1.5倍扩容
            int newCapacity = size + (size >> 1);
            if (newCapacity <= size) {
                newCapacity = size + 1;
            }
            // 2.扩容,将元素迁移到新的数组
            elementData = copyOf(elementData, newCapacity);
        }
    }

    /**
     * 从源数组复制指定长度的元素到新数组. 用于扩容或缩容
     * 
     * @param original
     * @param newLength
     * @return
     */
    private Object[] copyOf(Object[] original, int newLength) {
        Object[] copy = new Object[newLength];
        System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
        return copy;
    }

}

---转载本站文章请注明作者和出处 二进制之路(binarylife.icu),请勿用于任何商业用途---

留下评论