JAVAで線形リストの順次記憶構造ArrayListを実装する方法

コレクション ArrayList の基本構造は配列を使用します。主な実装メソッドは、要素を追加するときの配列の展開処理です。早速、コードに進みましょう:

/**
 * ArrayList底层使用数组结构，暴露方法，增删改查 其中元素增加，需要判断数组的长度
 */
public class MyArrayList<E> {
private Object[] array;// 存放元素的数组
private Object[] EMPTY_ARRAY = {};// 空数组
private static final int DEFAULT_CAPACITY = 8;// 默认数组长度
private int size;// 数组中元素的个数
private int modSize;// 线性表修改的次数
public MyArrayList() {
array = EMPTY_ARRAY;// 默认是给个空数组还是给个8个空间的数组呢？
}
public MyArrayList(int initCapacity) {
if (initCapacity < 0) {// 传入的数量为负数，抛出异常
throw new IllegalArgumentException("参数错误:" + initCapacity);
} else if (initCapacity == 0) {// 空数组
array = EMPTY_ARRAY;
} else {
array = new Object[initCapacity];
}
}
public MyArrayList(Collection<E> c) {
Object[] obj = c.toArray();
if ((size = obj.length) != 0) {// 将Collection中的数据拷贝出来，防止污染
System.arraycopy(obj, 0, array, 0, size);
} else {
array = EMPTY_ARRAY;
}
}
/**
* 添加一个元素到线性表尾部->先判断数组大小和元素个数是否相同－》相同的话，需要扩容
* 
* @param e
* @return
*/
public boolean add(E e) {
array = judgeIsGrow();
array[size] = e;
size++;
modSize++;
return true;
}
// 判断是否扩容
private Object[] judgeIsGrow() {
if (size == array.length) {
// 确定新数组的大小－－》new出来－－》将原来数组的数据拷贝到新数组中
int newSize = 0;
if (size == 0) {
newSize = DEFAULT_CAPACITY;
} else {
newSize = size < Integer.MAX_VALUE / 2 ? size << 1 : Integer.MAX_VALUE;
}
Object[] newArray = new Object[newSize];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
}
return array;
}
/**
* 在第index位置插入一个元素
* 
* @param index
* @param e
* @return
*/
public boolean add(int index, E e) {
checkArgument(index);
array = judgeIsGrow();
Object[] newObj = new Object[array.length];
// 将array数组中的元素拷贝到新数组中
System.arraycopy(array, 0, newObj, 0, index);
System.arraycopy(array, index, newObj, index + 1, size- index);
newObj[index] = e;
array = newObj;
size++;
modSize++;
return true;
}
// 参数检查
private void checkArgument(int index) {
if (index < 0) {
throw new IllegalArgumentException("参数错误:" + index);
} else if (index > size) {
throw new IllegalArgumentException("超过数组长度，参数错误:" + index);
}
}
/**
* 删除第index个元素
* 
* @param index
* @return
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
Object[] newObj = new Object[array.length];
E obj = (E) array[index];
// 将array数组中的元素拷贝到新数组中
System.arraycopy(array, 0, newObj, 0, index);
System.arraycopy(array, index + 1, newObj, index, size - index - 1);
array = newObj;
size--;
modSize++;
return obj;
}
@SuppressWarnings("unchecked")
public E get(int index) {
return (E) array[index];
}
public void set(int index, E e) {
array[index] = e;
}
public int size() {
return size;
}
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>();
for (int i = 0; i < 10; i++) {
list.add("data "+i);
}
list.add(2,"add23");
list.add(11,"dddd");
list.remove(3);
list.set(9, "dajdfljfl");
int size = list.size();
for (int i = 0; i < size; i++) {
System.out.println("元素："+(i+1)+" == " + list.get(i));
}
}
}

最終的な出力結果は次のとおりです:

Element: 1 == data 0

Element: 2 == data 1

Element: 3 == add23

要素: 4 == データ 3

要素: 5 == データ 4

要素: 6 == データ 5

要素: 7 == データ 6

要素: 8 == データ 7

要素: 9 = = データ 8

要素: 10 == dajdfljfl

要素: 11 == dddd