大家好，今天給大家?guī)淼氖琼樞虮?，我覺得順序表還是有比較難理解的地方的，于是我就把這一塊的內(nèi)容全部整理到了一起，希望能夠給剛剛進行學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人帶來一些幫助，或者是已經(jīng)學(xué)過這塊的朋友們帶來更深的理解，我們現(xiàn)在就開始吧

寫在前面

關(guān)于數(shù)據(jù)結(jié)構(gòu)，Java官方其實已經(jīng)幫我們寫好并封裝起來了，在真正需要使用的時候直接調(diào)用即可，但為了更好的理解數(shù)據(jù)結(jié)構(gòu)，我會按照源碼的思路寫一個簡化后的數(shù)據(jù)結(jié)構(gòu)，默認接收的數(shù)據(jù)為int

1.線性表

線性表是多個具有相同特性的數(shù)據(jù)元素的序列，線性表在邏輯上是一條連續(xù)的直線，但在實際存儲上卻不一定

順序表則是線性表的一種，是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，通常是使用數(shù)組來實現(xiàn)

2.順序表的實現(xiàn)

新建一個類叫做ArrList，順序表的底層是數(shù)組，所以類里面也要有數(shù)組，其次還需要一個計數(shù)器來判斷數(shù)組目前使用的空間是多少，那么順序表的框架就完成了

public class ArrList {
    public int[] arr;
    public int count;
    public ArrList() {
        this.arr = new int[5];  //初始給5個大小空間
    }
}

接下來就是順序表的增刪改查等操作了

2.1增加數(shù)據(jù)

增加數(shù)據(jù)有兩個方法：末尾增加數(shù)據(jù)和任意位置增加數(shù)據(jù)

2.1.1尾部增加數(shù)據(jù)

在這之前需要進行的一項工作是判斷順序表的空間是否已滿，如果空間已滿的話需要進行擴容，判斷順序表空間是否已滿的依據(jù)是計數(shù)器的值和數(shù)組的長度是否相等

public boolean isFull() {
        return this.count==this.arr.length;
    }
public void tailAdd(int data) {
        //首先判斷順序表是否已滿
        if(isFull()) {
            //順序表已滿，需要擴容，這里是擴大為原來的兩倍
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        //程序走到這，不管有沒有擴容，此時順序表都是未滿，直接添加數(shù)據(jù)
        this.arr[this.count]=data;
        this.count++;
    }

2.1.2任意位置增加數(shù)據(jù)

任意位置添加數(shù)據(jù)的話首先要判斷輸入的值是否是合法的，有一點要注意：如果輸入的值和計數(shù)器的值是相等的，那么此時就是在順序表末尾添加數(shù)據(jù)，這個數(shù)是合法的

public void add(int index,int data) {
        //首先需要判斷index的值是否合法，不合法直接拋出異常
        if(index<0||index>this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        if(isFull()) {
            //順序表已滿，需要擴容
            this.arr= Arrays.copyOf(this.arr,2*this.arr.length);
        }
        if(index==this.count) {
            this.arr[this.count]=data;
            this.count++;
        } else {
            //中間位置添加數(shù)據(jù)需要先把從此處開始到末尾的數(shù)據(jù)都往后移動一位，從后往前移
            for (int i = this.count-1; i >=index ; i--) {  
                this.arr[i+1]=this.arr[i];
            }
            this.arr[index]=data;
            this.count++;
        }
    }

2.2查找數(shù)據(jù)

輸入一個值，遍歷順序表進行查找，有則返回下標，沒有返回-1

public int find (int data) {
       for (int i = 0; i < this.count; i++) {
            if(this.arr[i]==data) {
                return i;
            }
        }
        return -1;
    }

之所以返回值是int而不是boolean是因為后面的刪除和修改數(shù)據(jù)的方法會使用到此方法

2.3刪除數(shù)據(jù)

找到要刪除的值的下標，從此處開始用后面的值對前面的值進行覆蓋，最后將尾部的值改為0

public void delData(int data) {
        int i=find(data);
        if(i!=-1) {
            for (int j = i; j <this.count-1 ; j++) {
                this.arr[j]=this.arr[j+1];
            }
            this.count--;
            this.arr[this.count]=0;
        }
    }

2.4修改數(shù)據(jù)

修改指定位置的值，依舊首先要判斷位置是否合法

public void setIndex (int index,int data) {
        if(index<0||index>=this.count) {
            throw new ArrayIndexOutOfBoundsException("位置非法");
        }
        this.arr[index]=data;
    }

最后是銷毀順序表，不需要吧數(shù)組進行銷毀，否則下次使用的時候還需要再實例化一個對象，只需要讓計數(shù)器為0即可

public void clear () {
        this.count=0; 
    }

3.ArrayList

Java中的順序表叫做ArrayList，這是一個泛型類，這個類繼承了多個其它類以及接口，其中包括List接口，List提供了很多抽象方法，ArrayList實現(xiàn)此接口對這些方法進行重寫

3.1ArrayList的實例化

ArrayList有三種構(gòu)造方法

ArrayList()	無參構(gòu)造
ArrayList(Collection<? extends E> c)	利用其他 Collection 構(gòu)建 ArrayList
ArrayList(int initialCapacity)	指定順序表初始容量

要說明的是：調(diào)用無參數(shù)構(gòu)造方法，默認數(shù)組的大小為0，之后在調(diào)用里面的方法（比如add方法）的時候會有專門的擴容的方法將其擴容為10，之后如果數(shù)組滿了的話擴容為之前的1.5倍（源碼里面套的方法太多就不展示了）

3.2ArrayList常用的方法

boolean add(E e)	尾插
void add(int index, E element)	將元素插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	刪除 index 位置元素
boolean remove(Object o)	刪除遇到的第一個指定的值
E get(int index)	獲取下標 index 位置元素
E set(int index, E element)	修改下標 index 位置的元素
void clear()	銷毀順序表
boolean contains(Object o)	判斷指定元素是否在表中
int indexOf(Object o)	返回第一個指定元素所在下標
int lastIndexOf(Object o)	返回最后一個指定元素的下標
List<E> subList(int fromIndex, int toIndex)	截取指定部分的元素