JAVA用数组实现动态数组——顺序表

数组是我们在编程的过程中最常用到的数据结构。一般我们用的都是定长数组，动态数组用的会比较少。但是有时，或者说有很多时候，定长数组并不能很好地满足我们的要求，于是我们只能用动态数组。在JAVA中，有一个封装好的API——ArrayList，就是一个动态数组，在C++中有一个vector也是动态数组。我们可以直接拿过来使用。但是有时我们可能需要自己定制一个动态数组，以便更好地解决我们的问题。今天，我们就来用JAVA实现一个动态数组。实现动态数组的方法有两种，一种是用定长数组实现（顺序表），另一种是用引用（链表）实现。今天我们讲的是定长数组实现的方法。

一、基本概念

1、数组是一个容器，可以存储同一类型的N个数据。数组是一种数据结构，直接通过下标进行定位，是数据结构中访问速度最快的一种。它属于引用数据类型（数组名中存储的是内存首地址）。
数组本身只有length属性（length获取数组中能存储的数据个数），但是有从Object父类继承的属性和方法。
2、数组在内存中的存储：
        数组在内存中是一个连续的存储空间。
        一维数组、二维数组、......

以二维数组为例，它的空间结构如下：

二、实现的基本思路(定长数组实现动态数组的)：

1、实现过程：首先先申请一个定长的数组空间Original，定义一个int型的数据len，记录当前已使用的空间大小，也就是动态数组的长度。然后在每次涉及到增加元素的操作中对当前动态数组的长度和已开辟的空间大小进行比较。如果len>=length，那么我们就新开辟一个大小为Original.length()*2的新定长数组，先把原来数组的信息赋值到这个新的数组中，再增加新的数据。如果len

定长数组长度不足时

定长数组长度足够时

2、细节：

A、将待存储的数据定义为Object，因为Object是所有类的父类，因此我们就可以往这个数组中加入任何类型的数据。
B、有时我们要求数组中只能存储某一种数据类型，不能掺杂其他数据；有时我们又希望要求数组中可以存储任何数据类型。要满足这两个看似有些矛盾的要求就只能使用Java的泛型。泛型不是引用类型也不是基本数据类型；泛型是一种特殊的符号，它泛指Java中任何一种引用类型。泛型起到一个占位符的作用，之后在使用的过程中可以根据项目的具体需求来指定占位符的数据类型。

二、动态数组需要实现哪些功能

1.动态添加add方法；

2.获取任意位置的数据get方法；

3.返回当前动态数组的长度；

4.在任意位置插入数据的insert方法；

5.删除任意位置数据的delete方法；

6.合并其他数组的unite方法；

这里的话，前三个方法是必须要有的，后三个可有可无，根据具体的题目来决定。如果还需要其他方法可以自行增加。

三、具体代码和解析

//实现一个动态数组
public class DynamicArray {
	//申请一个数组,初始定长是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;iOriginal.length) {
			Object[] newArray= new Object[(dArray.size()+len)*2];
			for(int i=0;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);
		
		DynamicArraydynamicArray2=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

Original=newArray;

			//这里需要强制转型
			Object x=dynamicArray.get(i);
			Test changex=(Test)x;