【Java資料結構】通過Java了解和實作——順序表和單連結清單🍉順序表

【Java資料結構】通過Java了解和實作——順序表和單連結清單

🍉線性表

🍉順序表

🌵順序表概念及結構

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

🍈列印順序表

🍈在pos位置新增元素

🍈擷取順序表長度

🍈判斷是否包含某個元素

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

🍈擷取pos位置的元素

🍈給pos位置的元素設為value

🍈删除第一次出現的資料

🍈清空順序表

🍌順序表的缺陷

🍉連結清單

🌵連結清單概念及結構

🍌無頭單向非循環連結清單接口實作（注釋非常詳細，我👴👴都能看懂）

🍈列印連結清單

🍈頭插法插入

🍈尾插法插入

🍈查找是否包含關鍵字key在單連結清單當中

🍈得到單連結清單的長度

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

🍈删除第一次出現關鍵字為key的節點

🍈删除所有值為key的節點

🍈清空連結清單

順序表和連結清單的差別與聯系

順序表

連結清單

線性表（linear list）是n個具有相同特性的資料元素的有限序列。 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、連結清單、棧、隊列、字元串…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在實體結構上并不一定是連續的，線性表在實體上存儲時，通常以數組和鍊式結構的形式存儲。

順序表是用一段實體位址連續的存儲單元依次存儲資料元素的線性結構，一般情況下采用數組存儲。在數組上完成資料的增删查改。

順序表一般可以分為：

靜态順序表：使用定長數組存儲。

動态順序表：使用動态開辟的數組存儲。

靜态順序表适用于确定知道需要存多少資料的場景.

靜态順序表的定長數組導緻N定大了，空間開多了浪費，開少了不夠用

相比之下動态順序表更靈活, 根據需要動态的配置設定空間大小.

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

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

• ①判斷pos是否合法
• ②判斷順序表滿沒滿（這裡還>需要額外寫一個判斷方法isFull()），滿了需要Arrays.copyOf()擴容
• ③pos之後的元素依次向後移動個位置
• ④将目标元素data放入這個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嗷
       }
   }
      

1. 順序表中間/頭部的插入删除，時間複雜度為O(N)

2. 增容需要申請新空間，拷貝資料，釋放舊空間。會有不小的消耗。

3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如目前容量為100，滿了以後增容到200，我們再繼續插入了5個資料，後面沒有資料插入了，那麼就浪費了95個資料空間。

連結清單會不會存在以上的問題呢？請往下看👇👇

連結清單是一種實體存儲結構上非連續存儲結構，資料元素的邏輯順序是通過連結清單中的引用連結次序實作的 。

連結清單結構非常多樣，以下情況組合起來有8種連結清單結構：

單向、雙向

帶頭、不帶頭

循環、非循環

我們重點學習以下兩種連結清單

先寫兩個類，一個是連結清單類（包含有一個可變的頭結點和實作各種功能的接口，因為是無頭連結清單，是以這個頭結點是可變的），一個是節點類（成員屬性有value和next）

接下來的接口都是寫在連結清單類裡的，因為連結清單是一個對象，我們要實作的就是一個連結清單對象所有的功能

//根據傳入的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;
   }
      

首先判斷頭結點是否為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類似，隻不過return換成了continue，再有就是需要設定一個局部變量size，删除過程進行完之後若删除前設定的size值沒發生改變，則說明沒有删除節點

順序表：一白遮百醜

白：空間連續、支援随機通路

醜：1.中間或前面部分的插入删除時間複雜度O(N) 2.增容的代價比較大。

連結清單：一(胖黑)毀所有

胖黑：以節點為機關存儲，不支援随機通路

所有：1.任意位置插入删除時間複雜度為O(1) 2.沒有增容問題，插入一個開辟一個空間。