【数据结构和算法】|【数据结构和算法】 —— ArrayList 【数据结构和算法】——Arra

1. 什么是线性表关于线性表的概念以及LinkedList和ArrayList的区别可以参考上篇文章。
Segment Fault
Bugkit
【【数据结构和算法】|【数据结构和算法】 —— ArrayList】下面我们直接看看如何用Java实现ArrayList
2. java实现

其中的抽象类 AbstractList和接口 List也是自己定义的，如需要看完整代码，可以到文末的Github查看完整代码。

/** * @param Type of element * @author bugkit * @since 2021.10.27 */ public class ArrayList extends AbstractList implements List {// 存储元素的数组 private E[] data; // 元素的默认容量，最多只能装8个 private int capacity = 8; // 创建容量为8的数组 public ArrayList() { data = https://www.it610.com/article/(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 = https://www.it610.com/article/(E[]) new Object[capacity]; System.arraycopy(data, 0, newData, 0, size); data = newData; } }