如何自己实现一个ArrayList？ 一、实现ArrayLi

发表于

一、实现ArrayList的关键点

  • 怎么存储数据？
  • 怎么增删改查数据？

二、怎么存储数据？

首先想到的就是数组，用int[]？还是String[]？既然我们也不知道类型，那干脆用Objec[]来表示。所以变成了如下：

1
2
3
4
java复制代码public class ArrayList {
    // 存放元素的地方
    private Object[] elementData;
}

数组长度设置多少呢？设置多少我们也不知道呀，所以给个默认值然后也支持让用户自定义设置比较合适，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码public class ArrayList {
    // 默认数组容量，是10
    private static final int DEFAULT_CAPACITY = 10;
 	// 存放元素的地方   
    private Object[] elementData;
    
    // 默认无参构造器，容量是10
    public ArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }
    
    // 自定义数组容量的构造器
    public ArrayList(int initialCapacity) {
        if (initialCapacity < 0) {
            initialCapacity = DEFAULT_CAPACITY;
        }
	    elementData = new Object[initialCapacity];
    }
}

很完美的样子，那我们容器有了，是不是就该提供api进行增删改查了？

三、API

1、增(add)

增加分为两种：直接在数组末尾增加，还一种就是我。

1.1、直接在数组末尾增加

那我们怎么知道数组中的元素的下标到哪了呢？是不是elementData.length ++就行呢？肯定不对。elementData.length是数组的容量，假设是10，那就代表一共可以容纳10个元素，但是很可能现在只有2个元素，也就是再add的时候应该放到下标为2（第三个元素）的位置上。

那怎么知道目前有多少元素在集合中呢？

维护个变量，每次add完都变量+1

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class ArrayList {
    // 数组当前元素个数
    private int size;
    
    // 在末尾添加元素
    public boolean add(Object e) {
		// 直接赋值，然后size+1
        elementData[size++] = e;
        return true;
    }
}

很简单，就是直接添加。那我们不想再末尾追加元素，想在自定义位置追加个元素，怎么办？

1.2、在固定位置增加

怎么在固定位置追加？比如[1, 2, 3]，我要在第二个位置追加4，变成[1, 4, 2, 3]，那是不是需要在第二个位置以后的元素整体向后移动一位？怎么移动？

可以通过System.arraycopy()直接复制元素到数组的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码public class ArrayList {
    // 数组当前元素个数
    private int size;
    
    // 在index位置添加element
	public void add(int index, Object element) {
        // 复制，也就是移动元素
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 赋值
        elementData[index] = element;
        size++;
    }
}

上面移动没看懂？分析下：

1
java复制代码System.arraycopy(elementData, index, elementData, index + 1, size - index);

这几个参数的含义是：

1
2
3
4
5
less复制代码src: 源数组
srcPos: 源数组要复制的起始位置
dest: 目的数组
destPos: 目的数组放置的起始位置
length: 复制的长度

我们这里原数组和目标数组都是elementData，那不就是相当于把第index位置的数据复制到index+1上嘛？一共复制size-index个。

比如[1,2,3,4]，index=1，element=5。

那么这行代码的意思是从第index开始复制（index=1，也就是第2个元素，在这里是2），将数据复制到elementData中。那复制到新数组的哪个位置呢？复制几个数据呢？

复制size-index=4-1=3个元素到新数组上，从新数组的index+1=2位置开始。所以变成了：[1,2,2,3,4]

然后最后执行了elementData[index] = element;，那不就是elementData[1] = 5;嘛？变成了[1,5,2,3,4]。完美。

效率不高，因为需要数组数据整体向后移动一位。

不管直接在数组末尾追加还是在固定位置增加，都有一个问题：因为数组是定长的，数组满了咋办？

只有两种解决方案：报错、自动扩容。报错显然不合适，自动扩容的机制怎么实现？

1.3、扩容

1
2
3
4
5
6
7
8
java复制代码// 扩容为1.5倍
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // >> 1相当于除以2，所以相当于1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 完成扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

很简单，就是利用Arrays.copyOf()来完成扩容。所以在add方法开始就先判断是不是需要扩容，是的话先扩容然后在add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码public class ArrayList {
    // 数组当前元素个数
    private int size;
    
    // 在末尾添加元素
    public boolean add(Object e) {
        // 如果达到容量了，就扩容。
        if (size >= elementData.length) {
            grow(minCapacity);
        }
		// 直接赋值，然后size+1
        elementData[size++] = e;
        return true;
    }
}

2、删(remove)

也很简单吧，删除后需要把删除后的数据都向前移动一位。移动方法是arraycopy，上面add详细讲解过了，不再多说。自己代数进去看看就知道了。

1
2
3
4
5
6
7
8
9
java复制代码public void remove(int index) {
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 整体向前移动
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 移动完后移除最后的元素
    elementData[--size] = null; 
}

3、改(set)

把某个位置的元素替换成新的，然后把被替换的旧值返回回去。

1
2
3
4
5
6
7
8
9
java复制代码public class ArrayList {
    public Object set(int index, Object element) {
        // 先找到旧值，返回用
        Object oldValue = elementData[index];
        // 其实就这一行代码就搞定了，直接赋值。
        elementData[index] = element;
        return oldValue;
    }
}

很简单，直接赋值。O(1)时间复杂度。

4、查(get)

查的话无非就两种：根据下标查元素、根据元素查下标。

根据下标查元素

1
2
3
4
5
6
7
java复制代码public class ArrayList {
    // 根据下标查元素
    public Object get(int index) {
        // 直接根据下标定位到元素了
        return elementData[index];
    }
}

效率杠杠的，O(1)时间复杂度，接下来再看看根据元素查下标怎么实现。

根据元素查下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public class ArrayList {
    // 根据元素查下标
    public int get(Object value) {
        // 只能遍历查找
        for (int i = 0; i < size; i ++) {
            // 找到了
            if (value == elementData[i]) {
                return i;
            }
        }
        // 没找到
        return -1;
    }
}

这个性能就不行了，平均时间复杂度是O(n)。不过工作中遇到这种需求的也很少，我实在想不到根据元素查找元素在数组中所在的位置有何用。

四、总结

其实实现原理就是Object[]，让给个默认长度10。

关键点：

  • add(index, e)/remove(index)需要移动数据，效率低下。
  • add(e)/add(index, e)可能需要扩容，扩容效率低下。
  • get(index)直接根据index找到数组中的元素，效率极高。

五、广告

个人微信公众号：Java码农社区

WechatIMG2.png

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%