Skip to content

自己动手实现ArrayList

我们用的最多的就是ArrayList类了。
Java提供ArrayList类作为数据结构中数组的实现,其内部无非是封装了原始的数组。
先不看jdk里的源代码,我们自己试着实现一下吧。
pubic class MyArrayList
首先我们需要一个原始的数组作为成员变量Object[];
然后我们开始定义需要提供的操作。无外乎是增删改查,其中增删改都是传入指定位置下标进行操作,我们也可以额外提供不指定位置的增加操作,默认在尾部增加。
当然我们还要对各种非法操作进行判断并抛出异常,比如数组大小为5,访问第10个位置的操作就为非法操作。
最后我们可以试着实现Iterable接口

public class MyArrayList {

    private Object[] elements;

    /**
     * 默认的构造函数,初始化内部数组,默认大小为0
     */
    public MyArrayList() {
        elements = new Object[0];
    }

    /**
     * 根据下标获取元素
     */
    public E get(int index) {
        return (E) elements[index];
    }

    /**
     * 根据下标设置元素的值
     */
    public void set(int index, E element) {
        elements[index] = element;
    }

    /**
     * 根据下标移除元素,数组需要变小
     */
    public E remove(int index) {
        E element = get(index);
        Object[] oldElements = elements;
        elements = new Object[oldElements.length - 1];
        for (int i = 0; i < index; i++) {
            elements[i] = oldElements[i];
        }
        // 下标之后的所有元素向前移位
        for (int i = index; i < elements.length; i++) {
            elements[i] = oldElements[i + 1];
        }
        return element;
    }

    /**
     * 在队尾插入元素,数组需要扩容
     */
    public void add(E element) {
        Object[] oldElements = elements;
        // 建立新的更大的数组
        elements = new Object[oldElements.length + 1];
        // 拷贝
        for (int i = 0; i < oldElements.length; i++) {
            elements[i] = oldElements[i];
        }
        elements[oldElements.length] = element;
    }

    public void add(int index, E element) {
        Object[] oldElements = elements;
        elements = new Object[oldElements.length + 1];
        for (int i = 0; i < index; i++) {
            elements[i] = oldElements[i];
        }
        elements[index] = element;
        for (int i = index + 1; i <= oldElements.length; i++) {
            elements[i] = oldElements[i - 1];
        }
    }
}

上面的代码写的太粗糙,可以称得上是一个最差实践。这些代码只提供一个思路,没有任何越界判断和校检数据,也没有垃圾回收意识,实际工程中千万不要这样写。

写上面这些代码主要是深化思想上的一些东西,我们的ArrayList目的是封装对一个数组的操作,所有提供的方法间接的操纵数组,当然一些方法需要生成新的数组,将原有数据和新数据复制进去,从而达到对数组扩容的目的,而使用者并不需要关心内部变化。

从设计到编写这些代码,充分体现了Java这门语言的封装特性。我们也明白那些复杂和庞大的东西细化之后内部总是最简单的。

由于我代码写的很不严谨和完善,之后实现Iterable接口的工作已经没有动力做下去了。可以看看我的这篇博客。
Iterable和Iterator

Published inJava

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注