学习的最好方式就是写出来
欢迎光临我的个人小窝：http://wsfss.top
今天我们就手撸一个简单版的ArrayList吧
1、第一步，当然是先写接口类：List
- 二话不说就上代码
package com.fss.util;
public interface List<E> extends Iterable{
/**
* 在链表末尾增加一个元素
*/
boolean add(E e);
/**
* 获取指定位置的元素
*/
E get(int index);
/**
* 在指定位置添加元素
*/
boolean set(int index, E e);
/**
* 移除一个元素
*/
E remove(int index);
/**
* 获取链表长度
*/
int size();
/**
* 打印链表元素
*/
void print();
}
2、第二步，写接口实现类（好像是废话，哈哈）
package com.fss.util;
import java.util.*;
public class ArrayList<E> implements List<E> {
// 数组默认长度为10
private static final int DEFAULT_CAPACITY = 10;
// 数组元素默认为空
private static final Object[] EMPTY_ELEMENTDATA = {};
// 设定数组的最大长度
private static final int MAX_CAPACITY = Integer.MAX_VALUE;
// transient修饰符阻止变量序列化，防止该变量为空时序列化，提高序列化性能
transient Object[] elementData;
// 数组实际长度
private int size;
public ArrayList() {
this.elementData = EMPTY_ELEMENTDATA;
}
public ArrayList(int initCapacity) {
if (initCapacity > 0) {
this.elementData = new Object[initCapacity];
} else {
throw new IllegalArgumentException("数组初始大小不能小于等于0");
}
}
/**
* 在数组末尾增加一个元素
*/
@Override
public boolean add(E e) {
checkCapacity();
elementData[size++] = e;
return true;
}
/**
* 获取指定位置的元素
*/
@Override
public E get(int index) {
checkIndex(index);
return (E) elementData[index];
}
/**
* 在指定位置添加元素，index前的元素保持不变，index后的元素后移一位
*/
@Override
public boolean set(int index, E e) {
checkIndex(index);
checkCapacity();
System.arraycopy(elementData, index + 1, elementData, index + 1, size - 1);
elementData[index] = e;
return true;
}
/**
* 移除一个元素，index前的元素保持不变，index后的元素前移一位
*/
@Override
public E remove(int index) {
checkIndex(index);
E e = get(index);
// 从指定的源数组中复制一个数组，从指定位置开始，到目标数组的指定位置。 数组组件的子序列从src引用的源数组复制到dest引用的目标数组。 复制的组件数等于length参数。
// 源数组中位置srcPos到srcPos+length-1处的组件分别复制到目标数组的位置destPos到destPos+length-1
// 将 6,7,8,9,10,11,12,13,14 复制到 5,6,7,8,9,10,11,12,13 的位置
// 常用于数组间的赋值,在复制数据量庞大时,优先采用这种方法,因为该方法是对内存的直接访问,少了for遍历的寻址时间,因此,时间复杂度低,其弊端为,它是线程不安全的
System.arraycopy(elementData, index + 1, elementData, index, size - 1);
elementData[--size] = null;
return e;
}
/**
* 获取数组实际长度
*/
@Override
public int size() {
return this.size;
}
/**
* 打印数组元素
*/
@Override
public void print() {
System.out.println("数组有效元素个数: " + size);
System.out.println("数组实际长度: " + elementData.length);
}
/**
* 检查长度，判断是否需要扩容
*/
private void checkCapacity() {
if (size == elementData.length) {
this.grow();
}
}
/**
* 检查数组下标是否越界
*/
private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超过数组长度");
}
}
/**
* 数组容积增长，扩容属于耗时操作，这里设置每次扩容为当前数组长度的一倍
*/
private void grow() {
int oldCapcacity = elementData.length;
int newCapcacity = size == 0 ? DEFAULT_CAPACITY : oldCapcacity << 1;
if (newCapcacity - MAX_CAPACITY > 0) {
throw new OutOfMemoryError();
}
this.elementData = Arrays.copyOf(elementData, newCapcacity);
}
/**
* 重写迭代器，不迭代数组扩容后，为null的元素
*/
@Override
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor = 0;
int lastRet = -1;
// 设定迭代器的最大长度为数组的实际长度
int expectedModCount = size;
@Override
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
@Override
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = size;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (size != expectedModCount) {
throw new ConcurrentModificationException();
}
}
}
}
3、第三步，写完了，当然得跑起来看看对不对啦
package test;
import com.fss.util.ArrayList;
import com.fss.util.List;
import java.time.LocalDateTime;
public class TestList {
public static void main(String[] args) {
// 记录add耗时，查看性能如何，这里我试过1000万条数据大概是1秒多一点
System.out.println("计时开始：" + LocalDateTime.now());
List<Integer> list = new ArrayList<>();
for (int i=1; i<15; i++) {
list.add(i);
}
System.out.println("计时结束：" + LocalDateTime.now());
list.print();
print(list);
list.remove(4);
System.out.println("删除了下标为4的元素");
print(list);
list.set(4, 0);
System.out.println("在下标4的位置添加元素");
print(list);
}
public static void print(List<Integer> list) {
for (Object o : list) {
System.out.print(o);
System.out.print(",");
}
System.out.println();
}
}
- 运行结果：
计时开始：2021-12-02T17:19:29.362
计时结束：2021-12-02T17:19:29.365
数组有效元素个数: 14
数组实际长度: 20
1,2,3,4,5,6,7,8,9,10,11,12,13,14,
删除了下标为4的元素
1,2,3,4,6,7,8,9,10,11,12,13,14,
在下标4的位置添加元素
1,2,3,4,0,7,8,9,10,11,12,13,14,
