Java数据结构告诉你如何选用数据集合（2）顺序表
Java数据结构告诉你如何选用数据集合（2）顺序表
今天接着上次的内容详细讲，用Java实现一个顺序表。名字就取MyArrayList，有点随便。上次讲了，顺序表的实现是使用数组实现的，那么在编写顺序表的时候就需要一个成员数组。但是数组是定长的，要怎么实现增删呢？实现思路如下，后面再具体解释：
1、定义一个变量size，用来表示数组的长度，取一个合理的初始值
2、1、先创建一个定长的数组，长度为size
3、定义一个变量length代表MyArrayList的长度（这里要注意，不是数组的长度）
那么怎么实现的，首先创建MyArrayList的时候把数组创建出来。这个时候数组长度是size，而MyArrayList的长度是0。在MyArrayList当中，size和length是两个不同的值。size是实际数组的长度，而length是我们告知别人这个顺序表的长度。那么这个类的成员变量如下：
public class MyArrayList<T> {
//用来存数据的数组
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到队尾的数据->插入数据->把保存的数据赋值回来。删除大概也是这么个类似的流程。这样就消耗了很多资源，所以速度要慢。在数据少的时候感觉不到什么，数据量一大就有天朗之别。所以学习数据结构还是非常有必要的，今天就先到这里。