資料結構之連結清單(LinkedList)(一)

連結清單(Linked List)介紹

連結清單是有序的清單，但是它在記憶體中是存儲如下

1）連結清單是以節點方式存儲的，是鍊式存儲

2）每個節點包含data域（value），next域，指向下一個節點

3）各個節點不一定連續存儲，如上圖

4）連結清單分 帶頭節點的連結清單和 不帶頭節點的連結清單，根據實際需求确定

單連結清單介紹

單連結清單(帶頭結點) 邏輯結構示意圖如下

應用執行個體

使用帶head頭的單向連結清單實作 –學生成績錄入管理   {學号，姓名，分數}

1.完成學生成績的增删改查操作

2.第一種方法在添加英雄時，直接添加到連結清單的尾部

3.第二種方式在添加學生時，根據學号排序，将學生插入指定位置

第一種實作思路：

添加（建立）

1. 先建立一個head 頭節點， 作用就是表示單連結清單的頭

2. 後面我們每添加一個節點，就直接加入到 連結清單的最後

周遊：

1. 通過一個輔助變量周遊，幫助周遊整個連結清單

示意圖：

代碼執行個體:

package com.linkedList;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

        // 測試一下單連結清單的反轉功能
        System.out.println("原來連結清單的情況");
        singleLinkedList.list();
    }
}
//定義SingleLinkedList 管理我們的英雄
class SingleLinkedList {
    //先初始化一個頭節點, 頭節點不要動, 不存放具體的資料
    private StuNode head = new StuNode(0, "", "");


    //傳回頭節點
    public StuNode getHead() {
        return head;
    }

    //添加節點到單向連結清單
    //思路，當不考慮編号順序時
    //1. 找到目前連結清單的最後節點
    //2. 将最後這個節點的next 指向 新的節點
    public void add(StuNode stuNode) {

        //因為head節點不能動，是以我們需要一個輔助周遊 temp
        StuNode temp = head;
        //周遊連結清單，找到最後
        while(true) {
            //找到連結清單的最後
            if(temp.next == null) {//
                break;
            }
            //如果沒有找到最後, 将将temp後移
            temp = temp.next;
        }
        //當退出while循環時，temp就指向了連結清單的最後
        //将最後這個節點的next 指向 新的節點
        temp.next = stuNode;
    }

    //顯示連結清單[周遊]
    public void list() {
        //判斷連結清單是否為空
        if(head.next == null) {
            System.out.println("連結清單為空");
            return;
        }
        //因為頭節點，不能動，是以我們需要一個輔助變量來周遊
        StuNode temp = head.next;
        while(true) {
            //判斷是否到連結清單最後
            if(temp == null) {
                break;
            }
            //輸出節點的資訊
            System.out.println(temp);
            //将temp後移， 一定小心
            temp = temp.next;
        }
    }
}
//定義StuNode ， 定義StuNode 對象就是一個節點
class StuNode {
    public int stuNo;
    public String name;
    public String mark;
    public StuNode next; //指向下一個節點
    //構造器
    public StuNode(int stuNo, String name, String mark) {
        this.stuNo = stuNo;
        this.name = name;
        this.mark = mark;
    }
    //為了顯示方法，我們重新toString
    @Override
    public String toString() {
        return "StuNode [stuNo=" + stuNo + ", name=" + name + ", mark=" + mark + "]";
    }
}      

代碼

 輸出：

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=4, name=小紅, mark=90]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]      

 從上面可以看對外連結表存儲是根據先後錄入順序的，那麼我們想要根據stuNo存儲呢。

第二種方式在添加學生時，根據學号排序，将學生插入指定位置

實作思路：

需要按照學号的順序添加

1. 首先找到新添加的節點的位置, 是通過輔助變量(指針), 通過周遊來搞定

2. 新的節點.next = temp.next

3. 将temp.next = 新的節點

示意圖：

實作代碼：

将代碼加入SingleLinkedList中

//第二種方式在添加學生時，根據學号将學生插入到指定位置
    //(如果有這個學号，則添加失敗，并給出提示)
    public void addByOrder(StuNode stuNode) {
        //因為頭節點不能動，是以我們仍然通過一個輔助指針(變量)來幫助找到添加的位置
        //因為單連結清單，因為我們找的temp 是位于 添加位置的前一個節點，否則插入不了
        StuNode temp = head;
        boolean flag = false; // flag标志添加的編号是否存在，預設為false
        while(true) {
            if(temp.next == null) {//說明temp已經在連結清單的最後
                break; //
            }
            if(temp.next.stuNo > stuNode.stuNo) { //位置找到，就在temp的後面插入
                break;
            } else if (temp.next.stuNo == stuNode.stuNo) {//說明希望添加的stuNode的學号已然存在

                flag = true; //說明學号存在
                break;
            }
            temp = temp.next; //後移，周遊目前連結清單
        }
        //判斷flag 的值
        if(flag) { //不能添加，說明學号存在
            System.out.printf("準備插入的學生 %d 已經存在了, 不能加入\n", stuNode.stuNo);
        } else {
            //插入到連結清單中, temp的後面
            stuNode.next = temp.next;
            temp.next = stuNode;
        }
    }      

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

        // 測試一下單連結清單的反轉功能
        System.out.println("原來連結清單的情況");
        singleLinkedList.list();
    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]      

輸出

 連結清單修改：

實作思路：

1.修改節點的資訊, 根據stuNo來修改，即stuNo不能改

2.将修改的值替換

實作代碼:

//修改節點的資訊, 根據stuNo來修改，即stuNo不能改.
    //說明
    //1. 根據 newStuNode 的 stuNo 來修改即可
    public void update(StuNode newStuNode) {
        //判斷是否空
        if(head.next == null) {
            System.out.println("連結清單為空~");
            return;
        }
        //找到需要修改的節點, 根據stuNo
        //定義一個輔助變量
        StuNode temp = head.next;
        boolean flag = false; //表示是否找到該節點
        while(true) {
            if (temp == null) {
                break; //已經周遊完連結清單
            }
            if(temp.stuNo == newStuNode.stuNo) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根據flag 判斷是否找到要修改的節點
        if(flag) {
            temp.name = newStuNode.name;
            temp.mark = newStuNode.mark;
        } else { //沒有找到
            System.out.printf("沒有找到 學号 %d 的節點，不能修改\n", newStuNode.stuNo);
        }
    }      

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

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

        StuNode newStu = new StuNode(3,"王五","99");
        singleLinkedList.update(newStu);

        System.out.println("修改之後的連結清單");
        singleLinkedList.list();

    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
修改之後的連結清單
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=王五, mark=99]
StuNode [stuNo=4, name=小紅, mark=90]      

輸出

連結清單删除：

實作思路：

1. 我們先找到 需要删除的這個節點的前一個節點 temp

2. temp.next = temp.next.next(待删除節點的上一個節點next直接指向待删除節點的下一個節點)

3. 被删除的節點，将不會有其它引用指向，會被垃圾回收機制回收

示意圖:

實作代碼：

//删除節點
    //思路
    //1. head 不能動，是以我們需要一個temp輔助節點找到待删除節點的前一個節點
    //2. 說明我們在比較時，是temp.next.stuNo 和  需要删除的節點的stuNo比較
    public void del(int stuNo){
        StuNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next==null){
                break;
            }
            if(temp.next.stuNo==stuNo){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.printf("要删除的 %d 學号節點不存在",stuNo);
        }

    }      

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

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

        singleLinkedList.del(2);
        System.out.println("删除之後的連結清單");
        singleLinkedList.list();

    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
删除之後的連結清單
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]      

輸出

下面我們看幾道關于單連結清單的面試題。

1.求單連結清單中有效節點的個數

2.查找單連結清單中的倒數第k個結點 【新浪面試題】

3.單連結清單的反轉【騰訊面試題，有點難度】

4.從尾到頭列印單連結清單 【百度，要求方式1：反向周遊 。 方式2：Stack棧】

第一題思路，隻要周遊該連結清單就可得出有效節點的個數

實作代碼：

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

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

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

        singleLinkedList.del(2);
        System.out.println("删除之後的連結清單");
        singleLinkedList.list();

        System.out.println("有效節點個數="+getLength(singleLinkedList.getHead()));


    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
删除之後的連結清單
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
有效節點個數=3      

輸出

第二題思路，先周遊對外連結表有效節點數size，在第size-k個就是倒數k個節點

實作代碼：

//查找單連結清單中的倒數第k個結點 【新浪面試題】
    //思路
    //1. 編寫一個方法，接收head節點，同時接收一個index 
    //2. index 表示是倒數第index個節點
    //3. 先把連結清單從頭到尾周遊，得到連結清單的總的長度 getLength
    //4. 得到size 後，我們從連結清單的第一個開始周遊 (size-index)個，就可以得到
    //5. 如果找到了，則傳回該節點，否則傳回nulll
    public static StuNode findLastIndexNode(StuNode 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
        StuNode cur = head.next; //3 // 3 - 1 = 2
        for(int i =0; i< size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }      

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

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

        singleLinkedList.del(2);
        System.out.println("删除之後的連結清單");
        singleLinkedList.list();
        System.out.println("有效節點個數="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒數第二個節點數是"+stuNode);
    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
删除之後的連結清單
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
有效節點個數=3
倒數第二個節點數是StuNode [stuNo=3, name=小明, mark=70]      

輸出

第三題思路

1. 先定義一個節點 reverseHead = new StuNode();

2. 從頭到尾周遊原來的連結清單，每周遊一個節點，就将其取出，并放在新的連結清單reverseHead 的最前端.

3. 原來的連結清單的head.next = reverseHead.next

實作代碼：

//将單連結清單反轉
    public static void reversetList(StuNode head) {
        //如果目前連結清單為空，或者隻有一個節點，無需反轉，直接傳回
        if(head.next == null || head.next.next == null) {
            return ;
        }

        //定義一個輔助的指針(變量)，幫助我們周遊原來的連結清單
        StuNode cur = head.next;
        StuNode next = null;// 指向目前節點[cur]的下一個節點
        StuNode reverseHead = new StuNode(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;
    }      

代碼

public static void main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

        // 測試一下單連結清單的反轉功能
        System.out.println("原來連結清單的情況");
        singleLinkedList.list();
        System.out.println("反轉連結清單的情況");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();

        /*singleLinkedList.del(2);
        System.out.println("删除之後的連結清單");
        singleLinkedList.list();
        System.out.println("有效節點個數="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒數第二個節點數是"+stuNode);*/
    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
反轉連結清單的情況
StuNode [stuNo=4, name=小紅, mark=90]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=1, name=張三, mark=85]      

輸出

第四題思路

1. 上面的題的要求就是逆序列印單連結清單.

2. 方式1： 先将單連結清單進行反轉操作，然後再周遊即可，這樣的做的問題是會破壞原來的單連結清單的結構，不建議

3. 方式2：可以利用棧這個資料結構，将各個節點壓入到棧中，然後利用棧的先進後出的特點，就實作了逆序列印的效果.

實作代碼：

//方式2：
    //可以利用棧這個資料結構，将各個節點壓入到棧中，然後利用棧的先進後出的特點，就實作了逆序列印的效果
    public static void reversePrint(StuNode head) {
        if(head.next == null) {
            return;//空連結清單，不能列印
        }
        //建立要給一個棧，将各個節點壓入棧
        Stack<StuNode> stack = new Stack<StuNode>();
        StuNode 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 main(String[] args) {
        //進行測試
        //先建立節點
        StuNode hero1 = new StuNode(1, "張三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小紅", "90");

        //建立要給連結清單
        SingleLinkedList singleLinkedList = new SingleLinkedList();


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

        // 測試一下單連結清單的反轉功能
        System.out.println("原來連結清單的情況");
        singleLinkedList.list();
        System.out.println("逆序列印單連結清單");
        reversePrint(singleLinkedList.getHead());

        /*singleLinkedList.del(2);
        System.out.println("删除之後的連結清單");
        singleLinkedList.list();
        System.out.println("有效節點個數="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒數第二個節點數是"+stuNode);*/
    }      

main

原來連結清單的情況
StuNode [stuNo=1, name=張三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小紅, mark=90]
逆序列印單連結清單
StuNode [stuNo=4, name=小紅, mark=90]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=1, name=張三, mark=85]      

輸出

posted on 2019-06-01 23:35 wanbf 閱讀(...) 評論(...) 編輯 收藏