🎓??引言
🎓??鏈表的概念及結構
🎓??單鏈表的實作及圖示分析
- 📝🔷單鏈表之創建單鏈表
- 📝🔷單鏈表之計算單鏈表的長度
- 📝🔷單鏈表之列印單鏈表
- 📝🔷單鏈表之單鏈表的增刪查改
- - 📝🔷頭插法插入元素
  - 🐮🐵尾插法插入元素
  - 🐮🐵把一個節點插入到鏈表的任意位置
  - 🐮🐵查找鏈表中是否含有某個元素
  - 🐮🐵洗掉鏈表中第一次出現value值的節點
  - 🐮🐵洗掉鏈表中出現value值得所有節點
  - 🐮🐵清空單鏈表

🎓??引言

??順序表的問題及思考，之前我寫了一篇順序表的博客，發現陣列和順序表基本一樣，很簡單地就實作了，但存在一些問題比如：

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

那么如何解決以上問題呢？答案是我們可以通過鏈表來解決上面存在的問題，鏈表適合插入和洗掉元素，可以做到隨用隨取不浪費空間，順序表則適合給定要查找元素的下標進行查找，

各有各的有點，下面給出了鏈表的結構來簡單地看一下，

🎓??鏈表的概念及結構

鏈表是一種物理存盤結構上非連續存盤結構，資料元素的邏輯順序是通過鏈表中的參考變數來實作的，如下圖的鏈表：
在這里插入圖片描述
下面是鏈表節點的基本結構：

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
單/雙向—>帶/不帶頭——>回圈/非回圈（2x2x2）

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

📝📐本篇博客重點實作單鏈表的基本功能，雙鏈表后期博文講解，而單向鏈表中，比較難，重要，面試經常遇到的就是單向不帶頭非回圈的鏈表了，因此我們重點講解它，單向的帶頭和回圈的很簡單，我們把不帶頭的非回圈的明白了，其他的學習起來也很簡單了，
注意事項：
對于這里所說的鏈表帶不帶頭，我們需要好好理解下，

不帶頭的單向非回圈鏈表，這個鏈表沒有真正的頭結點，但是我們把第一個節點叫做頭結點，這個節點是個虛擬的，只起一個標識作用，標識這個鏈表的頭結點
這個頭結點的位置隨時可能發生這變化，是不固定的，之后通過這個頭結點我們要完成一些鏈表的增刪查改，從頭開始，因此頭很重要
帶頭結點的鏈表，有正真的頭結點，這個頭結點也是用來標識頭結點的位置的，這個節點的位置不會發生改變，但這個頭結點里面的值不被使用，帶頭的就很簡單，比如每次頭插，頭都不變，

下面看代碼的時候你就會真正地感受到了，下面是幾種回圈的結構：

單向不帶頭非回圈鏈表
在這里插入圖片描述
單向帶頭非回圈鏈表

單向不帶頭回圈鏈表

🎓??單鏈表的實作及圖示分析

通過分析上面的鏈表，我們可以抽象出兩個類，一個是鏈表本身是一個類（鏈表這種型別）定義在MyLinkedList.java這個java檔案中，另外鏈表里面的節點也可以看做一個類，定義在Node.java這個檔案中，這兩個鏈表里面有不同的成員屬性，利用面向物件的思想來實作我們所要的單鏈表，
在這里插入圖片描述

📝🔷單鏈表之創建單鏈表

以窮舉的方式創建單鏈表
分別實體化了四個物件，并且呼叫構造方法進行值的初始化，在通過節點里面參考變數的指向使所有節點連接起來，

public void createList() {
        Node node1 = new Node(12);
        Node node2 = new Node(3);
        Node node3 = new Node(5);
        Node node4 = new Node(2);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        this.head = node1;
    }

在這里插入圖片描述

📝🔷單鏈表之計算單鏈表的長度

這個很簡單遍歷鏈表元素就行，創建一個臨時節點，代替頭結點遍歷，頭結點的位置很重要起到標識作用不能隨便改變，沒有了頭就不能找到這個鏈表了，還要注意遍歷的結束條件，

 //得到單鏈表的長度
    public int size() {
        Node cur = this.head;//創建一個臨時節點，代替頭結點遍歷，頭結點的位置很重要起到標識作用不能隨便改變，沒有了頭就不能找到這個鏈表了
        int count = 0;
        while (cur != null) {
            count++;//4
            cur = cur.next;//cur這個節點向后移動一步
        }
        return count;
    }

在這里插入圖片描述

📝🔷單鏈表之列印單鏈表

列印單鏈表也很簡單，遍歷列印就行，只是鏈表元素向后移動是通過參考變數指向物件的移動移動的，

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

在這里插入圖片描述

📝🔷單鏈表之單鏈表的增刪查改

📝🔷頭插法插入元素

頭插法插入元素的時候需要注意：

在插入一個節點的時候，一定要先使插入節點的空指標域指向下一個節點的地址，再更換頭結點
新插入的節點是頭結點
如果插入時，head為空，則證明之前鏈表沒有資料，直接this.head=node即可，之后又按第一個節點不是null的方法插入即可

//頭插法
    public void addFirst(int data) {
        Node node = new Node(data);
        if(this.head == null) {
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;
        }
    }

在這里插入圖片描述

🐮🐵尾插法插入元素

如果一個鏈表為空，也就是頭結點head==null,直接插入一個元素既是頭也是尾，不為空的時候通過while回圈找到尾巴節點，**當 cur.next為null時候是尾巴節點，**再使這個尾巴節點里面存盤node節點的地址，這樣把所有的節點都連接起來了，

//尾插法
    public void addLast(int data) {
        Node node = new Node(data);
        if(this.head == null) {//鏈表為空沒有元素
            this.head = node;
        }else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;//連接下一個節點
        }
    }

在這里插入圖片描述

🐮🐵把一個節點插入到鏈表的任意位置

對于鏈表里面的元素，假設第一個元素的下標為0，第二個元素下標為2，以此類推，插入元素之前要判斷元素位置的合法性，插入位置,0=<index<=size，當插入位置為0的時候，相當于頭插法，當index=size的時候，相當于尾插法，插入元素在中間的時候，插入到插入位置的前面，之后連接前后兩個元素即可，

尋找插入點的前一個節點
在這里插入圖片描述

//尋找前驅節點
 public Node searchPrev(int index) {
        Node cur = this.head;
        int count = 0;
        while(count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;//
    }

中間插入元素
在這里插入圖片描述

    //任意位置插入,第一個資料節點為0號下標
    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;
        }
        Node cur = searchPrev(index);
        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;
    }

🐮🐵查找鏈表中是否含有某個元素

從鏈表的頭到尾遍歷，看是否含有某個值，注意遍歷鏈表的條件是cur==null;

//查找是否包含關鍵字key是否在單鏈表當中 
    public boolean contains(int val) {
        Node cur = this.head;
        while (cur != null) {
            if(cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

🐮🐵洗掉鏈表中第一次出現value值的節點

洗掉鏈表中第一次出現value值的節點，首先這個鏈表要不為空，為null就直接回傳什么都不用做了，不為空，找到要洗掉節點的前面一個節點，**使前驅節點連接要洗掉節點后面的一個節點就把那個值給洗掉了，**另外如果頭結點為洗掉的節點要單獨判斷，更換頭結點就洗掉了，詳細解釋看圖
在這里插入圖片描述

public Node searchPrevNode(int val) {
        Node cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == val) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //洗掉第一次出現關鍵字為key的節點
    public void remove(int val) {
        if(this.head == null) return;
        //單獨判斷頭節點的問題
        if(this.head.val == val) {
            this.head = this.head.next;
            return;
        }
        Node cur = searchPrevNode(val);
        if(cur == null) {
            System.out.println("沒有你要洗掉的節點！");
            return;
        }
        Node del = cur.next;
        cur.next = del.next;
    }

如果是頭結點是要洗掉的節點
在這里插入圖片描述

🐮🐵洗掉鏈表中出現value值得所有節點

👀😄洗掉鏈表中出現的value值的所有節點，和之前洗掉出現value值的方法差不多，定義一個prev標記要洗掉節點的前驅，找到要洗掉的節點跳過它就行了，但要注意出現連續要洗掉的value值和頭節點是要洗掉的節點的情況，
在這里插入圖片描述

//洗掉所有值為key的節點
    public void removeAllKey(int val) {
        if(this.head == null) {
            return;
        }
        Node prev = this.head;
        Node cur = this.head.next;
        while (cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后判斷頭節點
        if(this.head.val == val) {
            this.head = this.head.next;
        }
    }

因為在洗掉節點時，**前驅節點一定是在判斷是否要洗掉的節點cur的前面，**也就是說通過上面的方法洗掉節點，頭結點的值沒判斷，要洗掉后面出現的value值后，要單獨判斷頭結點的情況，

🐮🐵清空單鏈表

👀😄jvm有自動回識訓制，當一個物件沒有被參考的時候就被回收了，當然我們也可以手動的將其設定了不被參考，而回收，最簡單的清空鏈表的方法把頭結點置為null，它不參考別的節點，別的節點也都不被參考，整個鏈表就被jvm回收了，當然最好還是一個一個節點的next域置為null，使他們都不被參考，
在這里插入圖片描述

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

📝📐有三個類檔案，最后把所有鏈表功能代碼放在代碼組合在一起放在MyLinkedList.java就是完整功能代碼了，下面是測驗類的代碼，用于測驗我們單鏈表的功能，還有一個鏈表節點的類檔案Node.java，

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        //myLinkedList.createList();
        myLinkedList.addLast(8);
        myLinkedList.addLast(9);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(16);
        myLinkedList.addLast(7);
        myLinkedList.show();//1  2  3  4
        myLinkedList.removeAllKey(1);
        myLinkedList.show();
   System.out.println(myLinkedList.contains(21));//false*/

    }
}

Node.java類檔案

public class Node {
    public int val;
    public Node next;//null

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

如🈶?題請🈯正，記🉐點👍🏻🍹持，🦀🦀，🦀🦀

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

標籤：其他

上一篇：二叉樹前序，中序，后序遍歷的迭代實作，實作思路及代碼

下一篇：Linux除錯工具_gdb的基本操作

鏈表的概念和結構及基本功能函式的實作（單鏈表的實作）

🎓??引言

🎓??鏈表的概念及結構

🎓??單鏈表的實作及圖示分析

📝🔷單鏈表之創建單鏈表

📝🔷單鏈表之計算單鏈表的長度

📝🔷單鏈表之列印單鏈表

📝🔷單鏈表之單鏈表的增刪查改

📝🔷頭插法插入元素

🐮🐵尾插法插入元素

🐮🐵把一個節點插入到鏈表的任意位置

🐮🐵查找鏈表中是否含有某個元素

🐮🐵洗掉鏈表中第一次出現value值的節點

🐮🐵洗掉鏈表中出現value值得所有節點

🐮🐵清空單鏈表