回顧 和 鏈表

接下來我們來通過代碼 來認識鏈表

1 準備作業

?

2 根據 前面 所說的，根據節點的特性寫一個類

?

3. new 節點

執行到這里，我們就有了這樣一個節點，而鏈表就是由這一個個節點，串成的，

&ensp；

我們已經知道怎么實體化一個節點，但是我們又怎么做，才能知道下一個節點的地址呢？

      要想知道它怎么做，我們必須實作 它 的 一個 頭插 和 尾插， 等等一系列操作，但是我們目前先不管它
      我們現在最重要的是 了解 鏈表的結構

?

我先來把前面的東西講清楚，

鏈表的頭參考 head

?

理解鏈表中： 帶頭、不帶頭、單向、雙向、回圈、不回圈的意思，

帶頭 和 不帶頭

?

回圈 和 不回圈

?

單向 和 雙向

?

至此 我們將鏈表的結構 全部分析完了，

?

接下來，我會以代碼的形式 來帶你們認識 鏈表，

以窮舉的方式 創建一個鏈表 （這方法很low，不建議去這樣寫，現在只是為了幫助我們去理解鏈表）

現在 我要實作 單向 不帶頭 非回圈的鏈表

?

回到代碼

&ensp；

創建一個函式，來實作鏈表的結構

先創建五個節點

?

將五個節點連接起來，

?

現在鏈表結構，已經構造好了，它的頭節點就是節點1，將 節點一 的地址 賦給 頭參考 head

?

遍歷鏈表資料

 首先，我要區分清楚，鏈表 不是順序表，不是一塊連續的空間， 鏈表的每個元素 是由地址來連接起來的，
   也就是說 我們不能使用普通思維模式 去思考 遍歷鏈表的資料域的值

 既然 鏈表是靠地址聯系起來的，也就是說 靠 next域中 存盤的地址來聯系個節點的資料
 這就是我們突破點，
  利用 head 遍歷每個每個節點的資料  寫法 head =  head/next，你可以參考上面的圖，來細品，
  這樣我們就跳轉到下一個節點，算了我還是畫個圖，請看下圖（注意我埋了一個坑，你們等會就知道，只有被打過，才會知道疼）

?

揭秘坑

?

解決方法 （創建一個head的替身 【cur == current — 目前的】，來代替head去遍歷鏈表資料）

代碼如下：

?

呼叫者程式

效果圖

另外注意一點

效果圖

?

總結：

 遍歷鏈表的時候， 尤其是我們現在所講的 不帶頭的鏈表，一定注意，不要讓 頭參考丟失，創建一個替身變數，讓它去做，
 保證頭參考指向的永遠都是 頭節點，

?

鏈表要實作的功能

?

查找關鍵字key是否在鏈表當中

    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

附圖

效果圖（最好兩邊加中間，還有找不到的情況都要測驗一下）

&ensp；

得到單鏈表的長度

  public int size(){
        int count=0;
        ListNode cur = this.head;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

附圖

?

頭插法

public void addFirst(int data){
           ListNode node = new ListNode(data);
           node.next = this.head;
           this.head = node;
        }

附圖

效果圖

?

使用頭插法，創建鏈表

?

尾插法

public void addLast(int data){
             ListNode node = new ListNode(data);
             if(this.head == null){
               this.head = node;
             }else{
                 ListNode cur = this.head;
                 while(cur.next!=null){
                     cur = cur.next;
                 }
                 cur.next = node;
             }

        }

附圖

*****

效果圖

任意位置插入一個資料節點

public void addIndex(int index,int data){
     if(index<0 || index>size()){
         System.out.println("插入資料節點的位置不合法");
         return;
     }
     if(index==0){
         addFirst(data);// 呼叫頭插
         return;
    }
     if(index== size()){
         addLast(data);
         return;
     }
      ListNode cur = findIndex(index);// 接收 index-1位置節點的地址
      ListNode node = new ListNode(data);// 根據 data的值，新建一個節點
      
      // 插入節點程式
      node.next = cur.next;
      cur.next = node;

}
// 找到index-1位置的節點位置
// 跟圖解解釋的一樣，如果你要插入一個位置，你就需要找它的前一個節點的位置
// 而我們是鏈表沒有下標，所以回傳是 前一個節點的地址
public ListNode findIndex(int index){
      ListNode cur = this.head;
    while(index-1 != 0){
        cur = cur.next;
        index--;
    }
    return cur;
}

附圖

效果圖

?

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

public void remove(int key){
if(this.head == null){// head為空
    System.out.println("鏈表為空，無數字可洗掉！");
    return;
}
if(this.head.val == key){// 判斷頭節點是為洗掉數字
    this.head = this.head.next;
    return;
}
ListNode cur = searchPrev(key);// 找到洗掉節點的前一個節點
if(cur == null){
    System.out.println("沒有你要洗掉元素");
    return;
}
ListNode del = cur.next;// 要洗掉的節點地址
cur.next =  del.next;// 洗掉節點

}
// 尋找洗掉節點的前一個節點（key的前驅）
public  ListNode searchPrev(int key){
  ListNode cur = this.head;
  while(cur.next != null){
      if(cur.next.val == key)
      {
          return cur;
      }
      cur = cur.next;
  }
  return null;// 表示沒找到
}

附圖

效果圖

?

洗掉所有值為key的節點

public ListNode removeAllKey(int key){
      if(this.head == null){
          return null; // 防止后面的cur出現空指標錯誤
      }
      ListNode prev = this.head;
      ListNode cur = this.head.next;
      while(cur!=null){
          if(cur.val == key){
              prev.next = cur.next;
              cur=cur.next;
          }else{
               prev = cur;
               cur=cur.next;
          }
      }
      // 最后處理頭
      if(this.head.val==key){
          this.head = this.head.next;
      }
      return head;
}

附圖

效果圖

清楚鏈表的所有的節點

public void clear(){
// this.head = null; 粗暴方法

// 溫柔的（最穩的）
    while(this.head!=null){
        ListNode headNext = head.next;
        this.head.next = null;
        this.head = headNext;
    }
}

附圖

效果圖

還有一種更直觀的方法，請看連續圖

附上鏈表程式

?

呼叫者程式

本文至此，就將鏈表的所有功能都實作了，有疑問的可以在下方評論，大家一起共同進步