自定义ArrayList
- List 接口 (PS:考虑到ArrayList的应用场景自定义的接口与JDK中有所区别, 如contains方法并不适合用该数据结构故不自此定义与实现)
public interface List<E> {
boolean isEmpty();
int capacity();
E get(int index);
void remove(E e);
E removeAt(int index);
void add(E e);
int size();
}
- ArrayList 实现
public class ArrayList<E> implements List<E> {
private E[] data;
private int size;
public ArrayList() {
this(8);
}
public ArrayList(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException("capacity must be > 0");
data = (E[]) new Object[capacity];
size = 0;
}
@Override
public int capacity() {
return data.length;
}
@Override
public boolean isEmpty() {
return size == 0;
}
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("index out of bound : " + index);
data[index] = e;
}
@Override
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("index out of bound : " + index);
return data[index];
}
@Override
public void remove(E e) {
int index = 0;
while (index < size) {
if (e.equals(data[index]))
removeAt(index);
else
index++;
}
}
@Override
public E removeAt(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("index out of bound : " + index);
E ret = data[index];
for (int i = index; i < size; i++) {
if (i + 1 < size)
data[i] = data[i + 1];
data[i + 1] = null;
}
size--;
reduceIfNecessary(size);
return ret;
}
// 必要的时候缩容为原来的 1/2
private void reduceIfNecessary(int size) {
// 此处的 1/3是为了防止复杂度震荡, 只要不是且小于1/2就可以了
if (size <= data.length / 3) {
E[] newData = (E[]) new Object[data.length >> 1];
for (int i = 0; i < this.size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
@Override
public void add(E e) {
growIfNecessary(size + 1);
data[size] = e;
size++;
}
// 必要时扩容为原来的 2 倍
private void growIfNecessary(int newCapacity) {
if (newCapacity < data.length) {
return;
}
// capacity grow
E[] newData = (E[]) new Object[data.length << 1];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
@Override
public int size() {
return size;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < size; i++) {
builder.append(data[i]).append(" -> ");
}
builder.append("| element size is : ").append(size);
builder.append(" , and capacity is : ").append(data.length);
return builder.toString();
}
}
JDK ArrayList Demo的思考
先添加100个元素,在删除前90个元素观察容量的变化
public class ListMain {
public static void main(String[] args) throws Exception {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add(i);
System.out.println("添加元素: " + i + ", 数组容量:" + getListCapacity(list));
}
for (int i = 0; i < 90; i++) {
// 传入对象Integer 删除的是对应的对象, 如果传入的是 int 删除的是对应的index的数据
list.remove(Integer.valueOf(i));
System.out.println("删除元素: " + i + ", 数组容量:" + getListCapacity(list) + ", 剩余元素个数: " + list.size());
}
}
/**
* 获取容量
*/
private static int getListCapacity(ArrayList<Integer> list) throws NoSuchFieldException, IllegalAccessException {
Field elementData = list.getClass().getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] elements = (Object[]) elementData.get(list);
return elements.length;
}
}
运行结果:
添加元素: 0, 数组容量:10
...
添加元素: 10, 数组容量:15
...
添加元素: 16, 数组容量:22
... ...
添加元素: 99, 数组容量:109
删除元素: 0, 数组容量:109, 剩余元素个数: 99
...
删除元素: 89, 数组容量:109, 剩余元素个数: 10
JDK ListDemo 运行结果表明(JDK 版本 1.8.0_171)
- List 的remove()方法不会引起容量的变化(不会缩容), 类似于demo中的操作可能造成空间的浪费(PS:可能没有这么无聊的场景,但确实是个问题)
- remove(Object e), 方法是比较坑die的,原因在于该方法有一个重载方法remove(int index),如果List中存入的是Integer类型时,调用的时候需要小心, 在我的demo中如果去掉Integer.valueOf()回报异常: java.lang.IndexOutOfBoundsException: Index: 50, Size: 50
