So implementieren Sie die lineare, sequenzielle Speicherstruktur ArrayList in JAVA

Die zugrunde liegende Struktur der Sammlung ArrayList verwendet ein Array. Die Hauptimplementierungsmethoden sind Hinzufügen, Löschen, Ändern und Überprüfen. Der Kernteil ist die Array-Erweiterungsverarbeitung, wenn ein Element hinzugefügt wird. Kommen wir ohne weitere Umschweife direkt zum Code:

/**
 * 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));
}
}
}

Das endgültige gedruckte Ergebnis ist:

Element: 1 == Daten 0

Elemente: 2 == Daten 1

Elemente: 3 == add23

Elemente: 4 == Daten 3

Elemente: 5 == Daten 4

Element: 6 == Daten 5

Element: 7 == Daten 6

Element: 8 == Daten 7

Element: 9 == Daten 8

Element: 10 == dajdfljfl

Element: 11 == dddd