1. 什么是线性表
对于线性表的概念以及LinkedList和ArrayList的区别能够参考上篇文章。
Segment Fault
Bugkit
上面咱们间接看看如何用Java实现ArrayList
2. java实现
其中的抽象类AbstractList和接口List也是本人定义的，如须要看残缺代码，能够到文末的Github查看残缺代码。
/** * @param <E> Type of element * @author bugkit * @since 2021.10.27 */public class ArrayList<E> extends AbstractList<E> implements List<E> { // 存储元素的数组 private E[] data; // 元素的默认容量，最多只能装8个 private int capacity = 8; // 创立容量为8的数组 public ArrayList() { data = (E[]) new Object[capacity]; } // 创立容量为传入参数大小的数组 public ArrayList(int capacity) { this.capacity = capacity; data = (E[]) new Object[capacity]; } // 获取在data数组中的第i个元素 @Override public E get(int i) { if (i >= size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } return data[i]; } // 移除在data数组中的第i个元素 @Override public E remove(int i) { if (i >= size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } E e = data[i]; System.arraycopy(data, i + 1, data, i, size - i); size--; return e; } // 在data数组的第i个地位插入新的元素，如果i大于以后元素的个数则会报错数组越界 @Override public boolean add(E e, int i) { if (i > size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } if (size == capacity - 1) { resize(); } if (size + 1 - i >= 0) System.arraycopy(data, i, data, i + 1, size + 1 - i); data[i] = e; size++; return true; } // 增加元素到开端 @Override public boolean add(E e) { return add(e, size); } // 移除特定元素，如果元素存在则移除该元素并返回true，否则返回false @Override public boolean remove(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { remove(i); return true; } } return false; } // 判断ArrayList是否存在元素e @Override public boolean contains(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return true; } } return false; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("ArrayList { "); for (int i = 0; i < size; i++) { sb.append(data[i]).append(", "); } sb.replace(sb.length() - 1, sb.length(),"").append(" }"); return sb.toString(); } // 扩容，当add元素后，size == capacity，则会将ArrayList扩容为原来的两倍， // 并将原来的元素按程序拷贝到新的data数组 private void resize() { capacity = capacity * 2; E[] newData = (E[]) new Object[capacity]; System.arraycopy(data, 0, newData, 0, size); data = newData; }}