一、單鏈表的引出

在學習單鏈表之前，我們先了解資料結構中其他的表，

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

也就是說，線性表是存放相同特征的資料的有限序列，每一個元素都具有兩個值域，一個是存放元素資訊的data域，另一個是存放下一個元素的地址的next域，前面的元素存盤著下一個元素的next域，下一個元素再存盤它的下一個的next域，這樣這些元素一一相連就組成了線性表，我們這篇文章學習的單鏈表也是線性表的一種，

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

順序表是一種使用陣列存取的線性表，它一般可以分類為：

靜態順序表一般使用于已知需要存盤多少資料的場景，
靜態順序表可以會因為陣列長度N給大了，浪費空間，N給小了不夠用的問題，
與此相比，動態順序表可以先初始化一個小的陣列長度，用滿了在進行擴容，比靜態順序表更加靈活，

1->靜態順序表代碼實作

C語言版本

//靜態的順序表
#define N 100
typedef int SLDataType;
typedef int size_t;
typedef  struct SeqList
{
	SLDataType  array[N];//定長陣列
	size_t size;   //有效資料的個數
}Seqlist;

Java版本

 class SeqList{
    public  int []elem=new int[100];
    public  int usedSize;
    
 }

2->動態順序表代碼實作

C語言版本

//動態的順序表
typedef struct SeqList
{
	SLDataType * array;//指向動態開辟的陣列
	size_t  size; //順序表中有效資料的個數
	size_t  capicity; //順序表容量空間的大小
}SepList;

Java版本

public class MyArraylist {
    public int []elem;//只是定義了一個參考
    public  int usedSize;//有效資料的個數
    public  MyArraylist(){
        //一個無參的構造方法，呼叫后生成一個大小為5的陣列
        this.elem=new int[5];
    }
}

二、動態順序表的9種方法(函式)

以下代碼用Java語言演示

2.1、 新增元素

  // 在 pos 位置新增元素
    public void add(int pos, int data) {

    }

假如我們的順序表中已經有了3個元素，我們還需要在pos位置，繼續增加元素，那這時候問題來了，你傳參傳過去的pos合法嗎？順序表空間夠你放嗎？資料結構是一門邏輯非常嚴謹的學科，所以考慮的時候也一定要考慮全面，下面是add方法的實作思路:

0、當前的順序表有沒有滿： 如果當前的順序表滿了的話，那當然就放不了元素了，這時候需要擴容，那怎么判斷它有沒有滿呢？詳情可以先跳轉到目錄2.2，那擴容怎么擴容呢？詳情可以跳轉到目錄2.3，

1、pos位置是否合法 : pos位置的大小需要在順序表的大小范圍內，不能超出，假如你pos位置傳了一個-2過去，那一定是不行的，陣列就沒有-2下標啊，也不能傳大于陣列長度的pos，不然會陣列越界，在有一個需要考慮的點如果我要在4下標存盤資料可以嗎？4下標又沒有已經存盤的資料，而且也沒有陣列越界的情況， 答案是不可以！！！回到上文1.2中，提到了順序表是物理連續的也需要滿足邏輯上連續，假如4下標存放了88，但是3下標這時沒有元素，邏輯上并不連續，所以不可以隔著空新增元素，

插入元素的時候，一定要有一個唯一的前驅資訊

2、不能抹掉原來pos位置的元素：用上圖舉個例子，你要在elem[1]下標新增元素88，當前1下標存盤的是資料2，那要怎么移？總不能直接把資料2覆寫掉，在1下標直接加data吧，正確做法是從順序表的最后一個位置開始向后挪，把elem[2]的3挪到3下標，再把elem[1]的2挪到2下標，最后再把88添加到pos位置1上面，然后usedSize加1變成4，

上代碼~

  /**
     * isFull方法和CapacityExpansion方法在下面有代碼實作和講解
     * @param pos  要插入元素的下標
     * @param data   要插入的資料
     */
    public void add(int pos, int data) {
       //0、 滿了怎么辦？  ->擴容
        if(this.isFull()){
          //擴容
            CapacityExpansion();
        }
        //1、判斷下標是否合法
      if(pos<0 ||pos>this.usedSize){
          //下標不合法
          System.out.println("pos位置不合法");
          return;
      }
      //2、挪其他資料
        for (int i = this.usedSize-1; i >=pos ; i--) {
            this.elem[i+1]=this.elem[i];
        }
        //3、增加元素，usedSize++
        this.elem[pos]=data;
        this.usedSize++;
    }

2.2 、判斷當前順序表是否已滿

這個方法實作起來非常容易，滿和沒滿之間的關系就是usedSize和陣列elem.length的關系，如果他們相等就是使用的元素個數和當前陣列的個數相同就是滿了，回傳true，如果不想等就是沒有滿，回傳false

上代碼~

 //判斷是不是滿了
    public  boolean isFull(){
        if(this.elem.length==this.usedSize){
            return  true;  //滿了
        }
        return  false; //沒滿
    }

2.3 、擴容

用Arrays.copyOf方法將原來的陣列長度擴大兩倍即可，

    //擴容
    public  void  CapacityExpansion(){
        if(isFull()){
            //滿了
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
            //擴大至原來的兩倍，
        }

2.4 、判斷是否包含某個元素

這個方法實作起來很容易，for回圈遍歷順序表即可，如果陣列中的某個值和傳入的引數相同回傳true，要是遍歷完了還沒找到就回傳false，

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

2.5、 查找某個元素對應的位置

和2.4很類似，只不過需要在找到時回傳當前下標i，找不到時回傳-1即可，

// 查找某個元素對應的位置 找到回傳下標，找不到回傳-1
        public int search(int toFind) {
            for (int i = 0; i <this.usedSize ; i++) {
                if(this.elem[i]==toFind){
                    return i;
                }
            }
        return -1; }

2.6 、獲取 pos 位置的元素

需要先判斷pos的合法性，也就是pos需要在[0-usedSize]這個區間里，如果合法直接回傳elem[pos]即可，如果不和法丟出一個例外，

可能有小伙伴要問什么要這么麻煩丟例外？而不是回傳-1？
解釋：-1也有可能是當前陣列的元素啊，

// 獲取 pos 位置的元素
        public int getPos(int pos) throws UnsupportedOperationException{
        //先檢查pos的合法性  [0-usedSize-1]
        if(pos<0 ||pos>=this.usedSize){
            throw new UnsupportedOperationException("位置不合法") ;
        }
       return  this.elem[pos];
         }

2.7、 獲取順序表長度

順序表當前長度就是usedSize，直接回傳就好

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

2.8、 給 pos 位置的元素設為 value

相當于更新pos下標的值，還是要先檢查pos的合法性，如果不合法列印提示，如果合法直接修改pos下標的值即可，

// 給 pos 位置的元素設為 value  更新
        public void setPos(int pos, int value) {
       if(pos<0 ||pos>=this.usedSize){
           System.out.println("pos位置不合法");
           return;
       }
       this.elem[pos]=value;
        }

2.9 、洗掉第一次出現的關鍵字key

如下圖，當前順序表元素2出現了兩次，需要洗掉第一次出現的2，
實作思路：
1、先找到要洗掉的關鍵字的位置，把它記為index，并且在當前下標定義一個i，
2、[i]=[i+1] i++,意思是把i+1的元素賦值給i下標的元素，i再繼續往后走，i需要滿足 i<usedSize-1，
3、usedSize–因為要洗掉一個key，所以usedSize需要減一次，

代碼實作：

//洗掉第一次出現的關鍵字key
        public void remove(int key) {
        //先找到需要洗掉關鍵字的下標
                int index=this.search(key);
        if(index==-1){
            //沒有這個關鍵字
            System.out.println("沒有關鍵字key");
            return;
        }
            for (int i = index; i <this.usedSize-1 ; i++) {
                this.elem[i]=this.elem[i+1];
            }
            this.usedSize--;
        }

三、結尾

上面的這些方法就足順序表的使用了，大家加油哦！！！