本文目标
理解动态数组,并能够实现简易的动态数组数据结构
先明确两个概念
|--- mSize是集合中真正元素的数量
|--- mElements是存放元素的数组,这个数组可能会很长,但是数组的长度并不等于实际元素的数量
扩容的思想
扩容的思想,就是把老的数组的数据复制一份,然后创建一个新的更大的新数组,把老数据塞进去
|---首先判断是否需要扩容,如果老的容量 >= 传进来的新的容量,不需要扩容
|---创建一个新的数组,容量是老的数组的容量的1.5倍
|---for循环老数组,然后把元素添加到新数组,从而实现扩容
缩容的思想
缩容的思想,把原有的数组的数据复制一份新然后塞到一个更小的数组中
|--- 每次remove的时候都去判断是否要缩容
|--- 先拿到现有的数组长度,然后除以2得到要缩容的新数组长度
|--- 如果当前的元素个数mSize > 新数组的长度,没必要缩容
|--- 如果缩容的新数组长度 < 默认的空间容量大小(默认的空间容量大小为10),没必要缩容
|--- 这些判断做好了以后,才可去进行缩容操作
|--- 创建新数组,然后遍历旧数组,把元素塞到新数组中,重新赋值当前的成员遍历mElements
顶层接口设计
基础API
int getSize() //元素的数量
boolean isEmpty() //是否为空
boolean contains(E element) //是否包含某个元素
增删改查清
void add(E element) // 添加元素到尾部
void add(int index, E element) //在index位置插入一个元素
E remove(int index) //删除index位置的元素
E set(int index, E element) //设置index位置的元素
void get(int index) //获取index位置的元素
clear() //清除所有元素
顶层接口List
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 元素的数量
* @return
*/
int getSize();
/**
* 是否为空
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 获取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
/**
* 清除所有元素
*/
void clear();
}
抽象的AbstractList
是对ArrayList和LinkedList的公共方法抽取,实现部分方法,然后部分方法,因为ArrayList和LinkedList有的方法实现方式不同
public abstract class AbstractList<E> implements List<E>{
protected int mSize; //元素的数量
/*
* 以下的API是基础组
*/
/**
* 元素的数量
* @return
*/
@Override
public int getSize() {
return mSize;
}
/**
* 是否为空
* @return
*/
@Override
public boolean isEmpty() {
return mSize == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
@Override
public boolean contains(E element) {
//索引不为-1就是有元素
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/*
* 正常的增删改查组清API有 add get set remove indexOf clear
* 能抽出来的只有add(e),其他方法ArrayList和LinkedList实现方式不尽相同
*/
/**
* 添加元素到尾部
* @param element
*/
@Override
public void add(E element) {
//直接调用自己的指定位置插入元素方法就好
add(mSize, element);
}
protected void rangeCheckForAdd(int index) {
if(index<0 || index>mSize) {
outOfBounds(index);
}
}
protected void rangeCheck(int index) {
if(index<0 || index>=mSize) {
outOfBounds(index);
}
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index"+index + "size"+mSize);
}
}
ArrayList
public class ArrayList<E> extends AbstractList<E> {
private static int DEFAULT_CAPACITY = 10;//默认的空间容量大小
private E[] mElements;//所有的元素
public ArrayList(int capaticy) {
int currentCaticy = capaticy>DEFAULT_CAPACITY ? capaticy:DEFAULT_CAPACITY;
mElements =(E[]) new Object[currentCaticy];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
/*
* 以下的API是 增删改查清组 add get set remove indexOf clear
*/
/**
* 添加元素到尾部
* @param element
*/
@Override
public void add(E element) {
//直接调用自己的指定位置插入元素方法就好
add(mSize, element);
}
/**
* 在index位置插入一个元素
* @param index
* @param element
* 需要倒着遍历数组,因为要插入一个元素,等于是从插入的位置向后都要往后走
* 就是说,先把插入位置之后的元素向后排,然后把要插入的位置空出来在进行赋值就好了
*/
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
//因为是add方法,所有要考虑扩容的问题
ensureCapacity(mSize +1);
//需要倒着遍历数组,因为要插入一个元素,等于是从插入的位置向后都要往后走
for(int x=mSize;x>index;x--) {
//这就是从要插入的位置开始,后面的元素都往后排了一位
mElements[x] = mElements[x-1];
}
//要插入的位置已经空出来了,赋值
mElements[index] = element;
mSize++;
}
/**
* 传入元素直接删除
*/
public E remove(E element) {
int index = indexOf(element);
return remove(index);
}
/**
* 删除index位置的元素
* @param index
* @return 删除掉的元素ֵ
*
* 因为要删除一个元素,那该元素后面的元素自然要往前走,只是数据的变化,其实内存还在
* 不允许删除一块内存中的部分内存,不允许的,然后这些个元素都往前走,但是最后一个元素所在的位置还是有引用指向堆内存的,需要设置为null
*/
@Override
public E remove(int index) {
rangeCheck(index);
E oldElement = mElements[index];
for(int x=index +1;x<mSize;x++) {
//把index后面的值赋值给前面索引的值
mElements[x-1] = mElements[x];
}
//自建索引自减
--mSize;
//最后一个元素置为null,要不然引用没断,上面的操作这是数据的变化
mElements[mSize] = null;
trim();
return oldElement;
}
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
@Override
public E set(int index, E element) {
rangeCheck(index);
//先把老的元素取出来是我了返回用
E oldElement = mElements[index];
//直接赋值就好
mElements[index] = element;
return oldElement;
}
/**
* 获取index位置的元素
* @param index
* @return
*/
@Override
public E get(int index) {
rangeCheck(index);
return mElements[index];
}
/**
* 查看元素的索引
* @param element
* @return
* 要考虑到传入的元素为null的情况,如果为null,则返回数组中第一个null的索引
*/
@Override
public int indexOf(E element) {
if(element ==null) {
for(int x=0;x<mSize;x++) {
if(mElements[x] == null) {
return x;
}
}
}else {
for(int x=0;x<mSize;x++) {
if(mElements[x] .equals(element)) {
return x;
}
}
}
return ELEMENT_NOT_FOUND;
}
/**
* 清除所有元素
*/
@Override
public void clear() {
//把所有对象置为null,然后就会自动切断引用连线
for(int x=0;x<mSize;x++) {
mElements[x]=null;
}
mSize=0;
//回到最初的状态
if (mElements != null && mElements.length > DEFAULT_CAPACITY) {
mElements = (E[]) new Object[DEFAULT_CAPACITY];
}
}
/*
* 确定扩容
* 扩容的思想,就是把老的数组的数据复制一份新的然后塞到一个更大的新数组中
* |---首先判断是否需要扩容,如果老的容量 >= 传进来的新的容量,不需要扩容
* |---创建一个新的数组,容量是老的数组的容量的1.5倍
* |---for循环老数组,然后把元素添加到新数组,从而实现扩容
*/
private void ensureCapacity(int capacity) {
//1.如果老的容量 >= 传进来的新的容量,不需要扩容
int oldCapacity = mElements.length;
if(oldCapacity >= capacity) {
return;
}
// 新容量为旧容量的1.5倍
//自己+自己的一半 就是1.5倍 位运算向右位移1位就是自身除以2,反之像左位移1位就是自身乘以2
int newCapacity = oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for(int x=0;x<mSize;x++) {
newElements[x] = mElements[x];
}
mElements = newElements;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
/*
* 缩容
* 缩容的思想,把原有的数组的数据复制一份新然后赛到一个更小的数组中
* |--- 每次remove的时候都去判断是否要缩容
* |--- 先拿到现有的数组长度,然后除以2得到要缩容的新数组长度
* |--- 如果当前的元素个数mSize > 新数组的长度,没必要缩容
* |--- 如果缩容的新数组长度 < 默认的空间容量大小(默认的空间容量大小为10),没必要缩容
* |--- 这些判断做好了以后,才可去进行缩容操作
* |--- 创建新数组,然后遍历旧数组,把元素塞到新数组中,重新赋值当前的成员遍历mElements
*/
private void trim() {
int oldCapacity = mElements.length;
int newCapacity = oldCapacity >> 1;
//如果当前的元素个数mSize > 新数组的长度,没必要缩容
//如果缩容的新数组长度 < 默认的空间容量大小,没必要缩容
if(mSize>newCapacity || newCapacity<DEFAULT_CAPACITY) {
return;
}
//创建新数组(容量更小),把老数组中的数据塞到新数组中
E[] newElements =(E[]) new Object[newCapacity];
for(int x=0;x<mSize;x++) {
E e = mElements[x];
newElements[x] = e;
}
mElements=newElements;
System.out.println(oldCapacity + "缩容为" + newCapacity);
}
@Override
public String toString() {
// size=3, [99, 88, 77]
StringBuilder string = new StringBuilder();
string.append("size=").append(mSize).append(", [");
for (int i = 0; i < mSize; i++) {
if (i != 0) {
string.append(", ");
}
string.append(mElements[i]);
}
string.append("]");
return string.toString();
}
}
总结
动态数组最核心的点在于增加和删除,要明白扩容的思想和缩容的思想,也要考虑一些边界条件
网友评论