摘要：
在实现动态数组之前，有必要先了解一下数据结构的概念？数据结构是计算机存储，组织数据的方式，常见的数据结构有线性结构，树形结构，图形结构等
线性结构：线性表（数组，链表，栈，队列，哈希表）
树形结构：二叉树（AVL树，红黑树，B树，堆，Trie，哈夫曼树，并查集）
图形结构：邻接矩阵，邻接表
这篇文章，我只是会记录到线性表中的数组，因为我也是在学习当中，其他很多东西都不懂，所以一步一步来
数组概念介绍
数组是一个有顺序存储的线性表,所有元素的内存地址是连续的，这个和链表不同的是，链表是不需要连续的内存的，如果我们申请一个100MB大小的数组，当内存中没有连续的，足够大的存储空间时，即便内存的剩余总可用空间大于100MB，也是无法申请成功的，但是100MB大小的链表，根本不会有问题，如下图所示：
数组声明int[ ] arrray = new int[ ]{11,22,33};
在内存中的表达形式如下：
在很多语言中，数组都有个致命的缺点，就是无法动态修改容量，所以在这里，我将实现一个动态数组
动态数组
动态数组接口设计
/* * 元素的数量 */private int size;
/* * 所有元素 */ private E[] elements;
int size();//元素数量
boolean isEmpty();//是否为空
boolean contains(E value);//是否包含某个元素
void add(E value);//添加元素到最后面
Item get(int index);//返回index位置对应的元素
Item set(int index,E value);//设置index位置的元素
void add(int index, E value);//往index位置添加元素
Item remove(int index);//删除index位置对应的元素
int indexOf(E value);//查看元素的位置
void clear();//清除所有
动态数组接口实现
构造函数实现
//构造函数
public ArrayList(int capacity) {
capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
//java 中只有生成一个Object数组才能实现泛型
elements= (E[])new Object [capacity];
}
清除元素实现
/** * 清楚所有元素 */
public void clear() { //消除对象的内存，如果是int可以直接size等于0，是因为int直接存在数组内存中
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
为什么需要将elements[i] = null;是因为如果不设置为null的话，内存中将会有大量的对象内存存放在对象中，画图分析一下
我们clear的时候要将对象地址设置为null，是为了释放对象的内存地址，如果仅仅是设置size 等于0，虽然别人是访问不到我们数组的内容，但是实际上，对象的内存地址还是存在的，如果将来不用了，那么这个内存一直存放在堆中，引起内存泄漏，假如现在对象是一个Person对象，然后Person对象，存放着很多成员变量，属性等，那么一个Person对象，可能就占用了很大的内存空间，这无疑是有问题的，所以调用clear的时候，一定要将内存地址设置为null，也就是上面的地址0，1，2，3，4，5，6等全部设置为null，设置为null之后，对象就没有了引用，对象销毁之后，对象的内存地址就可以回收掉了
添加元素
/* 添加元素到尾部*/
public void add (E element) {
add(size,element);
}
/* 在index位置插入一个元素*/
public void add (int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size+ 1);
for(inti=size;i>index;i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
顺序是从8-9,7-8,6-7,5-6 直接赋值给下标4
如果是C++的话，在clear的时候除开需要delete之外，还需要设置为null，因为没有自动机制，demo中会有实现的，具体下载demo观看，demo地址放到最后面
删除元素
public E remove(int index) {
rangeCheck(index);
E oldE=elements[index];
for(int i=index+ 1;i < size;i++){
elements[i - 1] = elements[i];
}
//移除最后一个对象内存
elements[--size] = null;
return oldE;
}
为什么是elements[i - 1] = elements[i]; 这样赋值呢，看图展示吧！
至于这个elements[--size] = null;是因为当我将9的元素赋值到8的时候，9的值也是要清空才会释放内存的呀，是吧~
但是上面的赋值语句是从5-->4，6->5,7->6,8->7,9->8 而不是9-->8,8->7,7->6,6->5,5->4这样的顺序,为什么是这样的顺序，想想应该就会明白了，避免覆盖，这个步骤和add相反的，add的时候，就是先赋值大的，再赋值小的
查看元素的索引
public int indexOf(E element) {
if(element==null) {
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;
}
扩展容量
private void ensureCapacity(int capacity) {
//容量足够，直接返回
int oldCapacity = elements.length;
if(oldCapacity >= capacity) return;
//容量不够，开始扩容1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
E []newElementsEs= (E[])newObject[newCapacity];
for(inti= 0;i < size;i++){
newElementsEs[i] = elements[i];
}
elements = newElementsEs;
capacity = newCapacity;
System.out.print(oldCapacity+"扩容为"+newCapacity);
}
elements = newElementsEs,将elements指向空间更大的数组
检查范围
private void rangeCheck(int index) {
if(index< 0 ||index>=size) {
outOfBounds(index);
}
}
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
@SuppressWarnings("unused")
private void rangeCheckForAdd(int index) {
if(index< 0 ||index>size) {
outOfBounds(index);
}
}
这里可以看到rangeCheckForAdd 和 rangeCheck的方法实现只是相差index 和size判断的一个条件而已，为什么rangeCheckForAdd是大于size，而rangeCheck的size值是大于等于呢？因为size值是添加元素时候的值，也就是说进行其他操作，例如删除操作的时候，其实size的值还没有元素的，只是在上一轮添加的时候size++了，所以这个时候删除元素的时候size索引对应的元素值是不存在的，所以这里rangeCheck判断的时候是需要将条件等于的情况加上的，因此形成了两种check索引的方法。
重写toString方法
@Override
public String toString() {
//TODO Auto-generated method stub
//size=3,[99,88,77]
StringBuilder stringBuilder=new StringBuilder();
stringBuilder.append("size=").append(size).append(",[");
for(inti= 0;i
if(i!= 0) {
stringBuilder.append(", ");
}
stringBuilder.append(elements[i]);
// if (i != size - 1) {
// string.append(", ");
// }
}
stringBuilder.append("]");
return stringBuilder.toString();
}
总结：
以上就是动态数组的一些设计思路，当然不是最好的，这个只是我学习路上的一个总结，demo中也会有C++的实现例子，如果想了解更多，请参考demo
