Java數據結構順序表的詳細講解

更新時間：2022年05月07日 08:46:47 作者：星鴉wyk

大家好，今天給大家?guī)淼氖琼樞虮恚矣X得順序表還是有比較難理解的地方的，于是我就把這一塊的內容全部整理到了一起，希望能夠給剛剛進行學習數據結構的人帶來一些幫助，或者是已經學過這塊的朋友們帶來更深的理解，我們現在就開始吧

寫在前面

關于數據結構，Java官方其實已經幫我們寫好并封裝起來了，在真正需要使用的時候直接調用即可，但為了更好的理解數據結構，我會按照源碼的思路寫一個簡化后的數據結構，默認接收的數據為int

1.線性表

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

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

2.順序表的實現

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

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

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

2.1增加數據

增加數據有兩個方法：末尾增加數據和任意位置增加數據

2.1.1尾部增加數據

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

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);
        }
        //程序走到這，不管有沒有擴容，此時順序表都是未滿，直接添加數據
        this.arr[this.count]=data;
        this.count++;
    }

2.1.2任意位置增加數據

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

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 {
            //中間位置添加數據需要先把從此處開始到末尾的數據都往后移動一位，從后往前移
            for (int i = this.count-1; i >=index ; i--) {  
                this.arr[i+1]=this.arr[i];
            }
            this.arr[index]=data;
            this.count++;
        }
    }

2.2查找數據

輸入一個值，遍歷順序表進行查找，有則返回下標，沒有返回-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是因為后面的刪除和修改數據的方法會使用到此方法

2.3刪除數據

找到要刪除的值的下標，從此處開始用后面的值對前面的值進行覆蓋，最后將尾部的值改為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修改數據

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

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

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

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

3.ArrayList

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

3.1ArrayList的實例化

ArrayList有三種構造方法

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

要說明的是：調用無參數構造方法，默認數組的大小為0，之后在調用里面的方法（比如add方法）的時候會有專門的擴容的方法將其擴容為10，之后如果數組滿了的話擴容為之前的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)	截取指定部分的元素