数据结构--顺序表

顺序表：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

1，自己实现一个基础的顺序表：

// 新增元素,默认在数组最后新增
void add(int data);
// 在 pos 位置新增元素
void add(int pos, int data);
// 判定是否包含某个元素
boolean contains(int toFind);
// 查找某个元素对应的位置
int indexOf(int toFind);
// 获取 pos 位置的元素
int get(int pos);
// 给 pos 位置的元素设为 value
void set(int pos, int value);
//删除第一次出现的关键字key
void remove(int toRemove);
void removeAll(int toRemove);
// 获取顺序表长度
int size();
// 清空顺序表
void clear();
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
void display();

首先我们建立一个类，建立一个数组和整数useSize的成员变量，数组用来放置数据或对象，整数用于记录下该数组的使用情况，如：数组存放了四个数据，则useSize为4。

1，display()，通过遍历数组，将每一个数组打印下来：

public void display() {
    if (isEmpty()){
        return;
    }
    for (int i = 0; i < useSize; i++) {
        System.out.print(array[i]+" ");
    }
    System.out.println();
}

2， size();顺序表的长度，也就是useSize的值

public int size() {
    return useSize;
}

3，contains，在遍历数组，看是否能找到相对应的数据

public boolean contains(int key) {
    for (int i = 0; i < useSize; i++) {
        if (array[i]==key){
            return true;
        }
    }
    return false;
}

4， indexOf，在contains的基础上，稍加改动，返回对应数据的下标

public int indexOf(int toFind) {
    for (int i = 0; i < useSize; i++) {
        if (array[i]==toFind){
            return i;
        }
    }
    return -1;
}

5， add，默认在数组的最后存放数据：1，看数组是否满了，如果满了，则将数组进行扩容【Arrays.copyOf】。2，需要找到最后一个数据的下一个下标，而这个下标为useSize的值,，将数据放入下标为useSize的空间中。3，useSize加一，说明数据量又增加了一个。

private boolean isFull(){
    return array.length==useSize;
}

public void add(int val) {
    if (isFull()){
        array= Arrays.copyOf(array,array.length*2);
    }
    array[useSize]=val;
    useSize++;
}

6，add(int pos, int data)：1，先判断输入的下标是否合法，如果不合法，要抛出异常。2，看数组是否满了，如果满了，则将数组进行扩容【Arrays.copyOf】。3，将输入的下标的数据，及以后的数据向后一个，然后将数据放入该下标。

（1），需要移几个数据呢？当useSize为4时，需要在下标为2的地方加入一个数据，则需要移4-2个数据，所以运用for循环，循环的次数为需要移动数据的次数

（2），下标什么时候算合法呢？当useSize为4时，可在下标为4及以前的地方增加数据，下标大于4或者小于0的地方即为不合法。

首先需要抛出异常，则需要写出一个异常

public class IndexNotLegalException extends RuntimeException{
public IndexNotLegalException(){

}

public IndexNotLegalException(String str){
    super(str);
}
}

private void isIndexLegal (int pos)throws IndexNotLegalException{
    if (pos>=useSize+1||pos<0){
        throw new IndexNotLegalException("下标异常");
    }
}

public void add( int pos,int val) {
    try {
    isIndexLegal(pos);
    }catch (Exception e){
        e.printStackTrace();
    }
    if (isFull()){
        array= Arrays.copyOf(array,array.length*2);
    }
        int cur = useSize;
        for (int i = useSize - pos; i > 0; i--) {

            array[cur] = array[cur - 1];
            cur--;
        }
        array[pos] = val;
        useSize++;

}

7，get：1，判断下标是否合法，不合法则抛出异常2，返回下标为pos 的数据的值

下标什么时候算合法呢？当useSize为4时，下标为4的地方就没有数据了，所以下标大于等于4或者小于0的地方即为不合法。

private void checkIndexGetSet(int pos)throws IndexNotLegalException{
    if (pos<0||pos>=useSize){
        throw new IndexNotLegalException("GetSet下标错误");
    }
}

public int get(int pos) {
    try {
        checkIndexGetSet(pos);
    }catch (Exception e){
        e.printStackTrace();
    }
    return array[pos];
}

8，set，与get方法相似，只是在改变下标为pos的数据

public void set(int pos, int value) {
    try {
        checkIndexGetSet(pos);
    }catch (Exception e){
        e.printStackTrace();
    }
     array[pos]=value;
}

9，remove：（1）将下标为pos之后的数据往前依次覆盖（2）useSize减一

首先遍历数组，找到要删的数值，获取下标 j=1。然后for循环，array[j]=array[j+1]，j++，j=2，array[j]=array[j+1]，这时，并不需要j++，因为j=3时，将下标为4的数据放到下标为3的地方时，会出现空指针异常，因为下标为四的地方没有数据。所以j的范围为j <=useSize-2

public void remove(int toRemove) {

    for (int i = 0; i < useSize; i++) {
        if (array[i]==toRemove){
            int tmp=i;
            for (int j = tmp; j <=useSize-2; j++) {
                array[j]=array[j+1];
            }
            useSize--;
            break;
        }
    }

}

10，removeAll，不可以在remove的基础上直接去掉break，因为删除一次后，顺序表的长度变了，数组内容也变了，所以for循环的条件也变了，所以单纯的删掉break并不能实现目的

public void removeAll(int toRemove) {
    while (contains(toRemove)) {
        for (int i = 0; i < useSize; i++) {
            if (array[i] == toRemove) {
                int tmp = i;
                for (int j = tmp; j <= useSize - 2; j++) {
                    array[j] = array[j + 1];
                }
                useSize--;
                break;
            }
        }
    }

}

11， clear：下面这种方法或者遍历数组将每个数据清零

public void clear() {
    useSize=0;
}

2，ArrayList的介绍：

（1）ArrayList有三种构造方法，分别为没有参数的，参数为整数的，参数为一个类型的

在没有参数的构造方法，数组的长度依旧为0；

有参数的构造方法中，参数就为数组的长度，对数组精修了初始化。如果输入的为0，则数组长度也为0；

将arrayList作为参数，传给ArrayList的构造方法中，arrayList的类型为Collection，

arrayList调用了collection接口，且arrayList的泛型与arrayList2的泛型类型一致，所以可以作为参数。

（2）为什么调用没有参数的构造方法时，数组的长度为0，但是却可以add数据？

我们可以通过add的底层代码逻辑，得出在数组长度为0时，会将数组的长度初始化为10，如果数组满了，也会进行1.5倍的扩容。

（3）remove方法，输入参数会自动认为为下标，而非要删除的值，所以我们需要将删除的值进行装箱，之后再作为参数，传入该方法中。

（4）subList方法，的参数是输入想要截取的前后下标，该区间为左闭右开区间。注意：list是下标为2的内存的地址，而不是又开辟了一块新的内存，将该区间的数值放到新的空间中去。所以如果改变list中的值，arrayList中的值也会发生改变。

（5）遍历数组

方法1：

System.out.println(arrayList);

方法2：

for (int i = 0; i < arrayList.size(); i++) {
    System.out.print(arrayList.get(i)+" ");
}
System.out.println();

方法3：

for (Integer x:arrayList){
    System.out.print(x+" ");
}
System.out.println();

方法4：（迭代器）

Iterator it= arrayList.iterator();
while (it.hasNext()){
    System.out.print(it.next()+" ");
}
System.out.println();

ListIterator it1= arrayList.listIterator(arrayList.size());
while (it1.hasPrevious()){
    System.out.print(it1.previous()+" ");
}
System.out.println();