幾分鐘帶你解決資料結構問題-------單鏈表（超詳細）-有解無憂

🌈文章前提

鏈表在資料結構中占據很重要的地位，本篇博客將從單鏈表的創建，以及操作單鏈表實作幾種功能展開，下面正式開始但鏈表的講解 👇👇👇

📌文章目錄：

1??.鏈表的概念及其結構

2??.結點的創建

3??.單鏈表的創建

4??.單鏈表功能的實作

查詢鏈表的資料
計算鏈表的長度
頭插法實參資料的插入
尾插法實參資料的插入
任意位置插入新元素
洗掉第一次出現關鍵字為key的節點
洗掉所有值為key的節點
清空單鏈表

5??.單鏈表實作的全部代碼

1.鏈表的概念及其結構

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

鏈表的幾種結構：👇

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

?? 一共有 8 中資料結構

本博客主要討論兩種鏈表：👇

單向、不帶頭、非回圈
雙向、不帶頭、非回圈（后期博客涉及）

?? 考試、做專案、筆試題基本都是以上兩種鏈表 ??

如果需要存盤一組資料：👇

12 23 34 45 56

? 用順序表存盤即是用一個陣列去進行存盤，再進行增刪查改等操作

? 那如果是用鏈表進行存盤呢 👇

👉 鏈表是由一個一個叫做結點的東西組成的

如圖是單向鏈表一個結點的圖解：👇
在這里插入圖片描述
我們用實際的資料存盤來畫圖解釋一下單向鏈表 👇

?? 注：圖中每個結點的地址是隨意撰寫的

在這里插入圖片描述
? 如上圖當結點中存盤完資料后，每個結點都是獨立的，怎樣把它們串起來生成一個鏈表呢

👉 用每一個結點的 next 結點域保存下一個結點的地址，當前結點就可以指向下一個結點，這樣一步一步就可以把結點串聯起來生成一個鏈表

在這里插入圖片描述
👉 最后一個結點由于不知道下一個結點的地址是什么，所以在最后一個結點域中保存的是 null，上圖就是一個單鏈表結構

🔥 我們發現每一個結點在沒有串聯起來之前都是獨立的，所以可以把每一個結點都定義成一個類

👉 head 結點（頭結點）：存放第一個結點的地址
在這里插入圖片描述
? 那 head.next 存盤的是什么地址呢

👉 即下一個結點的地址，并且由于 head 存放的是結點物件的地址，所以由 head.可以訪問到結點的 val 域和 next 結點域

? 鏈表最后一個結點叫做什么呢

👉 鏈表最后一個結點稱為尾結點，尾結點有一個特點—>它的尾結點 next 域是一個 null ，如果有一個結點的 next 域為 null 即該結點為尾結點

2.結點的創建

👉 抽象化一個類代表的是一個結點型別

class ListNode {
    public int val;//數值域  存放數值
    public ListNode next;//next結點域
}

在這里插入圖片描述
👉 這里的 next 型別為 ListNode 型別，因為結點域存放的是下一個結點的地址，所以 next 型別當然是結點型別（ListNode）

👉構造方法

public ListNode(int val){
        this.val = val;
    }

在其他方法中實體化一個結點物件，可以生成一個結點：👇

public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
    }

👉 這樣就生成了一個數值域為 1 的一個結點，由于沒給它的 next 域進行賦值，所以其 next 域為 null

在這里插入圖片描述
👉 由于不知道當前結點的下一個結點是哪個，所以在初始化時，next 域不需要進行賦值

當新開辟一個物件時記憶體示意圖：👇
在這里插入圖片描述
?? 以上就是一個結點的創建

? 那么頭結點如何創建呢 👇

public class MyLinkList {
    public ListNode head;//鏈表的頭參考
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
    }
}

👉 我們可以看到頭結點是在 MyLinkList 鏈表類中定義的，因為 head 是鏈表的頭，并不是結點的頭

? 有這樣一個問題我們上面創建的是一個單向不帶頭非回圈的鏈表，那么帶頭的又是怎樣的呢 👇

在這里插入圖片描述

👉 區別：

不帶頭的鏈表頭結點位置不確定，位置一直在改變
帶頭的鏈表頭結點位置一直是固定的，非常簡單，其頭結點又被稱為傀儡結點，其數值沒有任何參考意義
二者沒有好壞之分，只是簡單與復雜的區別

? 科普一下------> 回圈的鏈表又是如何定義的呢

在這里插入圖片描述

3.單鏈表的創建

?? 我們先不使用頭插和尾插這樣的方式實作單鏈表的創建

👉 我們先用窮舉法實作單鏈表的創建

public class MyLinkList {
    public ListNode head;//鏈表的頭參考
    public void createList(){
        ListNode listNode = new ListNode(12);
        ListNode listNode1 = new ListNode(23);
        ListNode listNode2 = new ListNode(34);
        ListNode listNode3 = new ListNode(45);
        ListNode listNode4 = new ListNode(56);
    }
}

?? 在鏈表類中先定義方法，實體化五個結點物件，這五個結點目前的情況是：👇

?? 由于沒有給 next 結點域賦值，由于其是參考型別，默認為：null
在這里插入圖片描述
緊接著上面的代碼把結點都連接起來，上一個結點的 next 域存盤下一個結點的地址，頭結點存盤第一個結點的地址👇

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        this.head = listNode;

現在的各個結點就鏈接起來了，生成了一個單鏈表👇
在這里插入圖片描述
? 那么鏈表已經有了怎樣去遍歷鏈表，拿到這些資料呢，如果是陣列可以以0,1,2,3,4……下標對其進行遍歷，鏈表又是什么方法遍歷

👉 利用頭結點的移動進行單鏈表的遍歷，直到頭結點為空

head = head.next

👉 把頭結點的下一個結點地址賦值給頭結點，再用新的頭結點去訪問其 val 數值
在這里插入圖片描述
? 思考上述回圈遍歷的代碼是不是有問題??

?? 代碼最后回圈的終止條件是 head!=null ,當回圈終止時，這時候的 head 指向的是空物件，使得我們不知道 head 導致指向哪里了，這樣就導致 head 用過一次就不能再次重復使用了

👉 代碼改進：head 不能動，讓 head 的替身動即可

ListNode cur = this.head;

?? 把 head 保存到的地址賦值給 cur ，即 cur 也可以指向頭結點

遍歷單鏈表拿到結點數值：👇

public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur  = cur.next;
        }
    }

在測驗類中呼叫并列印：👇

public class TestDemo {
    public static void main(String[] args) {
        MyLinkList myLinkList = new MyLinkList();
        myLinkList.createList();
        myLinkList.display();
    }
}

12 23 34 45 56

?? 這里成功拿到了鏈表的所有數值

4.單鏈表功能的實作

功能一：查找是否包括關鍵字 key（查詢鏈表中的資料） 👇

在這里插入圖片描述
👉 移動 cur 對每個結點的 val 值進行訪問，對比和 key（需要進行查找的數值）是否相同，相同回傳 true 當回圈結束仍沒有回傳，就證明沒有此數值即回傳false ，回圈結束的標志是 cur 訪問到最后一個結點

代碼實作：📌

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

測驗類中呼叫此方法，傳入需要進行查詢的數值作為方法的實參，并列印 👇

System.out.println(myLinkList.contains(13));
System.out.println(myLinkList.contains(56));

功能二、求得單鏈表的長度 👇

👉 利用 cur 去進行遍歷，定義一個計數器，回圈去計算，回圈終止條件是，cur指向 null，即 cur 指向尾結點時結束回圈

代碼實作：📌

public int size() {
        int count = 0;//定義一個計數器
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

在測驗類中呼叫該方法并列印：👇

System.out.println(myLinkList.size());

功能三、頭插法 👇

比如：需要在單鏈表的頭結點處插入如圖資料 👇
在這里插入圖片描述
我們可以看到插入的資料是 1 ，然而插入鏈表的需要是結點，所以需要拿 1 來構造一個結點 👇

ListNode node = new ListNode(1);

在這里插入圖片描述
頭插法需要對兩個地方進行修改：

一、插入元素的 next 結點存盤第一個結點的地址
二、頭結點存盤當前結點的地址

在這里插入圖片描述
?? 在實作插入代碼時候，容易出現下圖賦值順序的錯誤 👇

?? 第一種不可以，如果先把 head 指向插入的新元素的地址，這時候 head 存盤的地址是 0x444，再 head 賦值給 node.next ，node.next 存盤的地址是 0x444，這就相當于把自己指向自己了，代碼顯然是錯誤的

?? 一定記住系結位置的時候一定先系結后面，以防把后面的東西弄丟

? 如果插入的時候鏈表沒有元素，鏈表為空時，怎樣插入呢

在這里插入圖片描述
?? 這里空鏈表用上述的代碼實作頭插也是完全可以的，效果一樣

代碼實作：📌

public void addFirst(int data){
        ListNode node = new ListNode(data);//創建一個新的結點
        node.next = this.head;
        this.head = node;
    }

在類方法中呼叫：👇

myLinkList.addFirst(12);
myLinkList.addFirst(23);
myLinkList.addFirst(34);
myLinkList.addFirst(45);
myLinkList.addFirst(56);

56 45 34 23 12

?? 這里數值是倒序列印出來的，因為先存盤存盤第一個資料（12），再把后面的資料依次插在第一個插入元素的前面，所以得到的結果是與輸入順序相反的

功能四、尾插法 👇

? 尾插法表示已經有一個鏈表了，把一個元素放在最后面，如何實作

👉 把鏈表最后一個結點（尾結點）的結點域保存尾插元素的地址即可，首要任務是尋找鏈表的最后一個結點
在這里插入圖片描述
👉 即 cur 所指向的結點是尾結點

? 上圖所示的代碼，是單鏈表中存在其他結點，那么當鏈表為空時，怎么實作尾插法呢
在這里插入圖片描述
?? 由于在插入途中會對 cur.next 進行訪問，如果是空串列這樣就會造成空指標例外，所以尾插法第一次插入必須判斷，如果為空，用上圖的方法把 node 賦值給 head，然后再進行正常的尾插法操作

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

在測驗類中呼叫并列印插入結點后的鏈表

myLinkList.addLast(1);
myLinkList.addLast(2);
myLinkList.display();

56 45 34 23 12 1 2

功能五、在任意位置插入新元素 👇

👉 先人為的給鏈表加上一個標號，幾號位置
在這里插入圖片描述
假設我需要在 2 號位置進行插入 👇

在這里插入圖片描述

需要往 2 號位置插入，就需要找到插入位置的前一個元素，然后進行兩步操作

一、node.next = cur.next

二、cur.next = node

?? 通過上述兩步把插入的結點插入到鏈表中

代碼實作：📌

public ListNode findList(int index){
        ListNode cur = this.head;
        while(index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public void addIndex(int index, int data){
        ListNode node = new ListNode(data);
        if (index < 0 || index > size()){
            System.out.println("位置不合法");
            return;
        }
        if (index == 0){
            addFirst(data);
            return;
        }
        if (index == size()){
            addLast(data);
            return;
        }
        ListNode pos = findList(index);
        node.next = pos.next;
        pos.next = node;
    }

👉 先進行判斷插入結點的位置合不合法，下標是從 0 開始的沒有負數，如果大于元素個數，沒有前一個結點沒辦法插入元素，

📌 如果在下標為 0 的位置進行結點插入，即是頭插法，呼叫頭插法的實作方法即可

📌 如果在尾結點進行插入，即是尾插法，呼叫尾插法的方法即可

📌 在中間進行插入時，呼叫 findList 方法找到插入位置的前一個結點位置，回傳值是一個結點型別，接

收其地址后，進行元素的插入即可完成指定位置的插入

在測驗類中呼叫此方法，并進行列印即可： 👇

 myLinkList.addIndex(3,1);

功能六、洗掉第一次出現關鍵字為key的節點 👇

? 如下圖，想要洗掉鏈表中的數值為 23 的結點，怎樣進行操作
在這里插入圖片描述
實作的大致思想：👇

👉 回圈的條件是 cur 的結點域不為空，當回圈終止時也沒有找到 key 結點元素，則證明在鏈表中不存在該元素，無法進行洗掉

操作

?? 由于判斷條件是 cur.next.val == key，頭結點的元素會被忽略過去，所以頭結點需要單獨判斷

洗掉步驟：👇

一、判斷頭結點（head向后移即可）

二、找洗掉結點的 del 和 cur 位置，找到進行洗掉操作，找不到即列印該鏈表不存在此資料

代碼實作：👇

public void remove(int key){
        if(this.head == null){
            System.out.println("單鏈表為空，不能進行洗掉操作");
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPos(key);
        if (cur == null){
            System.out.println("洗掉的元素在鏈表中不存在，無法完成洗掉操作");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

在測驗類中呼叫此方法并進行列印：👇

myLinkList.remove(56);
myLinkList.remove(23);

功能七、洗掉所有值為key的節點 👇

?? 要求只遍歷一遍鏈表洗掉所有 key 數值的結點
在這里插入圖片描述
洗掉的幾種情況：

一、當需要洗掉的元素結點在鏈表的中間

在這里插入圖片描述
cur 代表需要洗掉的結點，如果 cur 結點的數值剛好等于需要洗掉的數值，即

prev.next = cur.next;

在這里插入圖片描述

?? 這時候第一個結點和第三個結點就連接起來了，然后 cur 繼續向后走，尋找其他數值為 key 的結點

cur = cur.next;

👉 再進行判斷目前 cur 的數值是不是 key，如上圖的第三個結點數值是 34 ，不是洗掉的數值，就把目前 cur 的結點地址賦值給 prev

prev = cur;
cur = cur.next;

在這里插入圖片描述
?? 回圈的終止條件就是當 cur 遍歷整個鏈表后，當 cur = null 的時候結束回圈

二、當洗掉的元素結點在頭和中間時，上方代碼依舊適用，只不過頭結點沒有進行判斷，少洗掉一個結點，等全部洗掉完畢，再來判斷一下頭結點，單獨洗掉即可

代碼實作： 👇

public ListNode removeAllKey(int key){
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        //防止空指標例外
        if(this.head == null){
            return null;
        }
        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 this.head;
    }

在測驗類呼叫并列印即可：

myLinkList.removeAllKey(23);

功能八、情況鏈表 👇

👉 把鏈表的每一個結點都清空，防止記憶體泄漏

粗暴演算法：把 head 置空，之后的每一個結點都沒人參考了 👇

head = null;

溫柔演算法：一個一個結點釋放 👇

public void clear(){
        while(this.head != null){
            ListNode curNext = head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }

👆 curNext 向后走，head 不斷的置空，再把 curNext 賦給 head ，回圈置空即可

五、全部代碼👇

單鏈表的創建及功能實作：👇

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2021-11-05
 * Time: 9:17
 */
class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}

public class MyLinkList {
    public ListNode head;
    public void createList(){
        ListNode listNode = new ListNode(12);
        ListNode listNode1 = new ListNode(23);
        ListNode listNode2 = new ListNode(34);
        ListNode listNode3 = new ListNode(45);
        ListNode listNode4 = new ListNode(56);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        this.head = listNode;
    }
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur  = cur.next;
        }
    }
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    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);
        ListNode cur = this.head;
        if (this.head == null){
            this.head = node;
        }
        else{
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    public ListNode findList(int index){
        ListNode cur = this.head;
        while(index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public void addIndex(int index, int data){
        ListNode node = new ListNode(data);
        if (index < 0 || index > size()){
            System.out.println("位置不合法");
            return;
        }
        if (index == 0){
            addFirst(data);
            return;
        }
        if (index == size()){
            addLast(data);
            return;
        }
        ListNode pos = findList(index);
        node.next = pos.next;
        pos.next = node;
    }
    public ListNode findPos(int key){
        ListNode cur = this.head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    public void remove(int key){
        if(this.head == null){
            System.out.println("單鏈表為空，不能進行洗掉操作");
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPos(key);
        if (cur == null){
            System.out.println("洗掉的元素在鏈表中不存在，無法完成洗掉操作");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    public ListNode removeAllKey(int key){
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        //防止空指標例外
        if(this.head == null){
            return null;
        }
        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 this.head;
    }
    public void clear(){
        while(this.head != null){
            ListNode curNext = head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }
}

測驗類中呼叫實作：👇

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2021-11-05
 * Time: 9:17
 */
public class TestDemo {
    public static void main(String[] args) {
        MyLinkList myLinkList = new MyLinkList();
        //myLinkList.createList();
        myLinkList.addFirst(12);
        myLinkList.addFirst(23);
        myLinkList.addFirst(34);
        myLinkList.addFirst(23);
        myLinkList.addFirst(56);
        myLinkList.display();
        System.out.println();
        System.out.println(myLinkList.contains(12));
        System.out.println(myLinkList.contains(56));
        System.out.println(myLinkList.size());
        //myLinkList.addLast(1);
        //myLinkList.addLast(2);
        //myLinkList.addIndex(3,1);
        /*myLinkList.remove(56);
        myLinkList.remove(23);
        myLinkList.remove(1);*/
        myLinkList.removeAllKey(23);
        myLinkList.display();
        myLinkList.clear();
        System.out.println("ssssss");
    }
}

以上就是單鏈表的全部內容，希望對大家有所幫助，如果有問題歡迎交流，謝謝大家的支持！！！！！

💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞💞

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350941.html

標籤：其他

上一篇：資料結構：線性表順序表以及單鏈表詳解

下一篇：Linux權限