🍉線性表

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

🍉順序表

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

🌵順序表概念及結構

順序表一般可以分為：
靜態順序表：使用定長陣列存盤，
動態順序表：使用動態開辟的陣列存盤，

靜態順序表適用于確定知道需要存多少資料的場景.
靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用
相比之下動態順序表更靈活, 根據需要動態的分配空間大小.

接下來詳細講解動態順序表的實作

🍌順序表介面實作（注釋非常詳細，我👴👴都能看懂）

先把這個順序表類的成員屬性和建構式寫好

然后就是實作接下來的一個個介面

🍈列印順序表

這里很簡單，就像遍歷陣列一樣，把順序表遍歷一遍即可

// 列印順序表
   public void display() {
       for (int i = 0; i < this.usedSize; i++) {//將有效元素遍歷并且列印
           System.out.print(this.elem[i]+" ");
       }
       System.out.println();
   }

🍈在pos位置新增元素

這里思路分為以下幾個步驟：

• ①判斷pos是否合法
• ②判斷順序表滿沒滿（這里還>需要額外寫一個判斷方法isFull()），滿了需要Arrays.copyOf()擴容
• ③pos之后的元素依次向后移動個位置
• ④將目標元素data放入這個pos位置

//判斷順序表是否滿了
public boolean isFull() {//判斷方法就是將有效元素個數和陣列長度比較
       if (usedSize==elem.length)//如果兩者相等，說明這個陣列已經裝滿了
        return true;
       else
           return false;
 }

// 在 pos 位置新增元素
   public void add(int pos, int data) {
       if (pos>=0 && pos<=usedSize){ //首先保證pos得是合法的
          if (isFull()){//判斷容量是否已經滿了
              this.elem = Arrays.copyOf(this.elem,this.elem.length+1);//滿了得擴容
          }
          for (int i = usedSize-1 ; i >= pos ; i--){
          //要從后往前移動，不能從前往后移，這樣前一個位置的值移到后一個位置的值上，
          //那后一個位置上的值就會被覆寫，導致后邊的所有值都變成與第一個移動的值一樣
              elem[i+1] = elem[i];//從新增元素位置之后的所有元素整體往后移動 1位
          }
          this.elem[pos] = data;//向pos位置插入資料
          this.usedSize++;//有效元素+1
       }
       else
           System.out.println("位置不合法");
   }

🍈獲取順序表長度

這個很簡單，獲取成員屬性的有效長度useSize就可以了

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

🍈判斷是否包含某個元素

傳入需要查找的元素，然后在所有有效元素中依次查找

// 判定是否包含某個元素
   public boolean contains(int toFind) {
       for (int i =0 ; i<usedSize ; i++){//在有效元素里依次查找
           if (elem[i]==toFind)
           return true;
       }
       return false;
   }

🍈查找某個元素對應的位置

這里可以用遍歷有效元素就好了和上邊一樣，我只不過想復習一下二分查找，因為二分查找雖然也是一種遍歷，但是可以很好的提高遍歷的效率

// 查找某個元素對應的位置（復習一遍二分查找）
   public int search(int toFind) {
       int left = 0; //設定一個左下標
       int right = elem.length-1;//再設定一個右下標，值為陣列長度-1
       while (left <= right) {//回圈查找，條件就是左下標<=右下標
       //=號不要忘，不然會漏掉一種情況（所查值為最后一個元素的情況）
           int mid=(left+right)/2;//設定中間值，用來減半需要遍歷的元素，提高效率
           if (elem[mid]<toFind){//如果這個中間值小于目標值，就把這個中間值的下一個元素設為左值
              left = mid+1;
           }//與上邊同理
           else if (elem[mid]>toFind){
               right = mid-1;
           }
          else//如果這個中間值既不大于也不小于目標值，那這個中間值就是所要查找目標值，回傳其下標就好了
               return mid;
       }
       System.out.println("沒有這個數");
      return -1;
   }

🍈獲取pos位置的元素

傳入一個位置，先判斷這個位置是否合法，合法的話直接回傳這個位置上的元素就好了

// 獲取 pos 位置的元素
   public int getPos(int pos) {
       if (pos>=0 && pos<=usedSize)//判斷位置是否合法
           return elem[pos];
       else
       return -1;//如果位置不合法回傳-1表示位置不合法
   }

🍈給pos位置的元素設為value

依舊先判斷位置是否合法，合法的話，直接將value賦值給這個位置覆寫掉原資料

// 給 pos 位置的元素設為 value
   public void setPos(int pos, int value) {//傳入位置和想賦予的值
       if (pos>=0 && pos<=usedSize){//判斷是否合法
          elem[pos]=value;
       }
       else
           System.out.println("pos非法");
   }

🍈洗掉第一次出現的資料

先呼叫上邊已經寫好的查找介面判斷是否有這個資料，如果有的話，就從此資料開始依次將當前資料的下一個資料覆寫當前資料實作洗掉功能不要忘了有效元素-1

//洗掉第一次出現的關鍵字key
   public void remove(int toRemove) {
       if (-1==this.search(toRemove)){
           System.out.println("沒有這個元素");
       }
       else{
           int index = this.search(toRemove);//獲得要洗掉資料的位置（下標）
           for (int i = index ; i<usedSize-1 ; i++)//從此資料開始依次將當前資料的下一個資料覆寫當前資料實作洗掉功能
         elem[i]=elem[i+1];
           usedSize--;//注意洗掉一個元素之后，整個順序表的有效元素也要-1嗷
       }
   }

🍈清空順序表

這里就用最粗暴的辦法，直接將有效元素個數清零，其實不用管陣列元素是否都變成0，因為下一次使用的時候又會有新的資料覆寫上去

// 清空順序表
   public void clear() {
       this.usedSize = 0;
   }

🍌順序表的缺陷

• 1. 順序表中間/頭部的插入洗掉，時間復雜度為O(N)
• 2. 增容需要申請新空間，拷貝資料，釋放舊空間，會有不小的消耗，
• 3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個資料，后面沒有資料插入了，那么就浪費了95個資料空間，

鏈表會不會存在以上的問題呢？請往下看👇👇

🍉鏈表

🌵鏈表概念及結構

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的 ，

鏈表結構非常多樣，以下情況組合起來有8種鏈表結構：

• 單向、雙向
• 帶頭、不帶頭
• 回圈、非回圈

我們重點學習以下兩種鏈表

🍌無頭單向非回圈鏈表介面實作（注釋非常詳細，我👴👴都能看懂）

先寫兩個類，一個是鏈表類（包含有一個可變的頭結點和實作各種功能的介面，因為是無頭鏈表，所以這個頭結點是可變的），一個是節點類（成員屬性有value和next）


接下來的介面都是寫在鏈表類里的，因為鏈表是一個物件，我們要實作的就是一個鏈表物件所有的功能

🍈列印鏈表

列印鏈表其實和列印順序表類似，遍歷鏈表就好了，不過要注意一個點，這里需要引入一個區域變數cur來代替頭節點去遍歷，因為頭結點在沒添加或者洗掉節點之前是固定的，不要讓頭結點變來變去

//列印鏈表
   public void display(){
       ListNode cur = this.head;//利用創建一個區域變數cur來替代head，這樣頭結點就不會改變了
       while (cur!=null) {//遍歷的條件就是下一個節點的參考（地址）不為null
           System.out.print(cur.value+" ");
           cur = cur.next;//找到下一個節點
       }
       System.out.println();
   }

🍈頭插法插入

顧名思義，頭插法就是從頭部插入節點，使新創建的節點成為新的頭結點，這里需要額外考慮一個點，就是頭結點是否存在（鏈表是否為空），不過以下代碼能處理頭結點為空的情況（注意要先將原頭結點的地址先存入新節點，再將新節點參考賦給原頭結點成為新頭結點）

//頭插法
   public void addFirst(int data){
        ListNode node = new ListNode(data);//創建新節點并初始化節點的data
        node.next = this.head;//將當前頭結點地址存到新節點的next里
        this.head = node;//將新創建的節點變為頭結點
        //這兩行代碼包含了頭結點為null的情況
   }

🍈尾插法插入

尾插法不同于頭插法，必須先判斷鏈表是否為空（判斷頭結點是否為null），然后引入區域變數cur遍歷鏈表，直到cur.next為空的時候，說明找到尾節點了，此時的cur就是尾巴結點

//尾插法
   public void addLast(int data){
   //找尾巴，cur.next為null了，說明這是尾節點了
       ListNode node = new ListNode(data);//創建新節點并初始化節點的data
       if (this.head == null){ //尾插的第一次必須判斷頭結點是否為空
           this.head = node;//如果是第一次插入，則新節點就是頭結點
       }
       ListNode cur = this.head; //引入區域變數cur遍歷鏈表
           while(cur.next != null){ //next等于null了就跳出while了
               cur = cur.next;//找到下一個節點
           }
       cur.next = node;
   }

🍈查找是否包含關鍵字key在單鏈表當中

傳入關鍵字key，依舊引入區域變數cur遍歷鏈表，哪個節點的value等于key了，說明鏈表里有這個關鍵字，回傳true，否則回傳false

//查找是否包含關鍵字key是否在單鏈表當中
   public boolean contains(int key){
       ListNode cur = this.head;//引入區域變數cur遍歷
           while(cur != null){//回圈條件為節點參考不為null
               if (key == cur.value)
                   return true;//如果找到了，回傳true
               cur = cur.next;//找到下一個節點
           }
           return false;
   }

🍈得到單鏈表的長度

依舊采取參考區域變數cur來遍歷鏈表，還要多設定一個區域變數size來計數，只要節點不為null，size就+1，最后回傳size的值就是鏈表長度了

//得到單鏈表的長度
   public int size(){
       int size=0;//引入區域變數來計數
       ListNode cur = this.head;
          while(cur != null){//遍歷并計數
              size++;//節點不為null，計數器+1
              cur = cur.next;//找到下一個節點
          }
          return size;//回傳鏈表長度
   }

🍈任意位置插入,第一個資料節點為0號下標

首先得判斷你要插入的這個位置是否合法，然后這里需要額外寫一個查找插入位置前一個節點的方法findIndex()用于插入節點，插入原理

//根據傳入的index查找前一個節點并回傳地址
   public ListNode findIndex(int index){
       ListNode cur = this.head;//引入區域變數遍歷至index前一節點
       while (index-1 != 0){//停止條件就是index-1等于0了
       //也就是說遍歷到index位置上一個節點了
           cur = cur.next;//向后遍歷
           index--;//每向后找一個節點index減1
       }
       return cur;//回傳index上一個節點參考
   }
//任意位置插入,第一個資料節點為0號下標
   public void addIndex(int index,int data){//需要創建一個查找index位置前一節點的函式
       if (index > 0 && index < size()) {//判斷插入位置是否合法
           ListNode node = new ListNode(data);//創建新節點并初始化節點的data
           node.next = findIndex(index).next;//通過上邊寫的查找方法將index位置前一節點的下一節點參考賦給新插入節點的next
           findIndex(index).next = node;//將新節點的參考存到查找到的節點的next達到鏈接效果
       }

       else if (index==0) {//如果插入位置是0，則直接使用頭插法插入
           addFirst(data);
           return;
       }

       else if(index==size()) {//如果插入位置是鏈表長度值，則直接使用尾插法插入
           addLast(data);
           return;
       }
       else
           System.out.println("位置不合法！");
       return;
   }

🍈洗掉第一次出現關鍵字為key的節點

首先判斷頭結點是否為null（鏈表是否為空），然后有兩種情況
①關鍵字在頭結點：將頭結點下一個節點設定為新頭結點
②關鍵字不在頭結點：將有關鍵字的節點的下一節點參考賦給有關鍵位元組點的上一節點的next

//洗掉第一次出現關鍵字為key的節點
   public void remove(int key){
       if (this.head == null){//判斷鏈表是否為空
           System.out.println("鏈表為空，不能洗掉");
           return;
       }
       ListNode cur = this.head;
       while(cur.next != null){//遍歷鏈表
           if(cur.value == key) {//①關鍵字在頭結點：將頭結點下一個節點設定為新頭結點
               head = cur.next;
               return;
           }
           else if(cur.next.value == key) {//②關鍵字不在頭結點：將有關鍵字的節點的下一節點參考賦給有關鍵位元組點的上一節點的next
               cur.next = cur.next.next;
               return;
           }
           cur = cur.next;
       }
       System.out.println("沒有你要洗掉的節點");
   }

🍈洗掉所有值為key的節點

和上邊洗掉第一次出現的key類似，只不過return換成了continue，再有就是需要設定一個區域變數size，洗掉程序進行完之后若洗掉前設定的size值沒發生改變，則說明沒有洗掉節點

//洗掉所有值為key的節點
   public void removeAllKey(int key){
       int size = size();
       if (this.head == null){
           System.out.println("鏈表為空，不能洗掉");
           return;
       }
       ListNode cur = this.head;
       while(cur.next != null){
           if(cur.value == key) {
               head = cur.next;
               continue;//洗掉之后不要return，繼續遍歷
           }
           else if(cur.next.value == key) {
               cur.next = cur.next.next;
               continue;//洗掉之后不要return，繼續遍歷
           }
           cur = cur.next;
       }
       if(size()==size) {//如果進行洗掉前設定的size等于進行洗掉后size()方法回傳的值，說明沒有進行洗掉操作
           System.out.println("沒有你要洗掉的節點");
       }
   }

🍈清空鏈表

暴力清空，直接將頭結點置空，這樣整個鏈表就無法找到了

//清空鏈表
   public void clear(){
       this.head = null;
   }

順序表和鏈表的區別與聯系

順序表

順序表：一白遮百丑
白：空間連續、支持隨機訪問
丑：1.中間或前面部分的插入洗掉時間復雜度O(N) 2.增容的代價比較大，

鏈表

鏈表：一(胖黑)毀所有
胖黑：以節點為單位存盤，不支持隨機訪問
所有：1.任意位置插入洗掉時間復雜度為O(1) 2.沒有增容問題，插入一個開辟一個空間，

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙