java顺序表的无序表_Java数据结构告诉你如何选用数据集合（2）顺序表

今天接着上次的内容详细讲，用Java实现一个顺序表。名字就取MyArrayList，有点随便。上次讲了，顺序表的实现是使用数组实现的，那么在编写顺序表的时候就需要一个成员数组。但是数组是定长的，要怎么实现增删呢？实现思路如下，后面再具体解释：

1、定义一个变量size，用来表示数组的长度，取一个合理的初始值

2、1、先创建一个定长的数组，长度为size

3、定义一个变量length代表MyArrayList的长度(这里要注意，不是数组的长度)

那么怎么实现的，首先创建MyArrayList的时候把数组创建出来。这个时候数组长度是size，而MyArrayList的长度是0。在MyArrayList当中，size和length是两个不同的值。size是实际数组的长度，而length是我们告知别人这个顺序表的长度。那么这个类的成员变量如下：

public class MyArrayList {//用来存数据的数组private T[] data;//数组的长度private int size = 100;//顺序表的长度private int length = 0;/*** 构造方法*/public MyArrayList(){//在创建MyArrayList时，创建数组data = (T[])new Object[size];}｝

上面的代码很简单，因为要代码通用利用了泛型。那么我们来实现一下其他几个重要的方法，先是在队尾添加：

/*** 将数据插入到队尾* @param value 插入的值*/public void add(T value){//如果长度没有超过size，就直接添加元素if(length < size){data[length] = value;}else{//原数组不够用moreData();data[length] = value;}//长度增长length++;}

长度没超过size的时候大家都知道，直接在数组最后面加一个元素就好了。但是大于size再添加的话，会下标越界，这个时候就需要另外处理。这里使用自定义的moreData()方法，因为后面还有指定位置添加数据也要用到这个方法。下面一起给大家讲，再来看看指定位置添加数据：

/*** 指定下标插入* @param value 插入的值* @param index 插入的下标*/public void add(T value, int index){if(index >= size){System.out.println("下标越界无法添加");}else if(length + 1 > size){moreData();addDataByIndex(value, index);} else{addDataByIndex(value, index);}}

先是判断是否越界，再判断数组长度够不够。这里的话又有一个自定义方法addDataByIndex()，因为重复的关系，抽了出来。下面我们分别看一下moreData()和addDataByIndex()：

/*** 当元素组不够用时调用此方法*/private void moreData(){//把data数组原有的数据取出T[] temp = data.clone();//从新创建一个更长数组size += 50;data = (T[])new Object[size];//把temp中的数据复制回来并添加新的值for (int i = 0; i < temp.length; i++){data[i] = temp[i];}}

因为数组长度不能改变的缘故，当长度不够时，只能重新创建一个数组。但是在创建之前，要先把数组原数据记录下来(这里用了temp数组)，然后再把原数据放入变长后的data数组。

接下来是addDataByIndex()方法：

/*** 通过下标添加数据的实现* @param value 插入的值* @param index 插入的下标*/private void addDataByIndex(T value, int index){//创建一个数组存储index后面的数据T[] temp = (T[])new Object[length - index];for(int i = index, j = 0; i < length; i++, j++){temp[j] = data[i];}//插入数据data[index] = value;//补足后面数据for(int i = index + 1, j = 0; i < length+1; i++, j++){data[i] = temp[j];}length++;}

先把从index开始的数据保存下来，然后在index插入要插入的数据，然后再把index后面的数据重新赋值原先的。其实实际上就是从index个元素开始后移。

接下来就是删除数据。这里的话我图方便，简化了一下，没有考虑size的大小：

/*** 删除队尾的数据*/public void delete(){if(length > 0){length--;//复制数组中的数据T[] temp = data.clone();data = (T[])new Object[size];for(int i = 0; i < length; i++){data[i] = temp[i];}}else{System.out.println("没有可以删除的元素了");}}

这里就是把数据复制到temp当中，然后重新创建了一个data。再把除队尾的数据赋值回data。应该还有其它办法，这里只作为参考。

然后是通过下标删除：

/*** 删除指定位置的数据* @param index 下标*/public void delete(int index){if(index < 0 || index > length - 1){System.out.println("下标越界了");}else{length--;T[] temp = data.clone();data = (T[])new Object[size];for(int i = 0; i < length; i++){if(i < index){data[i] = temp[i];}else{data[i] = temp[i + 1];}}}}

这里就是要以index为界限了，前面的是照常赋值，之后的就要赋值后面一(i + 1)个了。还有一些其它方法大致，这里也就不详细实现了。

下面来解决两个问题：

①为什么顺序表查询快？

这里我们没有去实现查询方法，但是我们知道顺序表的底层实现是通过数组的。可以说顺序表的查询就是数组的查询，而且数据存储在相邻的内存，所以查询的时候快。

②为什么顺序表插入慢？

我们已经实现了插入和删除方法，会发现有多次复制。我们在对中插入，大概是这么一个步骤：保存index到队尾的数据->插入数据->把保存的数据赋值回来。删除大概也是这么个类似的流程。这样就消耗了很多资源，所以速度要慢。在数据少的时候感觉不到什么，数据量一大就有天朗之别。所以学习数据结构还是非常有必要的，今天就先到这里。