數據結構003_鏈表

  • 2020 年 9 月 17 日
  • 筆記

鏈表內容我打算就寫在這一篇里。包括單鏈表，雙向鏈表，單向及雙向環形鏈表，josephu問題。

  1. 鏈表是以節點的方式來存儲，是鏈式存儲
  2. 每個節點包含data域，next域(指向下一個節點)
  3. 鏈表在記憶體中未必是連續存儲
  4. 鏈表根據實際需求確定帶有頭結點和不帶頭結點

一 單鏈表的增刪改查

單鏈表的兩種添加方式，一種是直接載入鏈表尾部，另一種是按節點順序添加到指定位置。

兩種都比較簡單,直接上程式碼。

package com.njbj.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        // 進行測試
        // 先創建節點
        HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");
        HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吳用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");

        // 創建要給鏈表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);

        // 測試一下單鏈表的反轉功能
        System.out.println("原來鏈表的情況~~");
        singleLinkedList.list();

        // System.out.println("反轉單鏈表~~");
        // reversetList(singleLinkedList.getHead());
        // singleLinkedList.list();

        System.out.println("測試逆序列印單鏈表, 沒有改變鏈表的結構~~");
        reversePrint(singleLinkedList.getHead());

        /*
         * //加入按照編號的順序 singleLinkedList.addByOrder(hero1);
         * singleLinkedList.addByOrder(hero4);
         * singleLinkedList.addByOrder(hero2);
         * singleLinkedList.addByOrder(hero3);
         * 
         * //顯示一把 singleLinkedList.list();
         * 
         * //測試修改節點的程式碼 HeroNode newHeroNode = new HeroNode(2, "小盧", "玉麒麟~~");
         * singleLinkedList.update(newHeroNode);
         * 
         * System.out.println("修改後的鏈表情況~~"); singleLinkedList.list();
         * 
         * //刪除一個節點 singleLinkedList.del(1); singleLinkedList.del(4);
         * System.out.println("刪除後的鏈表情況~~"); singleLinkedList.list();
         * 
         * //測試一下 求單鏈表中有效節點的個數 System.out.println("有效的節點個數=" +
         * getLength(singleLinkedList.getHead()));//2
         * 
         * //測試一下看看是否得到了倒數第K個節點 HeroNode res =
         * findLastIndexNode(singleLinkedList.getHead(), 3);
         * System.out.println("res=" + res);
         */

    }

    // 方式2：
    // 可以利用棧這個數據結構，將各個節點壓入到棧中，然後利用棧的先進後出的特點，就實現了逆序列印的效果
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return;// 空鏈表，不能列印
        }
        // 創建要給一個棧，將各個節點壓入棧
        Stack<HeroNode> stack = new Stack<HeroNode>();
        HeroNode cur = head.next;
        // 將鏈表的所有節點壓入棧
        while (cur != null) {
            stack.push(cur);
            cur = cur.next; // cur後移，這樣就可以壓入下一個節點
        }
        // 將棧中的節點進行列印,pop 出棧
        while (stack.size() > 0) {
            System.out.println(stack.pop()); // stack的特點是先進後出
        }
    }

    // 將單鏈表反轉
    public static void reversetList(HeroNode head) {
        // 如果當前鏈表為空，或者只有一個節點，無需反轉，直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }

        // 定義一個輔助的指針(變數)，幫助我們遍歷原來的鏈表
        HeroNode cur = head.next;
        HeroNode next = null;// 指向當前節點[cur]的下一個節點
        HeroNode reverseHead = new HeroNode(0, "", "");
        // 遍歷原來的鏈表，每遍歷一個節點，就將其取出，並放在新的鏈表reverseHead 的最前端
        // 動腦筋
        while (cur != null) {
            next = cur.next;// 先暫時保存當前節點的下一個節點，因為後面需要使用
            cur.next = reverseHead.next;// 將cur的下一個節點指向新的鏈表的最前端
            reverseHead.next = cur; // 將cur 連接到新的鏈表上
            cur = next;// 讓cur後移
        }
        // 將head.next 指向 reverseHead.next , 實現單鏈表的反轉
        head.next = reverseHead.next;
    }

    // 查找單鏈表中的倒數第k個結點 【新浪面試題】
    // 思路
    // 1. 編寫一個方法，接收head節點，同時接收一個index
    // 2. index 表示是倒數第index個節點
    // 3. 先把鏈表從頭到尾遍歷，得到鏈表的總的長度 getLength
    // 4. 得到size 後，我們從鏈表的第一個開始遍歷 (size-index)個，就可以得到
    // 5. 如果找到了，則返回該節點，否則返回nulll
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        // 判斷如果鏈表為空，返回null
        if (head.next == null) {
            return null;// 沒有找到
        }
        // 第一個遍歷得到鏈表的長度(節點個數)
        int size = getLength(head);
        // 第二次遍歷 size-index 位置，就是我們倒數的第K個節點
        // 先做一個index的校驗
        if (index <= 0 || index > size) {
            return null;
        }
        // 定義給輔助變數， for 循環定位到倒數的index
        HeroNode cur = head.next; // 3 // 3 - 1 = 2
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;

    }

    // 方法：獲取到單鏈表的節點的個數(如果是帶頭結點的鏈表，需求不統計頭節點)
    /**
     * 
     * @param head
     *            鏈表的頭節點
     * @return 返回的就是有效節點的個數
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) { // 空鏈表
            return 0;
        }
        int length = 0;
        // 定義一個輔助的變數, 這裡我們沒有統計頭節點
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next; // 遍歷
        }
        return length;
    }

}

// 定義SingleLinkedList 管理我們的英雄
class SingleLinkedList {
    // 先初始化一個頭節點, 頭節點不要動, 不存放具體的數據
    private HeroNode head = new HeroNode(0, "", "");

    // 返回頭節點
    public HeroNode getHead() {
        return head;
    }

    // 添加節點到單向鏈表
    // 思路，當不考慮編號順序時
    // 1. 找到當前鏈表的最後節點
    // 2. 將最後這個節點的next 指向 新的節點
    public void add(HeroNode heroNode) {

        // 因為head節點不能動，因此我們需要一個輔助遍歷 temp
        HeroNode temp = head;
        // 遍歷鏈表，找到最後
        while (true) {
            // 找到鏈表的最後
            if (temp.next == null) {//
                break;
            }
            // 如果沒有找到最後, 將將temp後移
            temp = temp.next;
        }
        // 當退出while循環時，temp就指向了鏈表的最後
        // 將最後這個節點的next 指向 新的節點
        temp.next = heroNode;
    }

    // 第二種方式在添加英雄時，根據排名將英雄插入到指定位置
    // (如果有這個排名，則添加失敗，並給出提示)
    public void addByOrder(HeroNode heroNode) {
        // 因為頭節點不能動，因此我們仍然通過一個輔助指針(變數)來幫助找到添加的位置
        // 因為單鏈表，因為我們找的temp 是位於 添加位置的前一個節點，否則插入不了
        HeroNode temp = head;
        boolean flag = false; // flag標誌添加的編號是否存在，默認為false
        while (true) {
            if (temp.next == null) {// 說明temp已經在鏈表的最後
                break; //
            }
            if (temp.next.no > heroNode.no) { // 位置找到，就在temp的後面插入
                break;
            } else if (temp.next.no == heroNode.no) {// 說明希望添加的heroNode的編號已然存在

                flag = true; // 說明編號存在
                break;
            }
            temp = temp.next; // 後移，遍歷當前鏈表
        }
        // 判斷flag 的值
        if (flag) { // 不能添加，說明編號存在
            System.out.printf("準備插入的英雄的編號 %d 已經存在了, 不能加入\n", heroNode.no);
        } else {
            // 插入到鏈表中, temp的後面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 修改節點的資訊, 根據no編號來修改，即no編號不能改.
    // 說明
    // 1. 根據 newHeroNode 的 no 來修改即可
    public void update(HeroNode newHeroNode) {
        // 判斷是否空
        if (head.next == null) {
            System.out.println("鏈表為空~");
            return;
        }
        // 找到需要修改的節點, 根據no編號
        // 定義一個輔助變數
        HeroNode temp = head.next;
        boolean flag = false; // 表示是否找到該節點
        while (true) {
            if (temp == null) {
                break; // 已經遍歷完鏈表
            }
            if (temp.no == newHeroNode.no) {
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根據flag 判斷是否找到要修改的節點
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else { // 沒有找到
            System.out.printf("沒有找到 編號 %d 的節點，不能修改\n", newHeroNode.no);
        }
    }

    // 刪除節點
    // 思路
    // 1. head 不能動，因此我們需要一個temp輔助節點找到待刪除節點的前一個節點
    // 2. 說明我們在比較時，是temp.next.no 和 需要刪除的節點的no比較
    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false; // 標誌是否找到待刪除節點的
        while (true) {
            if (temp.next == null) { // 已經到鏈表的最後
                break;
            }
            if (temp.next.no == no) {
                // 找到的待刪除節點的前一個節點temp
                flag = true;
                break;
            }
            temp = temp.next; // temp後移，遍歷
        }
        // 判斷flag
        if (flag) { // 找到
            // 可以刪除
            temp.next = temp.next.next;
        } else {
            System.out.printf("要刪除的 %d 節點不存在\n", no);
        }
    }

    // 顯示鏈表[遍歷]
    public void list() {
        // 判斷鏈表是否為空
        if (head.next == null) {
            System.out.println("鏈表為空");
            return;
        }
        // 因為頭節點，不能動，因此我們需要一個輔助變數來遍歷
        HeroNode temp = head.next;
        while (true) {
            // 判斷是否到鏈表最後
            if (temp == null) {
                break;
            }
            // 輸出節點的資訊
            System.out.println(temp);
            // 將temp後移， 一定小心
            temp = temp.next;
        }
    }
}

// 定義HeroNode ， 每個HeroNode 對象就是一個節點
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; // 指向下一個節點
    // 構造器

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    // 為了顯示方法，我們重新toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }

}

二、雙向鏈表的增刪改查

單向鏈表查找只能是一個方向，而雙向鏈表可以是向前或者向後查找

單向鏈表不能自我刪除，刪除主要靠輔助節點。雙向鏈表可自我刪除。

雙向鏈表的操作都在程式碼里了，思路就在注釋里，直接貼程式碼：

package com.njbj.linkedlist;

public class DoubleLinkedListDemo {

    public static void main(String[] args) {
        // 測試
        System.out.println("雙向鏈表的測試");
        // 先創建節點
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及時雨");
        HeroNode2 hero2 = new HeroNode2(2, "盧俊義", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吳用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林沖", "豹子頭");
        // 創建一個雙向鏈表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);

        doubleLinkedList.list();

        // 修改
        HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入雲龍");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改後的鏈表情況");
        doubleLinkedList.list();

        // 刪除
        doubleLinkedList.del(3);
        System.out.println("刪除後的鏈表情況~~");
        doubleLinkedList.list();

    }

}

// 創建一個雙向鏈表的類
class DoubleLinkedList {

    // 先初始化一個頭節點, 頭節點不要動, 不存放具體的數據
    private HeroNode2 head = new HeroNode2(0, "", "");

    // 返回頭節點
    public HeroNode2 getHead() {
        return head;
    }

    // 遍歷雙向鏈表的方法
    // 顯示鏈表[遍歷]
    public void list() {
        // 判斷鏈表是否為空
        if (head.next == null) {
            System.out.println("鏈表為空");
            return;
        }
        // 因為頭節點，不能動，因此我們需要一個輔助變數來遍歷
        HeroNode2 temp = head.next;
        while (true) {
            // 判斷是否到鏈表最後
            if (temp == null) {
                break;
            }
            // 輸出節點的資訊
            System.out.println(temp);
            // 將temp後移， 一定小心
            temp = temp.next;
        }
    }

    // 添加一個節點到雙向鏈表的最後.
    public void add(HeroNode2 heroNode) {

        // 因為head節點不能動，因此我們需要一個輔助遍歷 temp
        HeroNode2 temp = head;
        // 遍歷鏈表，找到最後
        while (true) {
            // 找到鏈表的最後
            if (temp.next == null) {//
                break;
            }
            // 如果沒有找到最後, 將將temp後移
            temp = temp.next;
        }
        // 當退出while循環時，temp就指向了鏈表的最後
        // 形成一個雙向鏈表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    // 修改一個節點的內容, 可以看到雙向鏈表的節點內容修改和單向鏈表一樣
    // 只是 節點類型改成 HeroNode2
    public void update(HeroNode2 newHeroNode) {
        // 判斷是否空
        if (head.next == null) {
            System.out.println("鏈表為空~");
            return;
        }
        // 找到需要修改的節點, 根據no編號
        // 定義一個輔助變數
        HeroNode2 temp = head.next;
        boolean flag = false; // 表示是否找到該節點
        while (true) {
            if (temp == null) {
                break; // 已經遍歷完鏈表
            }
            if (temp.no == newHeroNode.no) {
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根據flag 判斷是否找到要修改的節點
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else { // 沒有找到
            System.out.printf("沒有找到 編號 %d 的節點，不能修改\n", newHeroNode.no);
        }
    }

    // 從雙向鏈表中刪除一個節點,
    // 說明
    // 1 對於雙向鏈表，我們可以直接找到要刪除的這個節點
    // 2 找到後，自我刪除即可
    public void del(int no) {

        // 判斷當前鏈表是否為空
        if (head.next == null) {// 空鏈表
            System.out.println("鏈表為空，無法刪除");
            return;
        }

        HeroNode2 temp = head.next; // 輔助變數(指針)
        boolean flag = false; // 標誌是否找到待刪除節點的
        while (true) {
            if (temp == null) { // 已經到鏈表的最後
                break;
            }
            if (temp.no == no) {
                // 找到的待刪除節點的前一個節點temp
                flag = true;
                break;
            }
            temp = temp.next; // temp後移，遍歷
        }
        // 判斷flag
        if (flag) { // 找到
            // 可以刪除
            // temp.next = temp.next.next;[單向鏈表]
            temp.pre.next = temp.next;
            // 這裡我們的程式碼有問題?
            // 如果是最後一個節點，就不需要執行下面這句話，否則出現空指針
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("要刪除的 %d 節點不存在\n", no);
        }
    }

}

// 定義HeroNode2 ， 每個HeroNode 對象就是一個節點
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next; // 指向下一個節點, 默認為null
    public HeroNode2 pre; // 指向前一個節點, 默認為null
    // 構造器

    public HeroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    // 為了顯示方法，我們重新toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }

}

三、單向環形鏈表

1.約瑟夫問題描述：

先構成一個有n個節點的單鏈表，從k節點起從1開始計數，計到m時，對應節點從鏈表中刪除。然後再從刪除節點的下一個節點重新從1開始計數，知道最後一個節點從鏈表中刪除演算法結束。(最後產生一個出隊編號的序列)

 2.

  • 構建一個單向的環形鏈表思路：
  • 1). 先創建第一個節點, 讓 first 指向該節點，並形成環形
  • 2). 後面當我們每創建一個新的節點，就把該節點，加入到已有的環形鏈表中即可.
  • 遍歷環形鏈表思路：
  • 1). 先讓一個輔助指針(變數) curBoy，指向first節點
  • 2). 然後通過一個while循環遍歷 該環形鏈表即可 curBoy.next  == first 結束

示例和程式碼：

根據用戶的輸入，生成一個小孩出圈的順序
n = 5 , 即有5個人
k = 1, 從第一個人開始報數
m = 2, 數2下
分析：
1.  需求創建一個輔助指針(變數) helper , 事先應該指向環形鏈表的最後這個節點.
補充： 小孩報數前，先讓 first 和  helper 移動 k - 1次
2.  當小孩報數時，讓first 和 helper 指針同時 的移動  m  - 1 次
3.  這時就可以將first 指向的小孩節點 出圈
first = first .next
helper.next = first  
原來first 指向的節點就沒有任何引用，就會被回收

出圈的順序
2->4->1->5->3

 

 

package com.atguigu.linkedlist;

public class Josepfu {

    public static void main(String[] args) {
        // 測試一把看看構建環形鏈表，和遍歷是否ok
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(125);// 加入5個小孩節點
        circleSingleLinkedList.showBoy();

        // 測試一把小孩出圈是否正確
        circleSingleLinkedList.countBoy(10, 20, 125); // 2->4->1->5->3
        // String str = "7*2*2-5+1-5+3-3";
    }

}

// 創建一個環形的單向鏈表
class CircleSingleLinkedList {
    // 創建一個first節點,當前沒有編號
    private Boy first = null;

    // 添加小孩節點，構建成一個環形的鏈表
    public void addBoy(int nums) {
        // nums 做一個數據校驗
        if (nums < 1) {
            System.out.println("nums的值不正確");
            return;
        }
        Boy curBoy = null; // 輔助指針，幫助構建環形鏈表
        // 使用for來創建我們的環形鏈表
        for (int i = 1; i <= nums; i++) {
            // 根據編號，創建小孩節點
            Boy boy = new Boy(i);
            // 如果是第一個小孩
            if (i == 1) {
                first = boy;
                first.setNext(first); // 構成環
                curBoy = first; // 讓curBoy指向第一個小孩
            } else {
                curBoy.setNext(boy);//
                boy.setNext(first);//
                curBoy = boy;
            }
        }
    }

    // 遍歷當前的環形鏈表
    public void showBoy() {
        // 判斷鏈表是否為空
        if (first == null) {
            System.out.println("沒有任何小孩~~");
            return;
        }
        // 因為first不能動，因此我們仍然使用一個輔助指針完成遍歷
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的編號 %d \n", curBoy.getNo());
            if (curBoy.getNext() == first) {// 說明已經遍歷完畢
                break;
            }
            curBoy = curBoy.getNext(); // curBoy後移
        }
    }

    // 根據用戶的輸入，計算出小孩出圈的順序
    /**
     * 
     * @param startNo
     *            表示從第幾個小孩開始數數
     * @param countNum
     *            表示數幾下
     * @param nums
     *            表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // 先對數據進行校驗
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("參數輸入有誤， 請重新輸入");
            return;
        }
        // 創建要給輔助指針,幫助完成小孩出圈
        Boy helper = first;
        // 需求創建一個輔助指針(變數) helper , 事先應該指向環形鏈表的最後這個節點
        while (true) {
            if (helper.getNext() == first) { // 說明helper指向最後小孩節點
                break;
            }
            helper = helper.getNext();
        }
        // 小孩報數前，先讓 first 和 helper 移動 k - 1次
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        // 當小孩報數時，讓first 和 helper 指針同時 的移動 m - 1 次, 然後出圈
        // 這裡是一個循環操作，知道圈中只有一個節點
        while (true) {
            if (helper == first) { // 說明圈中只有一個節點
                break;
            }
            // 讓 first 和 helper 指針同時 的移動 countNum - 1
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // 這時first指向的節點，就是要出圈的小孩節點
            System.out.printf("小孩%d出圈\n", first.getNo());
            // 這時將first指向的小孩節點出圈
            first = first.getNext();
            helper.setNext(first); //

        }
        System.out.printf("最後留在圈中的小孩編號%d \n", first.getNo());

    }
}

// 創建一個Boy類，表示一個節點
class Boy {
    private int no;// 編號
    private Boy next; // 指向下一個節點,默認null

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

}

 

Tags:

VirMach 便宜 VPS