day2动态数组实现

摘要：

在实现动态数组之前，有必要先了解一下数据结构的概念？数据结构是计算机存储，组织数据的方式，常见的数据结构有线性结构，树形结构，图形结构等

线性结构：线性表（数组，链表，栈，队列，哈希表）

树形结构：二叉树（AVL树，红黑树，B树，堆，Trie，哈夫曼树，并查集）

图形结构：邻接矩阵，邻接表

这篇文章，我只是会记录到线性表中的数组，因为我也是在学习当中，其他很多东西都不懂，所以一步一步来

数组概念介绍

数组是一个有顺序存储的线性表,所有元素的内存地址是连续的，这个和链表不同的是，链表是不需要连续的内存的，如果我们申请一个100MB大小的数组，当内存中没有连续的，足够大的存储空间时，即便内存的剩余总可用空间大于100MB，也是无法申请成功的，但是100MB大小的链表，根本不会有问题，如下图所示：

数组VS链表

数组声明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

    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++;

}

未add之前

add 之后

顺序是从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

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

if(elements[i] == null) return i;

}

}else{

for(int i= 0;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

newElementsEs[i] = elements[i];

}

elements = newElementsEs;

capacity = newCapacity;

System.out.print(oldCapacity+”扩容为”+newCapacity);

}

elements = newElementsEs,将elements指向空间更大的数组

检查范围

private void rangeCheck(int index) {

if(index=size) {

outOfBounds(index);

}

}

private void outOfBounds(int index) {

throw new IndexOutOfBoundsException(“Index:”+index+”,Size:”+size);

}

@SuppressWarnings(“unused”)

private void rangeCheckForAdd(int index) {

if(indexsize) {

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