1：仿写一个ArrayList数组
主要为仿写JDK1.8的ArrayList数组
初始容量为0的可扩容的数组
1：初始容量为0 首次新增时赋予初始化容量
2：新增数据的时候 如果数组已满
则使用位移符申请原容量两倍的新数组并复制搬动数据
3：删除数据的时候 如果实际数据等于数组的四分之一
则使用位移符缩容成原容量的二分之一
* 1:getLength() 获取空间大小
* 2:getCount() 获取已有个数
* 3:get(int index) 获取对应 index 位置的元素
* 4:set(int index, T e) 修改 index 位置的元素
* 5: find(T e) 获取对应元素的下标, 未找到，返回 -1
* 6:contains(T e) 查看数组是否包含元素e
* 7:addFirst(T e) 向数组头插入元素
* 8:addLast(T e) 向数组尾插入元素
* 9:removeElement(T e) 删除 index 位置的元素，并返回
* 10:removeFirst() 删除第一个元素
* 11:removeLast() 删除末尾元素
* 12:removeElement(T e) 从数组中删除指定元素
2：代码实战
public class DynamicArrayList<T> {
//存储数据
private T[] data;
//定义实际个数
private int count;
private int capacity;
// 根据传入容量，构造Array
public DynamicArrayList(int capacity) {
data = (T[]) new Object[capacity];
count = 0;
}
// 无参构造方法，默认数组容量为5
public DynamicArrayList() {
this(0);
}
// 获取空间大小
public int getLength() {
return data.length;
}
// 获取已有个数
public int getCount() {
return count;
}
// 获取对应 index 位置的元素
public T get(int index) {
checkIndex(index);
return data[index];
}
// 修改 index 位置的元素
public void set(int index, T e) {
checkIndex(index);
data[index] = e;
}
// 获取对应元素的下标, 未找到，返回 -1
public int find(T e) {
for ( int i = 0; i < count; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查看数组是否包含元素e
public boolean contains(T e) {
for (int i = 0; i < count; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
// 在 index 位置，插入元素e
public void add(int index, T e) {
checkIndexForAdd(index);
if(0 == index){
this.capacity =5;
data = (T[]) new Object[capacity];
}
// 如果当前元素个数等于数组容量，则将数组扩容为原来的2倍
// 如2等于10（2机制） 向左挪动一位为 100 等于4
if (count == data.length) {
resize( data.length<<1);
}
for (int i = count - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
count++;
}
// 向数组头插入元素
public void addFirst(T e) {
add(0, e);
}
// 向数组尾插入元素
public void addLast(T e) {
add(count, e);
}
// 删除 index 位置的元素，并返回
public T remove(int index) {
checkIndex(index);
T ret = data[index];
for (int i = index + 1; i < count; i++) {
data[i - 1] = data[i];
}
count --;
data[count] = null;
// 缩容 如果此时实际的大小等于四分之一 则缩容
// 如8等于1000（2机制） 向右挪动两位为 10 等于2
// 如8等于1000（2机制） 向右挪动两位为 100 等于4
if (count == data.length >>2 && data.length >>1 != 0) {
resize(data.length >>1);
}
return ret;
}
// 删除第一个元素
public T removeFirst() {
return remove(0);
}
// 删除末尾元素
public T removeLast() {
return remove(count - 1);
}
// 从数组中删除指定元素
public void removeElement(T e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
// 修改容量算法，时间复杂度 O(n)
private void resize(int capacity) {
T[] newData = (T[]) new Object[capacity];
for (int i = 0; i < count; i++) {
newData[i] = data[i];
}
data = newData;
}
private void checkIndex(int index) {
if (index < 0 || index >= count) {
throw new IllegalArgumentException("校验index失败 index >=0 and index < count");
}
}
private void checkIndexForAdd(int index) {
if(index < 0 || index > count) {
throw new IllegalArgumentException("新增失败 ! Require index >=0 and index <= count.");
}
}
}
3：代码测试
private static void dynamicArrayListTest() {
DynamicArrayList<String> dynamicArrayList = new DynamicArrayList();
dynamicArrayList.addLast("sui");
dynamicArrayList.addLast("jin");
dynamicArrayList.addFirst("he");
System.out.println("空间大小 ：:"+dynamicArrayList.getLength());
System.out.println("==============================================");
for (int i = 0; i < dynamicArrayList.getCount(); i++) {
System.out.println(dynamicArrayList.get(i));
}
System.out.println("==============================================");
dynamicArrayList.add(1,"第一次插入到下标1");
dynamicArrayList.add(1,"第二次插入到下标1");
System.out.println("空间大小 ：:"+dynamicArrayList.getLength());
dynamicArrayList.add(1,"第三次插入到下标1");
System.out.println("空间大小 ：:"+dynamicArrayList.getLength());
System.out.println("==============================================");
for (int i = 0; i < dynamicArrayList.getCount(); i++) {
System.out.println(dynamicArrayList.get(i));
}
System.out.println("==============================================");
dynamicArrayList.set(1,"下标1 已经做了修改");
System.out.println("是否存在:"+dynamicArrayList.contains("下标1 已经做了修改"));
System.out.println("对应下标"+dynamicArrayList.find("下标1 已经做了修改"));
System.out.println("打印下标1 ：:"+dynamicArrayList.get(1));
System.out.println("==============================================");
for (int i = 0; i < dynamicArrayList.getCount(); i++) {
System.out.println(dynamicArrayList.get(i));
}
System.out.println("==============================================");
dynamicArrayList.removeFirst();
dynamicArrayList.removeLast();
dynamicArrayList.removeElement("下标1 已经做了修改");
dynamicArrayList.remove(2);
System.out.println("==============================================");
for (int i = 0; i < dynamicArrayList.getCount(); i++) {
System.out.println(dynamicArrayList.get(i));
}
System.out.println("==============================================");
}
项目连接
请配合项目代码食用效果更佳：
项目地址：
https://github.com/hesuijin/hesuijin-algo
Git下载地址：
https://github.com.cnpmjs.org/hesuijin/hesuijin-algo.git
arrayCollection包
