构造动态数组(数据结构动态数组初始化)

写在前面

因为我们上篇实现的数组只能存放int类型，但是我们需要的是可以承载多种类型，甚至自定义对象的容器，所以本篇就来通过介绍数组的进阶修炼，来实现这个目的。

使用泛型

泛型是Java SE 1.5的新特性,泛型的本质是参数化类型,也就是说所操作的数据类型被指定为一个参数。使用泛型可以让我们的数据结构可以放置“任何”数据类型，注意既然是使用了泛型，因此不可以是基本数据类型，只能是类对象，要想使用基本数据类型就要使用它们对于的包装类对象。

基本数据类型是指byte,short,int,long,float,double,boolean,char。每个基本数据类型都有对应的包装类: Byte , Short, Integer , Long , Float , Double,Boolean,Character。

注意：只有int 和char其基本数据类型与对应的包装类有一个变形以外，其余的都是其首字母的大写而已。

我们可以通过装箱和拆箱来实现其基本数据类型和对应包装类之间的转换。

我们现在将前面的Array.Java文件，复制一份，名字为ArrayElement.java，里面修改泛型E（Element这只是一个元素的简称，你可以自己随意定义）。

泛型是不能通过new来创建一个数组的data = new E[capacity];这是错误的做法。我们知道java中的类都是隐式的继承Object类，因此可以先通过new Object[]这样的方式先创建Object数组，然后再进行强制类型转换为E[]即可。也就是这样的：

data = (E[]) new Object[capacity];

然后还要注意因为使用了泛型，因此对象的类型就都要修改为E了。当然对象的比较更不能使用==了，应该使用equals()方法:

public int find(E e){ for(int i =0;i前面我们好像说过在删除指定元素的时候，就是假如你删除的不是最后一个元素，那么那个元素向前挪了一步，把前面的元素给覆盖了，但是后面的却没有元素将它（就是最后一个元素（data[size]），删除的是最后一个元素就更不必说了）给覆盖，而是依然存留在那里，但是由于元素的数量减少了，因此你永远也访问不到它。

现在在使用泛型的使用，我们尽管也可以这么做（不去管它，任其流浪，最后被java的垃圾回收机制收回，过程很漫长），但是建议这里使用data[size] = null;立即调用java回收机制进行处理。

为什么呢？我们知道8大基本数据类型，在内存中存放的是数据本身，而引用数据类型在内存中存放的数据的引用地址。数据本身是不可以被修改的，但是引用地址却是可以修改的，因此如果你能把该空间进行释放那就可以继续使用了。尽管Java有自动的垃圾回收机制，但如果data[size]依旧存放着对对象的地址引用，就使得它不会被自动的垃圾回收机制给处理掉。因此使用data[size] = null;就能立即调用java回收机制进行处理，从而释放资源。

如果data[size]不置为null，它会被称为loitering Objects（游荡对象），一点用都没有，而且垃圾回收机制是不回收的。loitering Objects != memory leak只是为了程序优化而已，如果能手动去除它就更好了，因此最后添加data[size] = null;，你是在不想添加也是可以的。

现在我附上完整的ArrayElement.java文件里面的代码：

package com.suanfa.test.Array;public class ArrayElement { private E[] data; //数组 private int size; //数组中元素的个数 /** * 带容量参数构造函数 * * @param capacity 数组容量 * **/ public ArrayElement(int capacity){ data = (E[]) new Object[capacity]; size =0; } /*** * 默认的构造函数 * */ public ArrayElement(){ this(10); } /** * 静态数组入参构造函数 * @param data 传入静态数组 */ public ArrayElement(E[] data) { this.data = data; } /** * 获取数组元素个数 * * @return size 数组元素个数 */ public int getSize() { return size; } /** * 获取数组的容量 * * @return capacity 获取容量 */ public int getCapacity(){ return data.length; } /** * 判断数组是否为空 * * @return 是否为空 */ public boolean isEmpty(){ return size==0; } /** * 向所有元素末尾添加一个新元素。 * * @param e 添加的元素 */ public void addList(E e){// if(size ==data.length){// throw new IllegalArgumentException("对不起，数组容量已经满了，添加元素操作失败！");// }//// data[size ]=e; //这个和下面两行代码表达的意思一样，但还是建议分开写。// data[size] =e;// size ; add(size,e); } /** * 向所有元素开头添加一个新元素。 * * @param e 添加的元素 */ public void addFirst(E e){ add(0,e); } /** * 在第Index的位置，添加e元素 * * @param e 添加的元素，index 待添加元素的索引号 */ public void add(int index, E e){ if(size ==data.length){ throw new IllegalArgumentException("对不起，数组容量已经满了，添加元素操作失败！"); } if(indexsize){ throw new IllegalArgumentException("对不起，索引号必须在0和size之间"); } //注意数组的索引范围为0-length-1； //开始位置: size也就是最后一个元素（索引号size-1），目标位置：index（这个元素也是要挪移的），然后新的元素将其进行覆盖 for(int i =size-1;i>=index;i--){ data[i 1]=data[i]; } //将新的元素添加到index位置处 data[index]=e; //size每次都需要 1 size ; } /*** * 打印数组信息及遍历元素 * * @return 数组信息和元素遍历结果 * */ @Override public String toString() { StringBuilder res =new StringBuilder(); res.append(String.format("ArrayElement: size = %d, capacity = %dn",size,data.length)); res.append("["); for(int i =0;i后面新建一个ArrayElementTest.java文件，这个也是复制原来的ArrayTest.java里面的代码，注意现在使用了泛型，因此应该在调用的时候声明泛型表示的具体类型，这里使用Integer:ArrayElement ArrayElement=new ArrayElement(20);，这里附上完整的ArrayElementTest.java文件里面的代码：package com.suanfa.test.Array;public class ArrayElementTest { public static void main(String [] args){ //从java 1.7开始后面就可以不写前面的类型了 ArrayElement ArrayElement=new ArrayElement(20); for(int i =0;i你很好奇这里为啥只需要声明Integer，而不需要像前面那样修改e的类型，那是因为Integer可以通过自动拆箱的方式转变为int，同样int可以通过自动装箱的方式转变为Integer类型。

为了更好的理解这个，我们可以先建一个Student.java文件，里面写入代码：

package com.suanfa.test.Array;public class Student { private String name; private int score; public Student(String studentName,int studentScore){ this.name=studentName; this.score=studentScore; } @Override public String toString() { return String.format("Student(name:%s, score:%d)",name,score); } public static void main(String [] args){ ArrayElement studentArrayElement =new ArrayElement(); studentArrayElement.addList(new Student("小明",100)); studentArrayElement.addList(new Student("小红",99)); studentArrayElement.addList(new Student("小白",90)); studentArrayElement.addList(new Student("小明",100)); System.out.println(studentArrayElement); }}//运行结果ArrayElement: size = 4, capacity = 10[Student(name:小明, score:100),Student(name:小红, score:99),Student(name:小白, score:90),Student(name:小明, score:100)]

你知道的，数组中是可以存放重复的元素的，如果你想让它变成和set一样（其实所谓的set不允许存放重复元素，它是指不能存放String类型，因为它重写了针对String元素不重复的hashCode()和equals()方法）不允许存放重复元素，那你是不是只需要自己重写Object类的hashCode()和equals()方法就能实现这个类似的功能呢？答案是不可以！！！因为set的底层实现是map，说白了是根据key的值来进行判断是否重复的，因此只有底层实现了map才能实现这个功能。

动态数组

我们假设现在有这么一个场景，一个名为data的数组，里面size为4，容量为4，也就是说该数组已经满了，按照我们之前的逻辑，现在往里面添加元素是不可能的事了。那有没有方法，可以对其进行扩容呢？其实所谓的扩容就是新建另一个容量比它大的数组newData，然后把data数组的元素全部遍历复制过去，最后修改原数组data的指针指向就完成了“扩容”的目的。那你可能会说那原来的数组还存在啊，是存在的，但是因为我们这个数组是定义在类中，当没有对象指向它的时候就会被java的垃圾回收机制给处理掉。同样对于删除元素的时候，你可以使用类似的“缩容”方法来达到目的。

数组扩容

打开ArrayElement.java文件，修改在第Index的位置，添加e元素的代码：

/** * 在第Index的位置，添加e元素 * * @param e 添加的元素，index 待添加元素的索引号 */ public void add(int index, E e){ if(indexsize){ throw new IllegalArgumentException("对不起，索引号必须在0和size之间"); } //不使用扩容的方法// if(size ==data.length){// throw new IllegalArgumentException("对不起，数组容量已经满了，添加元素操作失败！");// } //使用扩容的方法 if(size ==data.length){ resize(2* data.length); } //注意数组的索引范围为0-length-1； //开始位置: size也就是最后一个元素（索引号size-1），目标位置：index（这个元素也是要挪移的），然后新的元素将其进行覆盖 for(int i =size-1;i>=index;i--){ data[i 1]=data[i]; } //将新的元素添加到index位置处 data[index]=e; //size每次都需要 1 size ; }

同时新增扩容方法的代码：

/*** * 对数组进行动态扩容 * * @return 扩容以后的新的数组 * */ private void resize(int capacity){ E[] newData = (E[]) new Object[capacity]; //创建一个新的数组 for(int i =0;i然后打开ArrayElementTest.java文件，修改里面的代码如下： //从java 1.7开始后面就可以不写前面的类型了 ArrayElement ArrayElement=new ArrayElement(); //默认数组容量为10 for(int i =0;i数组缩容

缩容和扩容是相反的操作，因此修改删除元素的代码，确定当数组size小于seze/2时，就进行该操作，缩小一半的容量。

打开ArrayElement.java文件，修改删除第Index位置的元素，并返回删除的元素代码：

/** * 删除第Index位置的元素，并返回删除的元素 * * @param index 待删除元素的索引号 */ public E remove(int index){ if(index=size){ throw new IllegalArgumentException("对不起，索引号必须在0和size之间"); } //注意数组的索引范围为0-length-1； //开始位置: index后面一个元素（索引号index 1），目标位置：index（这个元素也是要挪移的），然后新的元素将其进行覆盖 for(int i =index 1;i后面缩容的方法和扩容的方法一样，直接调用即可。

然后打开ArrayElementTest.java文件，直接调用原来的代码：

package com.suanfa.test.Array;public class ArrayElementTest { public static void main(String [] args){ //从java 1.7开始后面就可以不写前面的类型了 ArrayElement ArrayElement=new ArrayElement(); for(int i =0;i看到没有数组先进行了扩容，然后进行了缩容操作，就可以很好地实现数组的动态功能。

简单的复杂度分析

你可能之前听过O(1), O(n) , O(lgn) , O(nlogn) , O(n^2);等，这些就是大O表示法表示的算法时间复杂度。大O描述的是算法的运行时间和输入数据之间的关系。

我们来看一个非常简单的例子，就是对一个nums数组进行求和：

public static int sum(int[] nums){ int sum = 0; for(int num: nums) sum = num; return sum;}

我们就说上面的算法其时间复杂度是O(n)，为什么是这样呢？这里的n是指数组nums中含有n个元素，就是说这个算法的时间与n的个数成线性关系的（n是一次方）。n呈线性关系,线性关系表现在一次方。

那你就有疑问，为什么要用大O，叫做O(n)?

因为我们忽略了常数，实际时间 T=c1*n c2，大O是一个大概的数。

假设有3个算法，一个是T1=2n 2,另一个是T2=2000n 10000，按照刚才的表述它们的时间复杂度是相同的，都是O(n)。因为无论c1，c2是多少，只要符合线性关系T=c1*n c2都是O(n)的算法。

第三个算法T3=1nn 1，它的时间复杂度是O(n*2)，那么我们就会说第三个算法的性能不如前面两个。

那你肯定又要说了，假设n=10，此时T1=22，T2=30000，T3=101，那么性能最好的不应该是T1么，然后就是T3，怎么也轮不到T2啊。是的，你这样分析很对，但是我们这里所说的时间复杂度其实是指渐进时间复杂度。你肯定学过高等数学，里面有一个同阶无穷小的概念，和这个渐进时间复杂度的概念很相似。

渐进时间复杂度

渐进时间复杂度是指对于一个算法来说，我们常常需要计算其复杂度来决定我们是否选择使用该算法。它的定义是对于一个算法，假设其问题的输入大小为n，那么我们可以用 O(n) 来表示其算法复杂度。那么，渐进时间复杂度就是当n趋于无穷大的时候，O(n) 得到的极限值。

你可以理解为：我们通过计算得出一个算法的运行时间 T(n), 与T(n)同数量级的即幂次最高的O(F(n))即为这个算法的时间复杂度。例如：某算法的运行时间T(n) = n 10与n是同阶的（同数量级的），所以称T(n)=O(n)为该算法的时间复杂度。

算法的渐进分析就是要估计：n逐步增大时资源开销T(n)的增长趋势。

如果你还不了解的话，可以使用这个公式： 当n趋于无穷的时候，T(n)/O(n)=k(常数)，那么O(n)就是其渐进时间复杂度。

常见排序算法的时间复杂度一览表：

关于算法，我后面会专门有一套笔记去介绍它，这里你不用担心。

既然理解了这个概念，我们再来看一下这个算法T(n)=2*n*n 300*n 10，这里需要注意让含有高阶幂次项的时候，低阶幂次项可以忽略，而各个幂次项前面的常数以及后面的常数都是可以忽略的，因此这个算法的渐进时间复杂度用大O表示的也是O(n*2)。

动态数组的时间复杂度

我们现在来分析前面我们自己创建的动态数组的时间复杂度，体验一下。

添加操作

addLast(e) // O(1) 末尾添加，直接赋值，仅此而已。

O(1)就意味着它与我们的数组规模无关，不论数组n有多大，addLast都能在常数时间内完成，此时不考虑数组size的变化。

addFirst(e) // O(n) 首位添加，所有元素往后挪位

O(n)就意味着它与我们的数组规模有关，n越大，所需时间也就越长。n个元素，就要后挪n-1次。

add(index, e) //这个因为不知道index的位置，因此不确定，是一个概率问题。

尽管add(index, e)与index的取值有关，但是我们可以这样分析：在数轴上取出任何一个在[0,n]之间的一个数的概率都是相等的为1/n，然后根据概率论知识，就能求出时间期望n/2。或者平均的来看就是O(n/2)，也就是O(n)。（前面的常数1/2可以去掉）

(就是最后一个，这里a=0,b=n，因此期望E(x)=n/2)

因此添加操作综合来看，整体都是O(n)级别的。为什么呢？这里的addLast(e)它就是O(1)啊，是的没错，如果你每次都调用这个这个算法的复杂度确实是O(1)。但是那是在非常幸运的条件下得到的结果，而我们大O表示法往往考虑的则是最糟糕的情况。

别忘了如果数组容量已满的情况下，那么就需要扩容，其时间复杂度就是O(n)

resize // O(n)，触发扩容，一次添加n个元素

删除操作

removeLast() // O(1) 末尾删除，仅此而已。removeFirst() // O(n) 首位删除，所有元素往前挪位remove(index, e) //和add(index, e)一样，都是O(n/2)=O(n)

因此删除操作综合来看，整体也都是O(n)级别的。别忘了如果数组容量小于1/2的情况下，那么就需要缩容，其时间复杂度也是O(n)。

修改操作

set(int index,E e) // O(1)，无论多少，根据索引就能立即找到进行替换，数组的优势

数组的优势就是支持随机访问，只要知道索引号，就能立即找到该元素。

查询操作

get(index) // O(1),因为是根据index来获取对应位置的元素contains(e) // O(n)，因为首先需要遍历数组，然后才进行比较find(e) // O(n，)根据查找元素e在数组中的位置（索引号）,一般找不到该元素就返回-1

因此这个需要看实际情况，因为不同的场景下的O(n)就是不一样，这不是概率问题。

总结一下动态数组

增加和删除都是O(n)级别操作；改：已知索引O(1)级别操作，未知索引O(n)级别操作；查：已知索引O(1)级别操作，未知索引O(n)级别操作。

但是我们对于增加中，假如是末尾操作呢？我们说它依旧是O(n)，而不是O(1)，是因为里面涉及到了resize扩容，所以我们认为它是O(n)而不是O(1)。那看到这里这个resize好像是一个性能很差的操作，到底是不是呢？其实不是，因为对于resize的分析，我们依旧使用最差情况来进行判断这是不合理的，应当使用均摊复杂度进行分析。

均摊复杂度

关于均摊复杂度，其实在很多算法书中都不会进行介绍，但是在实际工程中，这样的一个思想是蛮有意义的：就是一个相对比较耗时的操作，如果我们能保证他不会每次都被触发的话，那么这个相对比较耗时的操作它相应的时间是可以分摊到其它的操作中来的。

我们现在以增加操作为例，进行均摊复杂度的分析，删除的操作类似。

前面说过增加不是有三个操作么：

addLast(e) // O(1) 末尾添加，直接赋值，仅此而已。addFirst(e) // O(n) 首位添加，所有元素往后挪位add(index, e) //O(n)

现在我仅仅只使用addLast(e)这个算法，那么它的渐进时间复杂度就是O(1)，在涉及到了resize操作（扩容）的情况下，渐进时间复杂度就变成了O(n)。所以综合来看就是O(n)级别的操作。其实这里我们忽略了这么一个问题，就是我们不可能每次都进行resize操作。我们设置的数组初始容量为10，也就是说必须先装满10个元素以后，这个数组才会进行扩容操作变成20，然后又需要装满后面10个元素才能进行扩容。

resize的时间复杂度分析

我们前面知道resize的时间的复杂度是O(n)，假设现在当前数组的capacity（容量）为10，并且每一次添加操作都是使用addLast()。这样前面10个的复杂度都是O(1)，在增加第11个元素的时候，触发resize，然后先将前面10个元素进行复制，接着添加第11个元素。11次addLast()操作，10次复制元素操作，一次resize，一共进行了21次基本操作。

21/11大概等于2，平均下来相当于每次addLast操作，进行2次基本操作。

推广一下，假设capacity为n, 第n 1次addLast()操作，触发resize，总共进行2n 1次基本操作，平均每次addLast操作，进行2次基本操作。

你看到了，平均每次addLast操作，进行2次基本操作，这样均摊计算时间复杂度是O(1)的。在这个例子中，均摊计算是比考虑最槽糕的情况是有意义的，因为只有最好的和最坏的出现的概率一样，我们考虑最坏的情况才是有意义的。这里明显概率不一样。所以addLast()的均摊复杂度是O(1)，自然removeLast的均摊时间复杂度也是O(1)。

复杂度的震荡

前面我们分开看addLast()和removeLast()，我们发现它们的均摊时间复杂度都是O(1)。但是当我们同时看addLast()和removeLast()操作的时候就会出现一个问题了 ！

假设我们现在有一个数组，它的容量为n，并且已经装满了元素，那么现在我们再调用一下addLast操作，显然在添加一个新的元素的时候需要resize扩容操作（扩容会耗费O(n)的时间），之后我们立即进行removeLast操作（根据我们之前的逻辑，在上一个操作里通过扩容，容量变为了2n，在我们删除1个元素之后，元素又变为了n = 2n/2。因此根据我们代码中的逻辑，又会触发缩容操作，同样耗费了O(n)的时间）

继续使上面的addLast、removeLast操作相继进行，你可能就有疑问了，前面我们均摊是进行了n个元素以后才会进行resize操作，这里似乎没有，仅仅只增加或者删除了一个元素就触发了resize操作，这就是复杂度的震荡。（同时看addLast和removeLast的时候，每一次都会耗费O(n)的复杂度）

为什么会出现这种情况，原因在于我们进行removeLast操作的时候，resize过于着急，就把容量缩了（Eager）。

防止复杂度的震荡

为了解决上面的那种问题，我们可以使用 Lazy懒惰的方法。记住添加元素时，容量不足的情况下，只能通过扩容来实现，这是没有疑问的。但是删除元素的时候，我们就不一定是当容量小于1/2的时候就开始缩容了，我们完全可以等一等，等到只需要1/4的时候再进行缩容1/2（此时剩余1/2，但是只使用了1/4），这样就能解决震荡问题。

也就是capacity==1/4，我们就缩capacity==1/2，剩余capacity==1/2（其中占用capacity==1/4，未使用capacity==1/4）。

这样懒一下，就使得算法性能变得更好，后面在介绍线段树的时候还有更懒的例子。但是并不是说，越懒代码越少，逻辑越简单，但是实际上并不是这样，相反则是更难。

现在用代码实现刚才的分析，打开ArrayElement.java文件，修改删除第Index位置的元素，并返回删除的元素代码，将原来的这段代码

if(size ==data.length/2){ resize(data.length/2);}

修改为：

//判断是否需要进行缩容,是的话缩容一半//设置缩容条件为1/4，而且数组长度不能为0if(size ==data.length/4 && data.length/2 !=0){ resize(data.length/2);}

注意一下整数除法，当length为1时等于0，而我们是无法new一个容量为0的数组，因此需要过滤掉。

这样关于数组的介绍就到此为止了，不知你发现没有，我们研究一种数据结构的时候，都是先研究它如何存取数据。在存取的基础上，然后再考虑如何进行增删改查操作，最后就是时间复杂度的分析，后面我们也是采取这种模式来研究其余的数据结构。

常用数据结构有哪些

数据结构分为8类有：数组、栈、队列、链表、树、散列表、堆、图。数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 

1、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

2、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。  

3、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 

5、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

6、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

7、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

8、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

参考资料来源：百度百科—数据结构

数据结构有关动态数组的c++怎么写啊

自己动手丰衣足食吧，动态数组就是指由程序员管理的内存空间。C++的话用new创造，用delet清理。int* p=new int[5];delete []p;