🎓??線性表的概念

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常
見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的（比如鏈表），線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤

🎓??順序表

順序表的概念：
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

🔍📐動態順序表的實作

首先我們思考一個問題，順序表底層的資料結構是一個陣列，那么可以用這個陣列取代順序表，為什么要有這個順序表呢？？為什么要存在順序表呢？

我們可以簡單的這樣想，順序表是一種資料結構，一種用來描述和組織資料的方式，資料在記憶體中的存盤多種多樣，為了實作處理資料，實作不同的功能，就有了不同的資料結構，比如說，在計算陣列里的元素個數的時候，如果我們遍歷陣列，定義一個計數器，遇到非0計數器就+1，遇到0就結束程式，如果遇到資料是0和非0的數字交叉，或者我們存盤的資料本身就是0，這種演算法就是有問題的，陣列就很雞肋，因此我們通過順序表實作該功能，放一個數記錄一次，

🔍📐圖解順序表

接下來我們通過面向物件的思想來實作順序表，1.找物件向，這個順序表只有一個物件就是這個順序表，2.創建物件，順序表這個物件的成員屬性包括一個陣列，一個記錄陣列元素個數的標記usedsize，一個標識陣列容量的成員，之后使用物件，

創建成員屬性，呼叫構造方法初始化物件

public class MyArrayList {
    public int[] elem;//elem=null
    public int usedSize;//元素個數
    public static  int capacity = 10;//陣列容量要比元素個數多，否則就要擴容

    public MyArrayList() {
        this.elem = new int[capacity];
        //this.usedSize = 0;
    }

我們初始化物件后，物件，成員屬性的關系及記憶體布局大致如下：

?💦在順序表的某一個位置新增一個元素，大致分兩種情況，如下圖分析

 public boolean isFull() {//判斷陣列元素是否為滿的，滿了回傳ture,否則回傳false
        /*if(this.usedSize == capacity) {
            return true;
        }
        return false;*/
        return this.usedSize == capacity;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        if(pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法！");
            return;
        }
        //1、滿的情況   2、pos的合法情況
        if(isFull()) {
            //擴容
            this.elem =Arrays.copyOf(this.elem,2*capacity);//最少以兩倍容量擴充
            capacity *= 2;//新的容量
        }
        for(int i = this.usedSize-1; i >= pos;i--) {
            this.elem[i+1] = this.elem[i];//元素個數沒有達到陣列容量，i+1后不會越界
        }
        this.elem[pos] = data;//第一次沒有元素時添加新元素或在pos位置放置要新增的元素
        this.usedSize++;
    }

情況一

情況二

?💦列印順序表，遍歷陣列就行了

 // 列印順序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }

判定是否包含某個元素
判斷是否包含某個元素很簡單，遍歷陣列就行，函式回傳值boolean型別，找到為真回傳true，沒有找到為假回傳false

public boolean isEmpty() {
        return this.usedSize == 0;
    }
    // 判定是否包含某個元素
    public boolean contains(int toFind) {
        if(isEmpty()) return false;//如果為空直接回傳
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

?💦查找某個元素對應的位置，回傳對應的元素下標，如果順序表為空，沒有找到回傳-1

// 查找某個元素對應的位置
    public int search(int toFind) {
        if(isEmpty()) return -1;//只要回傳-1就是沒有找到
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

?💦獲取 pos 位置的元素
因為pos是作為陣列下標，回傳對應位置的元素的，所pos的取值為0~usedSize-1(包括兩個端點）

// 獲取 pos 位置的元素
    public int getPos(int pos) {
        if(isEmpty()) {
            //return -1; 業務的處理，回傳-1我們應該知道順序表此時是空的
            throw new RuntimeException("順序表是空的");//手動拋出錯誤(例外)
        }
        if(pos < 0 || pos >= this.usedSize) {//判斷位置的合法性
            throw new RuntimeException("pos不合法");//手動拋出錯誤(例外)
        }

        return this.elem[pos];
    }

獲取順序表長度，直接回傳成員屬性udedSize的值

 // 獲取順序表長度
    public int size() {
        return this.usedSize;
    }

?💦給 pos 位置的元素設為 value，pos也作為陣列下標，pos為0表示給0位置的元素，第一個元素設為value值，以此類推，所以判斷pos合法性的時候，pos要小于usedSize.

 // 給 pos 位置的元素設為 value
    public void setPos(int pos, int value) {
        if(pos < 0 || pos >= this.usedSize) {
            System.out.println("pos不合法！");
            return;
        }
        if(isEmpty()) {
            System.out.println("順序表為空！");//不判斷是否為空也行，如果為空，usedsize 為0了陣列長度為0，上面判斷pos的合法性，不論你輸入什么，都是不合法的
            return;
        }
        this.elem[pos] = value;
    }

?💦洗掉第一次出現的關鍵字key

 //洗掉第一次出現的關鍵字key
    public void remove(int toRemove) {
        if(isEmpty()) return;
        int index = search(toRemove);
        if(index == -1) {
            System.out.println("沒有你要洗掉的數字");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {//usedsize要減1，防止越界產生
            this.elem[i] = this.elem[i+1];//洗掉時向陣列下標小的位置移動
        }
        this.usedSize--;//最后一個沒有移動的元素也可以通過列印函式洗掉
    }

💥??清空順序表,把所有元素設定為0，元素個數usedSize也置為0即可，

 // 清空順序表
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0;
    }
}

💥??把上面的所有代碼復制到MyArrayList類里面就是完整的代碼，下面是一個測驗類，測驗順序表的功能的，

public class TestDemo {

    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();
        //myArrayList.add(-1, 1);
        myArrayList.add(0, 2);
        myArrayList.add(1, 3);
        myArrayList.add(2, 4);
        myArrayList.add(3, 4);
        myArrayList.remove(4);
    //    myArrayList.add(5, 4);
        myArrayList.display();
        }
        }

︿(￣︶￣)︿ (^▽) ( ＾?＾）／歡迎＼( ＾?＾）
記🉐點👍🏻🍹持👇🏻