Java自定义ArrayList(顺序存储结构)和性能分析

1. 自定义ArrayList

首先我们先看一个案例：
假如一个球场的教练，安排球员（5个）上场
模拟数据存储的案例，模拟上场球员的球衣号码的存储。
（1）初始容量为5的线性列表，准备用来存储场上的5个球衣号码：[11,22,33,44,55]
（2）查询指定位置的球员球衣号码是多少，查询索引位置为2的球衣号码如：33；
（3）根据球衣号码查询该球员在场上的索引位置，44在球衣号码的球员在场上的索引位置是3
（4）替换球场上索引位置为2的球员，替换之后该位置的球衣编号为，333
（5）替换球衣号码为22的球员，替换之后为222；
（6）把场上索引位置为2的球员罚下场
（7）按照球员在场上的位置，打印出球衣的号码，打印风格[11,22,33,44,55]

其实一开始想通过这个案例，引出ArrayList，但是显得有点啰嗦，其实说到底，上面对球员的操作不过就是对数组的操作，在之前介绍数组时候，已经讲到了数组有关的简单操作，如数组元素的打印，拷贝，替换。

但是数组毕竟是一种简单的数据存储结构，存储的数据长度是固定的。因此，我们可以基于数组封装一个数据集合，更灵活的存储数据。

1.1 自定义要实现的方法（接口）

public void addEle(Object ele); // 添加元素 public Object findEleByIndex(int index); // 查询指定索引位置的元素 public int findIndexByEle(Object ele);// 查询指定元素的索引位置 public void replaceEleByIndex(Object newEle, int index);// 替换指定索引位置的元素 public void replaceEleByEle(Object ele, int newEle); // 替换指定的元素 public void deleteEleByIndex(int index); // 删除指定索引位置的元素 public void deleteEleByEle(Object ele); // 删除指定元素 public int getSize(); // 返回数组元素的个数 public boolean isEmpty(); // 判断数组中的元素个数是否为零 public void clear(); //清空数组集合 public String toString() // 覆盖父类(Object)方法，按格式打印数组 

1.2 自定义ArrayList类

class MyArrayList { private Object[] num = null; private int size = 0; private final static int DEFAULT_INIT_CAPACITY = 10;// 模型长度 public MyArrayList() { this(DEFAULT_INIT_CAPACITY); } public MyArrayList(int capacity) { if (capacity < 0) { throw new IllegalArgumentException("容量不能为负数"); } num = new Object[capacity]; } // 添加元素 public void addEle(Object ele) { // 判断是否需要扩容(性能非常低) // (1) 创建一个新数组 // (2) 把旧数组的元素拷贝到新的数组中 if (size == num.length) { Object[] newNum = Arrays.copyOf(num, num.length * 2 + 1); num = newNum; } num[size] = ele; size++; } // 查询指定索引位置的元素 public Object findEleByIndex(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("索引越界"); } return num[index]; } // 查询指定元素的索引位置 public int findIndexByEle(Object ele) { for (int i = 0; i < size; i++) { if (ele.equals(num[i])) { return i; } } return -1; } // 替换指定索引位置的元素 public void replaceEleByIndex(Object newEle, int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("索引越界"); } num[index] = newEle; } // 替换指定的元素 public void replaceEleByEle(Object ele, int newEle) { // 先查询该元素的索引位置 int index = findIndexByEle(ele); if (index < 0) { throw new IllegalArgumentException("该元素不存在"); } replaceEleByIndex(newEle, index); } // 删除指定索引位置的元素 public void deleteEleByIndex(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("索引越界"); } for (int i = 0; i < size - 1 - index; i++) { num[index + i] = num[index + i + 1]; } num[size - 1] = null; size--; } // 删除指定元素 public void deleteEleByEle(Object ele) { int index = findIndexByEle(ele); if (index == -1) { throw new IllegalArgumentException("所删除的元素不存在"); } deleteEleByIndex(index); } // 返回数组元素的个数 public int getSize() { return size; } // 判断数组中的元素个数是否为零 public boolean isEmpty() { return size == 0; } //清空数组 public void clear() { this.num = new Object[DEFAULT_INIT_CAPACITY]; size = 0; } // 按格式打印数组 public String toString() { if (num == null) { System.out.println("null"); } StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { sb = sb.append(num[i]); if (i != size - 1) { sb = sb.append(","); } } sb = sb.append(']'); return sb.toString(); } } 

1.2 定义测试类

public class ArrayListDemo { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.addEle(11); myArrayList.addEle(22); myArrayList.addEle("33"); myArrayList.addEle("44"); myArrayList.addEle("55"); myArrayList.addEle("66"); // 这里就开始扩容了 System.out.println(myArrayList.findIndexByEle("55")); System.out.println(myArrayList); } } 

输出：

4 [11,22,33,44,55,66] 

2. ArrayList性能分析

（1）保存操作
如果将新的数据保存在最后一个位置，至少需要操作1次；
如果将新加的数据保存在数组第一个位置，假设存在N个元素，此时需要操作N次（后面的元素往后移动N-1次，添加操作再算一次，一共操作N次）；

（2）删除操作
如果删除最后一个元素，操作1次；
如果删除第一个元素，操作N次；
平均 (N+1) / 2

（3）修改操作
操作一次

（4）查询操作
如果根据索引查询元素，操作1次；
如果根据元素查询索引：此时使用线性搜索，平均(N+1) / 2

总结
基于数组的结构做查询和修改是非常快的，但是做保存和删除操作就比较慢了。
如何保证保存和删除操作的性能？那就要用到链表数据结构了。

本文地址：https://blog.csdn.net/weixin_43519707/article/details/107885192