你不知道的Java小知识——动态数组实现(ArrayList原理) JAVASE

你不知道的JAVA小知识——动态数组实现(ArrayList原理) 什么是数组

同类数据元素的集合，在计算机中以连续的地址存储，编译时确定长度，无法改变。

什么是动态数组

数据结构中顺序表的物理实现，同类数据元素的集合，在计算机中以连续的地址存储，大小在创建时决定，但是可以改变。

为什么使用动态数组

支持随机访问,查询速度快。但是插入和删除都需要移动元素，比起链表开销较大。如：java集合类中的ArrayList Vector等

【你不知道的Java小知识——动态数组实现(ArrayList原理)】动态数组实现代码(ArrayList原理)

/** * 顺序表的实现 * @author chengh * @param */ public class ArrayList { private Object[] data = null; // data: 用来保存此线性表数据的数组 private int capacity; // capacity：线性表的容量 private int current; // current：当前数据的下标 /** * 初始化为声明大小，则设置为10。 */ ArrayList() { this(10); } /** * 初始化线性表，声明保存数据的数组大小。 * @param initialSize 顺序表的初始化大小 */ ArrayList(int initialSize) { if (initialSize >= 0) { this.capacity = initialSize; data = https://www.it610.com/article/new Object[initialSize]; current = 0; } else { throw new RuntimeException("初始化大小不能小于0：" + initialSize); } } /** * 在线性表的末尾添加元素，添加之前确认线性表是否已满 * @param e 待加入的元素 * @return */ public boolean AddElement(E e) { ensureCapacity(); data[current] = e; ++current; return true; } /** * 检查存储数据的数组容量，如果数组已经满，则扩充容量；否则不操作。 */ private void ensureCapacity() { int index; if (current == capacity) { capacity *= 2; Object[] newData = https://www.it610.com/article/new Object[capacity]; for(index = 0; index < current; ++index) { newData[index] = data[index]; } data = newData; } } /** * 返回下标为index的元素 * @param index 欲取得元素的下标 * @return */ public E get(int index) { validateIndex(index); return (E) data[index]; } /** * * @param index 待插入的位置 * @param e 待插入的元素 * @return */ public boolean set(int index, E e) { validateIndex(index); data[index] = e; return true; } /** * 验证下标值是否合法，非法时抛出异常 * @param index 待验证的下标值 */ private void validateIndex(int index) { if (index < 0 || index> current) { throw new RuntimeException("无效的下标：" + index); } } /** * 返回当前顺序表的大小 * @return */ public int size() { return current; } /** * 在指定位置插入指定元素 * @param index 待插入的位置 * @param e 待插入的元素 * @return */ public boolean insert(int index, E e) { validateIndex(index); ensureCapacity(); for (int temp = current; temp > index; --temp) { data[temp] = data[temp - 1]; } data[index] = e; return true; } /** * 删除下标为index元素 * @param index 待删除元素的下标 * @return */ public boolean delete(int index) { validateIndex(index); for ( ; index < current - 1; ++index) { data[index] = data[index + 1]; } data[current - 1] = null; --current; return true; } @Override public String toString() { String str = "[ "; for (Object o : data) { if (o != null) { str += o + " "; } } str += "]"; return str; } }