Java數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)與面試題匯總

更新時間：2022年10月25日 11:13:40 作者：興趣使然黃小黃

由于順序表的插入刪除操作需要移動大量的元素，影響了運行效率，因此引入了線性表的鏈?zhǔn)酱鎯Α獑捂湵怼１疚臑榇蠹医榻B了單鏈表的實現(xiàn)與面試題匯總，感興趣的可以了解一下

1 單鏈表

1.1 單鏈表介紹

由于順序表的插入刪除操作需要移動大量的元素，影響了運行效率，因此引入了線性表的鏈?zhǔn)酱鎯?mdash;—單鏈表。單鏈表通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，不需要使用地址連續(xù)的存儲單元，因此它 不要求在邏輯上相鄰的兩個元素在物理位置上也相鄰。

物理結(jié)構(gòu)示意圖：

邏輯結(jié)構(gòu)示意圖：

關(guān)于單鏈表的一些說明：

鏈表是以節(jié)點的方式存儲的，每個節(jié)點包含data和next域，分別表示存儲的數(shù)據(jù)和指向下一個節(jié)點；
鏈表的各個節(jié)點不一定是連續(xù)存儲的；
可以根據(jù)實際需求來構(gòu)造是否帶有頭節(jié)點的鏈表。

1.2 單鏈表的實現(xiàn)思路分析

1.2.1 單鏈表的創(chuàng)建與遍歷

單鏈表的創(chuàng)建：

先創(chuàng)建一個 head 頭節(jié)點，表示單鏈表的頭；

每添加一個節(jié)點就直接加入鏈表的最后；

遍歷的思路：

創(chuàng)建一個輔助指針，用于幫助遍歷整個鏈表；

當(dāng)指針指向的節(jié)點的next域為null，說明當(dāng)前節(jié)點為最后一個，遍歷完成。 1.2.2 單鏈表節(jié)點的插入與修改

示意圖如下：

首先需要通過遍歷找到需要添加節(jié)點的位置，圖中示意的為a1的位置；
新的節(jié)點的next指向a1.next；
將該位置，即a1.next指向新的節(jié)點。

修改操作相當(dāng)于上述過程的簡化，只需要找到對應(yīng)的節(jié)點直接修改節(jié)點對應(yīng)的屬性即可，這里不再贅述。

1.2.3 單鏈表節(jié)點的刪除

刪除序號為 “2” 的節(jié)點示意圖如下：

思路如下：

找到待刪除節(jié)點的前一個節(jié)點，示例中則找到序號為1的節(jié)點；
讓該節(jié)點的 temp.next = temp.next.next，即可；
由于被刪除的節(jié)點沒有其他的指向，則會由Java的垃圾回收機制進行回收，無需處理。

1.3 實現(xiàn)代碼

StudentNode.java 節(jié)點類：

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 鏈表的節(jié)點類，包含學(xué)生信息和next
 */
public class StudentNode {
    public String no; //學(xué)號
    public String name; //姓名
    public int age; //年齡
    public StudentNode next; //指向下一個節(jié)點

    //構(gòu)造器
    public StudentNode(String no, String name, int age ){
        this.no = no;
        this.name = name;
        this.age = age;
    }

    //為了顯示方便
    @Override
    public String toString() {
        return "StudentNode{" +
                "no='" + no + '\'' +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

StudentLinkedList.java 鏈表的實現(xiàn)類：

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 鏈表的實現(xiàn)類，用于管理眾多StudentNode節(jié)點
 */
public class StudentLinkedList {
    //初始化頭節(jié)點
    private StudentNode head = new StudentNode("", "", 0);

	  //獲取頭節(jié)點
    public StudentNode getHead() {
        return head;
    }

    //添加節(jié)點
    //1.找到當(dāng)前鏈表的最后節(jié)點
    //2.將最后節(jié)點的next指向新的節(jié)點
    public void add(StudentNode studentNode) {
        StudentNode temp = head;
        //遍歷鏈表找到最后的節(jié)點
        while (temp.next != null) {
            //沒有找到，就后移
            temp = temp.next;
        }
        //最后的節(jié)點的next指向新節(jié)點
        temp.next = studentNode;
    }

    //遍歷 顯示鏈表
    public void showList(){
        //判斷鏈表是否為空
        if (head.next == null){
            System.out.println("當(dāng)前鏈表為空");
            return;
        }
        //遍歷 使用輔助指針
        StudentNode temp = head;
        while (temp != null){
            //更新指針
            temp = temp.next;
            if (temp.next == null){
                System.out.print(temp);
                break;
            }
            System.out.print(temp + "--->");
        }
    }

    //插入節(jié)點
    //根據(jù)學(xué)號順序查找添加的位置, 如果存在, 則提示錯誤信息
    public void addByOrder(StudentNode studentNode){
        //尋找的temp應(yīng)該為添加位置的前一個節(jié)點
        StudentNode temp = head;
        boolean flag = false; //標(biāo)識新添加的no是否已經(jīng)存在
        while (true){
            if (temp.next == null){
                //已經(jīng)在鏈表的尾部
                break;
            }
            if (Integer.parseInt(temp.next.no) > Integer.parseInt(studentNode.no)){
                //位置找到 插入到temp后
                break;
            }else if (Integer.parseInt(temp.next.no) == Integer.parseInt(studentNode.no)){
                //已經(jīng)存在
                flag = true;
                break;
            }
            //移動指針
            temp = temp.next;
        }
        if (flag){
            System.out.println("\n準(zhǔn)備插入的學(xué)生信息: " + studentNode.no + "，該學(xué)號已經(jīng)存在，不可添加！");
        }else {
            studentNode.next = temp.next;
            temp.next = studentNode;
        }
    }

    //根據(jù)no學(xué)號修改學(xué)生信息
    public void update(StudentNode studentNode){
        if (head.next == null){
            System.out.println("當(dāng)前鏈表為空, 無法修改");
            return;
        }
        StudentNode temp = head.next;
        boolean flag = false; //表示是否找到節(jié)點
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == studentNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = studentNode.name;
            temp.age = studentNode.age;
        }else {
            System.out.println("沒有找到");
        }
    }

    //刪除節(jié)點
    public void delete(String no){
        StudentNode temp = head;
        boolean flag = false; //標(biāo)志是否找到
        //查找到待刪除節(jié)點的前一個節(jié)點進行刪除操作
        while (true){
            if (temp.next == null){
                //到達尾部
                break;
            }
            if (temp.next.no == no){
                //找到了
                flag = true;
                break;
            }
            //遍歷
            temp = temp.next;
        }
        //刪除操作
        if (flag){
            temp.next = temp.next.next;
            System.out.println("刪除成功！");
        }else {
            System.out.println("要刪除的節(jié)點不存在！");
        }
    }
}

測試類：

/**
 * @author 興趣使然黃小黃
 * @version 1.0
 * 測試鏈表
 */
public class StudentListTest {

    public static void main(String[] args) {
        StudentNode node1 = new StudentNode("1", "黃小黃", 21);
        StudentNode node2 = new StudentNode("2", "懶羊羊", 21);
        StudentNode node3 = new StudentNode("3", "沸羊羊", 22);
        //創(chuàng)建單鏈表 錄入數(shù)據(jù) 輸出
        StudentLinkedList list = new StudentLinkedList();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        System.out.println("遍歷鏈表:");
        list.showList();
        //測試插入數(shù)據(jù)方法
        StudentNode node5 = new StudentNode("5", "美羊羊", 19);
        StudentNode node4 = new StudentNode("4", "暖羊羊", 19);
        list.addByOrder(node5);
        list.addByOrder(node4);
        System.out.println("\n依次插入學(xué)號為5、4的學(xué)生后:");
        list.showList();
        //測試修改方法
        System.out.println("\n測試修改方法:");
        list.update(new StudentNode("1", "禰豆子", 10));
        list.showList();
        //測試刪除方法
        System.out.println("\n測試刪除方法:");
        list.delete("1");
        list.delete("5");
        list.showList();
    }
}

實現(xiàn)結(jié)果：

遍歷鏈表:
StudentNode{no='1', name='黃小黃', age=21}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}
依次插入學(xué)號為5、4的學(xué)生后:
StudentNode{no='1', name='黃小黃', age=21}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
測試修改方法:
StudentNode{no='1', name='禰豆子', age=10}--->StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}--->StudentNode{no='5', name='美羊羊', age=19}
測試刪除方法:
刪除成功！
刪除成功！
StudentNode{no='2', name='懶羊羊', age=21}--->StudentNode{no='3', name='沸羊羊', age=22}--->StudentNode{no='4', name='暖羊羊', age=19}
Process finished with exit code 0

2 單鏈表的面試題

2.1 統(tǒng)計單鏈表中有效節(jié)點數(shù)量

 /**
     * 
     * @param head 頭節(jié)點
     * @return 返回有效節(jié)點個數(shù)
     */
    public static int getLength(StudentNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        StudentNode temp = head.next;
        while (temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

2.2 新浪–倒數(shù)第k個節(jié)點

查找鏈表中倒數(shù)第k個節(jié)點

思路分析：

編寫一個方法，接收head頭節(jié)點和index，index表示k；
鏈表從頭到尾遍歷，求出長度（鏈表節(jié)點個數(shù)）size；
從第一個節(jié)點，遍歷size-length次，即可找到倒數(shù)第k個節(jié)點。

參考代碼：

/**
     * 獲取單鏈表中倒數(shù)第k個節(jié)點
     * @param head 鏈表的頭節(jié)點
     * @param index 倒數(shù)第 k 個元素
     * @return 返回倒數(shù)第 k 個元素，或者 null
     */
    public static StudentNode findLastIndexNode(StudentNode head, int index){
        //如果鏈表為空
        if (head.next == null){
            return null;
        }
        //得到鏈表的長度(節(jié)點個數(shù))
        int size = getLength(head);
        //遍歷 size-index次 得到倒數(shù)第index個節(jié)點
        //數(shù)據(jù)校驗
        if (index <= 0 || index > size){
            return null;
        }
        //遍歷
        StudentNode current = head.next;
        for (int i = 0; i < size - index; i++) {
            current = current.next;
        }
        return current;
    }

2.3 騰訊–單鏈表的反轉(zhuǎn)

反轉(zhuǎn)單鏈表

思路分析：

可以使用頭插法；
以原鏈表為模板，每遍歷一個節(jié)點，取出，并接在新鏈表的最前端；
原h(huán)ead頭節(jié)點，指向新的節(jié)點；
直到遍歷完為止。

參考代碼：

	/**
     * 頭插法反轉(zhuǎn)鏈表
     * @param head 接收待反轉(zhuǎn)的鏈表
     * @return 返回一個反轉(zhuǎn)后的新鏈表
     */
    public static StudentLinkedList reverseList(StudentNode head){
        if (head.next == null){
            return null;
        }
        StudentNode old = head.next; //用于遍歷舊鏈表
        //創(chuàng)建新鏈表，新鏈表根據(jù)原鏈表遍歷得到
        StudentLinkedList newList = new StudentLinkedList();
        StudentNode newHead = newList.getHead(); //新鏈表的頭節(jié)點
        //遍歷構(gòu)造
        boolean flag = true; //標(biāo)記是否為第一次添加
        while (old != null){
            //頭插法加入到新鏈表中
            StudentNode newNode = new StudentNode(old.no, old.name, old.age);
            if(flag){
                newHead.next = newNode;
                newNode.next = null;
                flag = false;
            }else {
                newNode.next = newHead.next;
                newHead.next = newNode;
            }
            old = old.next;
        }
        return newList;
    }

以上方式雖然可以實現(xiàn)鏈表的反轉(zhuǎn)，但是是以返回一個新的反轉(zhuǎn)鏈表的形式，并沒有真正意義上實現(xiàn)原地反轉(zhuǎn)，下面介紹另一種方式：

雙指針:

	/**
     * 雙指針就地反轉(zhuǎn)鏈表
     * @param head 接收鏈表的頭節(jié)點，方法中會將鏈表反轉(zhuǎn)
     */
    public static void reverse(StudentNode head){
        //如果當(dāng)前鏈表為空 或者只有一個節(jié)點 直接返回即可
        if (head.next == null || head.next.next == null){
            return;
        }
        //輔助指針遍歷原來的鏈表
        StudentNode cur = head.next; //當(dāng)前節(jié)點
        StudentNode next = null; //指向cur的下一個節(jié)點
        StudentNode reverseHead = new StudentNode("", "", 0);
        //遍歷原來的鏈表，每遍歷一個節(jié)點，就取出，放在新鏈表的最前端
        while (cur != null){
            next = cur.next; //暫時保存當(dāng)前節(jié)點的下一個節(jié)點
            cur.next = reverseHead.next; //講cur下一個節(jié)點放在鏈表最前端
            reverseHead.next = cur;
            cur = next; //cur后移動
        }
        head.next = reverseHead.next;
        return;
    }

2.4 百度–逆序打印單鏈表

從尾到頭打印單鏈表

方式一： 先將單鏈表反轉(zhuǎn)，然后再打印。但是這樣會破壞掉原有單鏈表的結(jié)構(gòu)，而題目要求僅僅是打印，因此不建議！

方式二： 利用棧模擬

將單鏈表的各個節(jié)點壓入棧中，利用棧先進后出的特點，實現(xiàn)逆序打印。

參考代碼：

    /**
     * 利用棧模擬 實現(xiàn)鏈表的逆序打印
     * @param head 鏈表的頭節(jié)點
     */
    public static void reversePrintList(StudentNode head){
        if (head.next == null){
            return; //空鏈表無法打印
        }
        //創(chuàng)建棧模擬逆序打印
        Stack<StudentNode> stack = new Stack<>(); //棧
        StudentNode cur = head.next;
        //將鏈表的所有節(jié)點壓入棧
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //逆序打印
        while (!stack.empty()){
            //出棧
            System.out.println(stack.pop());
        }
        return;
    }

以上就是Java數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)與面試題匯總的詳細(xì)內(nèi)容，更多關(guān)于Java單鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: