数组是我们在编程的过程中最常用到的数据结构。一般我们用的都是定长数组，动态数组用的会比较少。但是有时，或者说有很多时候，定长数组并不能很好地满足我们的要求，于是我们只能用动态数组。在JAVA中，有一个封装好的API——ArrayList，就是一个动态数组，在C++中有一个vector也是动态数组。我们可以直接拿过来使用。但是有时我们可能需要自己定制一个动态数组，以便更好地解决我们的问题。今天，我们就来用JAVA实现一个动态数组。实现动态数组的方法有两种，一种是用定长数组实现（顺序表），另一种是用引用（链表）实现。今天我们讲的是定长数组实现的方法。
一、基本概念
1、数组是一个容器，可以存储同一类型的N个数据。数组是一种数据结构，直接通过下标进行定位，是数据结构中访问速度最快的一种。它属于引用数据类型（数组名中存储的是内存首地址）。 数组本身只有length属性（length获取数组中能存储的数据个数），但是有从Object父类继承的属性和方法。 2、数组在内存中的存储： 数组在内存中是一个连续的存储空间。 一维数组、二维数组、......
以二维数组为例，它的空间结构如下：
二、实现的基本思路(定长数组实现动态数组的)：
1、实现过程：首先先申请一个定长的数组空间Original，定义一个int型的数据len，记录当前已使用的空间大小，也就是动态数组的长度。然后在每次涉及到增加元素的操作中对当前动态数组的长度和已开辟的空间大小进行比较。如果len>=length，那么我们就新开辟一个大小为Original.length()*2的新定长数组，先把原来数组的信息赋值到这个新的数组中，再增加新的数据。如果len<length,我们可以直接在原来的定长数组中添加新数据。具体情况看下图
定长数组长度不足时
定长数组长度足够时
2、细节：
A、将待存储的数据定义为Object，因为Object是所有类的父类，因此我们就可以往这个数组中加入任何类型的数据。 B、有时我们要求数组中只能存储某一种数据类型，不能掺杂其他数据；有时我们又希望要求数组中可以存储任何数据类型。要满足这两个看似有些矛盾的要求就只能使用Java的泛型。泛型不是引用类型也不是基本数据类型；泛型是一种特殊的符号，它泛指Java中任何一种引用类型。泛型起到一个占位符的作用，之后在使用的过程中可以根据项目的具体需求来指定占位符的数据类型。
二、动态数组需要实现哪些功能
1.动态添加add方法；
2.获取任意位置的数据get方法；
3.返回当前动态数组的长度；
4.在任意位置插入数据的insert方法；
5.删除任意位置数据的delete方法；
6.合并其他数组的unite方法；
这里的话，前三个方法是必须要有的，后三个可有可无，根据具体的题目来决定。如果还需要其他方法可以自行增加。
三、具体代码和解析
//实现一个动态数组 public class DynamicArray<E> { //申请一个数组,初始定长是100 Object[] Original; private int startLength=100; int len=0;//当前长度 //不给数组的初始长度，使用默认的初始长度 public DynamicArray(){ Original=new Object[startLength]; } //给定初始数组长度 public DynamicArray(int startLength){ this.startLength=startLength; } //添加数据的方法 public void add(E o) { //当前所用长度和数组可用长度相等 if(len==Original.length) { //将数组的长度扩展一倍 Object[] newArray= new Object[Original.length*2]; //保存原来的值 for(int i=0;i<len;i++) newArray[i]=Original[i]; newArray[len]=o; //把原来的数组指向改变后的数组位置 Original=newArray; } else Original[len]=o; //当前元素个数增加1 len++; } //返回数组的长度 public int size() { return len; } //获取数据的方法 public Object get(int index) { return Original[index]; } //插入数据的方法 public void insert(E o,int position) { len++; if(len==Original.length) { Object[] newArray= new Object[Original.length*2]; for(int i=0;i<position;i++) newArray[i]=Original[i]; for(int i=position+1;i<len;i++) newArray[i]=Original[i-1]; newArray[position]=o; //把原来的数组指向改变后的数组位置 Original=newArray; } else { for(int i=position+1;i<len;i++) Original[i]=Original[i-1]; Original[position]=o; } } //删除数据的方法 public Object delete(int index) { //长度减少1 len--; //保存要删除的元素 Object element=Original[index]; //从index开始就需要从后往前替换 for(int i=index;i<len;i++) Original[i]=Original[i+1]; return element; } //合并另一个数组 public void unite(DynamicArray dArray) { //判断待合并的两个数组的大小和是不是比当前的定长数组要大 if(dArray.size()+len>Original.length) { Object[] newArray= new Object[(dArray.size()+len)*2]; for(int i=0;i<len;i++) newArray[i]=Original[i]; for(int i=len;i<(len+dArray.size());i++) newArray[i]=dArray.get(i); Original=newArray; } else { for(int i=len;i<(len+dArray.size());i++) Original[i]=dArray.get(i); } } } //定义一个测试类 public class Test { public int data; public Test(int data) { this.data=data; } public static void main(String[] args) { Test t1=new Test(1); Test t2=new Test(2); Test t3=new Test(3); DynamicArray dynamicArray=new DynamicArray(); dynamicArray.add(t1); dynamicArray.add(t2); dynamicArray.add(3); dynamicArray.insert(t3, 1); dynamicArray.delete(0); DynamicArray<Test>dynamicArray2=new DynamicArray(); dynamicArray2.add(t1); //dynamicArray2.add(3);//这个方法会报错，因为指定了泛型的具体数据类型 dynamicArray.unite(dynamicArray2); int len=dynamicArray.size(); System.out.println("length="+len); for(int i=0;i<dynamicArray.size();i++) { //这里需要强制转型 Object x=dynamicArray.get(i); Test changex=(Test)x; System.out.println(changex.data); } } }
四、反思总结
1.如果开辟了新数组，一定要把原来的Original指向新的数组，否则数组不会更新。因为函数中的数组属于局部变量，一旦这个被调用方法返回之后这个数组空间就会被释放了。
Original=newArray;2.这里我们选择的是双倍扩展数组空间，目的是为了降低算法的空间复杂度。如果采用每增加一个元素增加一个数组空间的话，每次添加函数都要进行一次赋值操作，该操作的时间复杂度是n，一旦n值较大，就会大大降低算法的运算效率
3.Object类是所有类的父类，因此我们这里在实现动态数组的时候参数类型设置为Object后就可以适用于任意类的对象。不过在获取这个动态数组的对象时，记得把得到的Object类强制转化为具体的类
//这里需要强制转型 Object x=dynamicArray.get(i); Test changex=(Test)x;