数据结构之动态数组(数据结构数组的基本操作)
数组（Array）
线性表
数组的特点
数组是一种顺序存储的线性表，数组内所有元素的内存地址都是连续的，
数组的长度一旦确定则不可更改
数组只能存储同一类型的数据
数组提供角标的方式访问元素
int[] array=new int[]{11,22,33,44,55} 复制代码
- array存放在栈空间中 - array数组中的元素放在堆空间中，每个数组元素占用4个字节 复制代码
数组的缺点
数组一般都是都无法动态修改容量，只有在初始化数组的时候固定好数组长度。
实际应用中，数据的容量都是动态改变的。
动态数组（Dynamic Array）
概念
动态数组是指在声明时没有确定数组大小的数组，可以根据用户需求可以自动增加或者减少数组空间，有效的利用空间。
接口设计
创建
ArrayList类，创建size属性来管理数组中元素的个数， 创建elements属性来管理存取的数据。可以对动态数组进行
增删改查操作。
package array; /** * @program: data-structure * @author: * @created: 2021/11/16 * 动态数组源码解析 */ public class ArrayList<E> { //元素的数量 private int size; //所有的元素 private E[] elements; //初始容量 private static final int DEFAULT_CAPACITY = 10; //查找不到元素就-1 private static final int ELEMENT_NOT_FOUND = -1; // 元素的数量 int size(); // 是否为空 boolean isEmpty(); // 是否包含某个元素 boolean contains(E element); // 添加元素到最后面 void add(E element); // 返回index位置对应的元素 E get(int index); // 设置index位置的元素 E set(int index, E element); // 往index位置添加元素 void add(int index, E element); // 删除index位置对应的元素 E remove(int index); // 查看元素的位置 int indexOf(E element); // 清除所有元素 void clear(); } 复制代码动态数组实现
构造方法
如果构造的数组长度小于默认长度，则会以默认长度构建数组。
public class ArrayList<E> { //元素的数量 private int size; //所有的元素 private E[] elements; //初始容量 private static final int DEFAULT_CAPACITY = 10; //查找不到元素就-1 private static final int ELEMENT_NOT_FOUND = -1; /** * 有参构造 * * @param capacity */ public ArrayList(int capacity) { //容量小于10一律扩充为10，三元表达式 capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity; elements = (E[]) new Object[capacity]; } /** * 无参构造，默认创建长度为10的数组 */ public ArrayList() { this(DEFAULT_CAPACITY); } } 复制代码查看数组元素数量
size的值，即为元素的数量。
public int size() { return size; } 复制代码数组是否为空
size为空，则表示数组为空
public boolean isEmpty() { return size == 0; } 复制代码数组是否包含某个元素
通过判断索引(indexOf)是否等于
ELEMENT_ON_FOUND即可。
public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } 复制代码根据索引获取对应位置的元素
通过数组下标进行查询
public E get(int index) { return elements[index]; } 复制代码根据索引和元素替换对应的老元素
先获取原来的元素，然后把新增的元素替换到原来的元素位置，并且返回原来index位置的元素
public E set(int index, E element) { E old = elements[index]; elements[index] = element; return old; } 复制代码添加元素
添加元素就是将指定位置之后的元素统一后移一位，并将指定元素插入到指定位置
数组越界
添加元素的时候索引的大小有限制，不能小于0, 也不能大于size。
private void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); } } 复制代码数组动态扩容（核心所在）
由于数组长度是默认长度为10，那么当数组存满元素，就需要对该数组进行扩容操作。
因为数组是无法动态增加的，就需要创建一个新的数组，并且数组容量一般都是原数组容量的1.5呗，然后将原数组的元素循环放入新数组中，这就是动态扩容。
private void ensureCapacity(int capacity) { // 获取当前数组的容量 int oldCapacity = elements.length; // 当前存储的元素个数 < 当前数组容量, 直接返回 if (oldCapacity >= capacity) { return; } // 创建新的新容量为旧容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //根据新的容量创建新数组 E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { // 拷贝原数组元素到新数组 newElements[i] = elements[i]; } // 引用新数组 elements = newElements; System.out.println("size=" + oldCapacity + ", 扩容到了" + newCapacity); } 复制代码数组添加实现
数组添加之前需要先验证索引是否越界
然后判断当前数组是否需要扩容操作
public void add(int index, E element) { //检查下标是否越界 rangeCheckForAdd(index); // 判断数组是否需要越界 ensureCapacity(size + 1); // 先从后往前开始, 将每个元素往后移一位, 然后再赋值 for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } // 复制 elements[index] = element; size++; } 复制代码删除元素
删除数组元素就是删除指定位置的元素，并将指定位置之后的元素统一前移一位
数组越界
移除元素的时候索引的大小有限制，不能小于0, 也不能大于等于size。
private void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } private void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); } } 复制代码动态缩容
当数组中的元素删除后，可能会导致数组的剩余空间很大，会造成
内存的浪费当删除数组中的元素，需要先判断是否打到缩容的条件，如果达不到，就不进行缩容处理
动态缩容实现方法类似于扩容，当数组中容量小于某个值时，创建新的数组，然后将原有数组中的元素
存入新数组即可。
private void trimToSize() { // 获取当前数组的容量 int oldCapacity = elements.length; //设置新数组的容量为原数组容量的0.5倍 int newCapacity = oldCapacity >> 1; // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回 if (size >= (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) { return; } //根据新的容量创建新数组 E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { // 拷贝原数组元素到新数组 newElements[i] = elements[i]; } elements = newElements; System.out.println("size=" + oldCapacity + ", 缩容到" + newCapacity); } 复制代码数组的删除实现
数组删除之前需要先验证索引是否越界
然后判断当前数组是否需要缩容操作
public E remove(int index) { rangeCheck(index); trimToSize(); E old = elements[index]; for (int i = index; i < size; i++) { elements[i] = elements[i + 1]; } elements[--size] = null; return old; } 复制代码查询元素的对应位置
通过循环查找元素的对应位置
注意：假如数组中可以存储
null，而null是不能调用equals方法的，所以需要对传入的元素进行判断，如果查找的元素是null，需要单独处理。当元素存在时返回索引，否则返回变量
ELEMENT_ON_FOUND的值。
public int indexOf(E element) { if (null == element) { for (int i = 0; i < size; i++) { if (elements[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) { return i; } } } return ELEMENT_NOT_FOUND; }
作者：努力的IT小胖子
链接：https://juejin.cn/post/7031836597448343560