Java資料結構之單鏈表（配圖詳解，簡單易懂）

（本筆記主要介紹單向不帶頭節點非回圈鏈表）

總結不易，希望uu們不要吝嗇你們的👍喲(＾Ｕ＾)ノ~ＹＯ！！

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考鏈接次序實作的，看著這段文字抽象不，生硬不，那看看下邊這幅圖吧！

🤭(●’?’●)看到發哥脖子上這條大金鏈子了嗎？其實資料結構中的鏈表就和發哥脖子上的金鏈子結構相似！！

實際中鏈表的結構非常多樣，以下情況組合起來就有多種鏈表結構：

單向、雙向

帶頭、不帶頭

回圈、非回圈

下面是我圍繞單向不帶頭非回圈鏈表的一些分享心得！！！

其實發哥脖子上的鏈子，是由一節一節組成的，我們的單鏈表也是這樣，每一個小節即為一個節點，

在一個節點內，不僅存放了資料，還存放了下一個資料的地址，這樣一來，一個一個的節點就會串起來比如要把一組資料給存入其中，那么他的結構將會是這個樣子.

接下來我們就來通過代碼實作這樣一個結構😊:

首先先把鏈子上的一個個小環給造好，然后再串起來

class Node {		//通過創建Node類，來實作一個節點的存在
    public int data; //節點中存在數值data
    public Node next;//節點中存在下一個節點的參考（地址），此處可能有疑問是next的型別，下面著重分享一下
    /*就像我們在學習c語言指標部分內容時我們在定義指標變數的型別（所以說c生萬物，其實都一樣😁）
    int a=10；
    int*p=&a；
    p存盤的是a的地址，而p的型別是由a決定的，因為a是int型，所以指標變數p也是int型
    ，next記憶體儲的是下一個節點的參考（地址），節點為Node型，所以next也應該是Node型
    */
    public Node (int data){//構造方法，在實體化物件時給物件進行初始化
        this.data=data;//this.next會被默認為null
    }

接下來就是我們金鏈子的發光時刻了！😎

public class MyLinkedList {
    public Node head;//head為對第一個節點的參考
    public void addFirst(int data); //1.頭插法 
    public void addLast(int data); //2.尾插法 
    public void display(); //3.列印單鏈表
    public int size(); //4.得到單鏈表的長度 
    public boolean addIndex(int index,int data); //5.任意位置插入,第一個資料節點為0號下標
    public boolean contains(int key); //6.查找是否包含關鍵字key是否在單鏈表當中
    public void remove(int key); //7.洗掉第一次出現關鍵字為key的節點 
    public void removeAllKey(int key);  //8.洗掉所有值為key的節點 
    public void clear();//9.清空鏈表
    
}

下邊是我們一個個介面的實作.

1.頭插法：

    public void addFirst(int data) {
        Node node=new Node(data);//我們先把要插的資料造成鏈表再進行插入
        if(this.head==null) {//一個資料也沒有時，其實就是直接存入一個資料
            this.head=node;//然后將head指向我們剛剛創建的節點
            return;//完成后記得直接回傳
        }
        node.next=this.head;//注意兩者不能顛倒順序（自己可以嘗試一下如果顛倒鏈表將接不上），節點都是先連接才能保證鏈表的連接
        this.head=node;
    }

2.尾插法：（難點在于如何找到尾巴）

    public void addLast(int data) {
        Node node=new Node(data);
        if(this.head==null) {//如果鏈表為空，直接插入
            this.head=node;
            return;
        }
        Node cur=this.head;//創建cur用來表示目前節點
        while(cur.next!=null)//設定回圈讓cur往后走，當cur到最后一個節點時停止回圈
        {
            cur=cur.next;//cur后移
        }
        cur.next=node;//最后一個節點接上尾巴
    }

3.列印鏈表：

    public void disPlay() {
        Node cur=this.head;
        while (cur!=null) {//設定回圈遍歷鏈表 完成列印
            System.out.println(cur.data+" ");
            cur=cur.next;
        }
    }

4.求鏈表長度：

    public int size() {
        int count=0;
        Node cur=this.head;
        while (cur!=null) {//遍歷鏈表，求出長度，回傳長度
            count++;
            cur=cur.next;
        }
        return count;
    }

5.指定位置插入：（第一個節點的角標為0，單向鏈表不可逆，所以需要找到指定位置的前一個節點所在位置）

private Node searchIndex(int index) {//封裝一個方法用來找指定位置
        if(index<0||index>this.size())//判斷位置合法性
        {
            throw new RuntimeException("index位置不合法");
        }
        Node cur=this.head;
        int count=0;
        while (count!=index-1)//找到指定位置的前一個位置，回傳這個節點
        {
            count++;
            cur=cur.next;
        }
        return cur;
    }
public void addIndex(int index,int data) {
        if(index==0) {//空鏈表直接插
            this.addFirst(data);
            return;
        }
        if(index==this.size()) {//this.size()回傳鏈表長度，位置為最后，直接呼叫尾插法
            this.addLast(data);
            return;
        }
        Node cur=searchIndex(index);//回傳目標位置的前一個位置的節點
        Node node=new Node(data);//為該資料創立節點
        node.next=cur.next;//以下兩步完成連接，一般都是先接上后邊，如果這兩步順序調換，則無法完成連接
        cur.next=node;
    }

6.查詢關鍵字：

    public boolean contains(int key) {
        if(this.head==null)//空鏈表直接回傳false
            return false;
        Node cur=this.head;//cur完成遍歷，查詢鏈表中是否存在關鍵字key
        while (cur!=null) {
            if(cur.data==key)
                return true;
            cur=cur.next;
        }
        return false;//完成遍歷后沒有找到，回傳false
    }

7.洗掉第一次關鍵字：（因為單向鏈表的不可逆性，所以還是回傳洗掉關鍵字的前一個位置）

    private Node searchDeleteAhead(int key) {
        Node cur=this.head;
        while (cur.next!=null) {//遍歷鏈表找尋關鍵字
            if(cur.next.data==key) {//找到則回傳關鍵字的前一個節點的參考
                return cur;
            }else {
                cur=cur.next;//否則繼續往后走
            }
        }
        return null;//沒找到回傳空
    }
	public void removeKey(int key) {
        if(this.head==null) {//空鏈表直接回傳
            return;
        }
        if(this.head.data==key) {//第一個節點單獨考慮，因為需要回傳關鍵字的前一個節點，若頭結點為關鍵字則沒有前一個節點，直接將頭節點洗掉即可
            this.head=this.head.next;
            return;
        }
        Node ahead=searchDeleteAhead(key);
        if(ahead==null) {
            System.out.println("無該節點!");
        }else {
            ahead.next=ahead.next.next;//前節點的next=被刪節點的next完成洗掉
        }
    }

8.洗掉所有關鍵字：（只通過一次遍歷完成所有關鍵字的洗掉）

public void removeAllKeys(int key) {
    //因為洗掉一個節點需要前一個節點的連接，所以需要建立兩個節點完成整個工程
        Node ahead=this.head;//前一個節點
        Node cur=ahead.next;//后一個節點（在cur中判斷data是否與key相等），兩個節點從頭開始往后遍歷
        while (cur!=null) {//當cur為空時完成遍歷
            if(cur.data==key) {//在cur中判斷data是否與key相等，如果相等則洗掉
                ahead.next=cur.next;//先完成連接
                cur=cur.next;//連接完成后cur后移繼續判斷該cur.data是否為關鍵字，ahead不用動（因為已經洗掉該節點以后，只需cur后移，ahead仍為cur的前一個節點）
            }else {//如果不相等，則兩者均后移
                ahead=cur;
                cur=cur.next;
            }
        }
        if(this.head.data==key) {//最后考慮頭節點，如果相等再完成洗掉
            this.head=this.head.next;
        }
    }

解釋一下為什么最后考慮頭節點

if(this.head.data==key) {
   this.head=this.head.next;
}
while (del!=null) {
   if(del.data==key) {
      ahead.next=del.next;
      del=del.next;
   }else {
        ahead=del;
        del=del.next;
   }
}

如圖所示，再先洗掉頭節點以后,直接跳過了ahead.data的考慮，所以把頭節點放在最后考慮，如果相等洗掉即可，

9.清空鏈表：

 public void clear() {
     this.head=null;
 }

（可別小看這一行代碼，其實它完成了整個鏈表的清空）

JVM在回收記憶體時，當該物件沒有人在參考它的時候，這個物件才會被回收，當把this.head置為空時，也就相當于沒有物件參考第一個頭節點了（其實就像多米諾骨牌后邊就全掉了），第一個被回收，后邊也就都被回收了

總結不易，希望uu們不要吝嗇你們的👍喲(＾Ｕ＾)ノ~ＹＯ！！