資料結構-鏈表-有解無憂

單鏈表練習

介紹

鏈表以結點的方式儲存，鏈式存盤
每個結點包含data域，next域
鏈表的結點可以是連續的，也可以是不連續的
鏈表分類
- 帶頭結點的鏈表
- 沒有頭結點的鏈表

應用實體

題目：使用帶head頭的單冋鏈表實作ˉ水滸英雄排行榜管理完成對英雄人物的増刪改査操作，

功能需求

在添加英雄時，直接添加到鏈表的尾部
在添加英雄時，根據排名將英雄插入到指定位置（如果有這個排名，則添加失敗，并給出提示）
修改節點資料
洗掉節點

代碼實作

單鏈表代碼

package com.linkedlist;

public class SingleLinkedList {
    // 先初始化一個頭結點，頭結點是尋找鏈表開始，不要動它
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    /**
     * 頭插法添加新節點
     */
    public void addHead(HeroNode heroNode) {
        heroNode.next = head.next;
        head.next = heroNode;
    }

    /**
     * 尾插法添加新節點
     * @param heroNode 新節點
     */
    public void add(HeroNode heroNode) {
        // 1.首先遍歷到尾結點
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        // 2.將尾結點的next指向新節點
        temp.next = heroNode;
    }

    /**
     * 根據排名插入資料
     * @param heroNode 新節點
     */
    public void addByOrder(HeroNode heroNode) {
        // 1.首先找到新節點的插入位置
        HeroNode temp = head;
        // 如果找到尾結點還沒有找到合適的位置，則尾插到最后
        while (temp.next != null && temp.next.no <= heroNode.no) {
            temp = temp.next;
            if (temp.no == heroNode.no) {
                System.out.println(heroNode.name+"已存在,不可添加");
                return;
            }
        }
        // 2.新節點指向后節點
        heroNode.next = temp.next;
        // 3.原節點指向新節點
        temp.next = heroNode;
    }

    /**
     * 根據編號更新節點資料
     */
    public void update(HeroNode heroNode) {
        // 1.首先找到新節點的插入位置
        HeroNode temp = head;
        while (temp.next != null && temp.no != heroNode.no) {
            temp = temp.next;
        }
        // 如果跳出回圈還沒有匹配，就是找不到對應的節點
        if (temp.no != heroNode.no) {
            System.out.println("該編號不存在");
        } else {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }
    }

    /**
     * 洗掉節點
     */
    public void delete(int no) {
        // 首先找到洗掉節點的【前一個】節點
        HeroNode temp = head;
        while (temp.next != null && temp.next.no != no) {
            temp = temp.next;
        }
        // 如果沒沒有遍歷到最后一個節點說明找到了匹配的節點
        if (temp.next != null) {
            // 跳過匹配節點的鏈接
            temp.next = temp.next.next;
        } else {
            System.out.println(no + "節點不存在");
        }
    }
    /**
     * 列印鏈表資訊
     */
    public void list() {
        if (head.next == null) {
            System.out.println("鏈表為空");
            return;
        }
        // 臨時變數遍歷
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp.toString());
        }
    }

}

/**
 * 定義一個節點
 */
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;


    public HeroNode() {
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

測驗代碼

package com.linkedlist;

public class Application {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及時雨");
        HeroNode hero2 = new HeroNode(2, "李逵", "黑旋風");
        HeroNode hero3 = new HeroNode(3, "林沖", "豹子頭");

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

        // 頭插法 頭插和尾插沒有做存在判斷，可能會出現死回圈，
//        singleLinkedList.addHead(hero1);
//        singleLinkedList.addHead(hero2);
//        singleLinkedList.addHead(hero3);

        // 尾插法添加節點
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero2);


        // 按照序號排序添加節點
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);

        // 顯示所有資料
        singleLinkedList.list();

        // 修改節點資料
        HeroNode newNode = new HeroNode(1, "小宋", "下大雨");
        singleLinkedList.update(newNode);

        System.out.println("=====修改節點后=====");
        singleLinkedList.list();

        // 洗掉節點資料
        System.out.println("=====洗掉程序=====");
        singleLinkedList.delete(1);
        singleLinkedList.delete(3);
        singleLinkedList.delete(4);
        System.out.println("=====洗掉節點后=====");
        singleLinkedList.list();
    }
}

練習

求單鏈表有效節點的個數
- 從第一個有效節點開始后移，計數
【新浪】查找單鏈表倒數第k個資料
- 先獲取有效節點個數
- 再從第一個有效節點后移size-k次
【騰訊】反轉單鏈表
- 創建一個新的頭節點（看作臨時鏈表）
- 遍歷原鏈表依次將節點用頭插法存到新頭節點（記得儲存當前節點的下一個節點next）
- 原頭節點指向新頭節點的第一個有效節點
【百度】從尾到頭列印單鏈表（方式一：反向遍歷方式二：Stack）
- 呼叫堆疊的API，遍歷單鏈表將節點壓入堆疊中
- 出堆疊列印
合并兩個單鏈表，合并之后仍然有序
- 首先比較兩鏈表的長度，將短的鏈表拼接到長的鏈表
- 遍歷短的鏈表，呼叫長鏈表按編號插入的方法將節點插入

練習代碼實作

package com.linkedlist;

import java.util.Stack;

public class practice {
    public static void main(String[] args) {
        // 創建鏈表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 按照序號排序添加節點
        singleLinkedList.addByOrder(new HeroNode(2, "李逵", "黑旋風"));
        singleLinkedList.addByOrder(new HeroNode(1, "宋江", "及時雨"));
        singleLinkedList.addByOrder(new HeroNode(3, "林沖", "豹子頭"));

        // 顯示鏈表當前情況
        singleLinkedList.list();

        // 1.求單鏈表有效節點的個數
        System.out.println("1.當前鏈表有效節點個數為：" + getSingleLinkedListLength(singleLinkedList));

        // 2.【新浪】查找單鏈表倒數第k個資料
        // 假設鏈表資料 頭 1 2 3 ，有效長度：3 ， 找倒數第1個資料 ，只需要從第一個節點向后移3-1次
        HeroNode res = findLastIndexNode(singleLinkedList, 1);
        System.out.println("2.res=" + res);

        // 3.【騰訊】反轉單鏈表
//        reversalSingleLinkedList(singleLinkedList);
//        singleLinkedList.list();

        // 4.【百度】從尾到頭列印單鏈表（方式一：反向遍歷 方式二：Stack）
        System.out.println("4.逆序列印單鏈表，不破壞原鏈表");
        singleLinkedList.list();
        System.out.println("逆序列印");
        reversalPrint(singleLinkedList);

        // 5. 合并兩個單鏈表，合并之后仍然有序，
        SingleLinkedList list1 = new SingleLinkedList();
        SingleLinkedList list2 = new SingleLinkedList();
        list1.addByOrder(new HeroNode(2, "李逵", "黑旋風"));
        list1.addByOrder(new HeroNode(1, "宋江", "及時雨"));
        list1.addByOrder(new HeroNode(3, "林沖", "豹子頭"));

        list2.addByOrder(new HeroNode(4, "吳用", "智多星"));
        list2.addByOrder(new HeroNode(1, "宋江", "及時雨"));
//        list2.addByOrder(new HeroNode(5, "宋江", "及時雨"));
//        list2.addByOrder(new HeroNode(6, "宋江", "及時雨"));
//        list2.addByOrder(new HeroNode(7, "宋江", "及時雨"));

        System.out.println("+++++++二合一+++++++++++");
        System.out.println("鏈表1原資料");
        list1.list();
        System.out.println("鏈表2原資料");
        list2.list();

        boolean list1Long = true;
        // 如果鏈表1的長度大于鏈表2長度，則將鏈表2合并到鏈表1，呼叫鏈表的按編號插入方法
        if (getSingleLinkedListLength(list1) > getSingleLinkedListLength(list2)) {
            combineSingleLinkedList(list1, list2);
        } else {
            list1Long = false;
            combineSingleLinkedList(list2, list1);
        }
        System.out.println("合并后");
        if (list1Long) {
            list1.list();
        } else {
            list2.list();
        }
    }

    /**
     * 將鏈表2合并到鏈表1
     * @param list1 1
     * @param list2 2
     */
    private static void combineSingleLinkedList(SingleLinkedList list1, SingleLinkedList list2) {
        // 如果鏈表2 無資料直接回傳
        if (list2 == null || list2.getHead() == null) {
            return;
        }
        HeroNode cur2 = list2.getHead().next;
        HeroNode next2 = null;

        while (cur2 != null) {
            next2 = cur2.next;
            list1.addByOrder(cur2);
            cur2 = next2;
        }
    }

    private static void reversalPrint(SingleLinkedList singleLinkedList) {
        if (singleLinkedList == null || singleLinkedList.getHead() == null) {
            System.out.println("鏈表為空");
            return;
        }
        Stack<HeroNode> heroNodes = new Stack<>();
        HeroNode cur = singleLinkedList.getHead().next;
        while (cur != null) {
            heroNodes.push(cur);
            cur = cur.next;
        }

        while (!heroNodes.empty()) {
            System.out.println(heroNodes.pop());
        }
    }

    public static int getSingleLinkedListLength(SingleLinkedList list) {
        if (list == null || list.getHead().next == null) {
            return 0;
        }
        // 因為頭結點不算有效資料，將它視為第0個，后移一次加一個
        HeroNode cur = list.getHead();
        int length = 0;
        while (cur.next != null) {
            cur = cur.next;
            length++;
        }
        return length;
    }

    private static HeroNode findLastIndexNode(SingleLinkedList singleLinkedList, int n) {
        if (singleLinkedList == null || singleLinkedList.getHead() == null) {
            return null;
        }
        // 獲取鏈表的有效長度
        int size = getSingleLinkedListLength(singleLinkedList);
        // 檢查查找的下標的有效性
        if (n <= 0 || n > size) {
            return null;
        }
        // 從第一個結點開始移動，移動size - n 次
        HeroNode cur = singleLinkedList.getHead().next;
        for (int i = 0; i < size - n; i++) {
            cur = cur.next;
        }
        return cur;
    }

    private static void reversalSingleLinkedList(SingleLinkedList list) {
        // 只有一個節點時也不需要反轉
        if (list == null || list.getHead().next == null || list.getHead().next.next == null) {
            return;
        }
        // 定義一個新的頭節點，帶領新隊伍
        HeroNode newHead = new HeroNode();
        // 從第一個節點開始遍歷
        HeroNode cur = list.getHead().next;
        // 記錄后一個節點
        HeroNode next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;
        }

        list.getHead().next = newHead.next;
    }
}

回圈鏈表

回圈鏈表：將單鏈表中終端結點的指標端由空指標改為指向頭結點，就使整個單鏈表形成個環，

其實就是頭尾相連的單鏈表，

應用場景（約瑟夫問題）

Joseph問題為：設編號為1，2，…n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數，數到m的那個人出列，

它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列，

解決思路

實作代碼

package com.linkedlist;

public class Joseph {
    public static void main(String[] args) {
        //Joseph問題為：
        // 設編號為1，2，…n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人
        // 從1開始報數，數到m的那個人出列，
        // 它的下一位又從1開始報數，數到m的那個人又出列
        // 依次類推，直到所有人出列為止，由此產生一個出隊編號的序列，
        // 例如：5個人，從1號開始報數，報到2出列
        start(5, 1, 2);
    }

    private static void start(int n, int k, int m) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        // 添加n個小朋友 1 2 3
        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);
            circleSingleLinkedList.add(node);
        }
        // 約定k號開始報數，進行鏈表偏移
        circleSingleLinkedList.offset(k);

        // 數到2，依次出隊
        System.out.print("出列順序為：");
        for (int i = 0; i < n; i++) {
            circleSingleLinkedList.out(m);
        }
    }
}

/**
 * 單向回圈鏈表
 */
class CircleSingleLinkedList {
    // 創建一個頭結點
    private Node first;

    public void add(Node node) {
        if (first == null) {
            first = node;
            first.setNext(node);
        }
        Node temp = first;
        while (temp.getNext() != first) {
            temp = temp.getNext();
        }
        temp.setNext(node);
        // 回圈鏈表相比于單向鏈表多了最后一個節點指向頭節點，
        node.setNext(first);
    }

    public void offset(int k) {
        if (first == null) {
            System.out.println("空？");
            return;
        }
        // 第一個節點向后偏移
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
        }

    }

    public void out(int k) {
        // 校驗移動值
        if (k < 1) {
            System.out.println("k例外");
            return;
        }
        if (first == null) {
            System.out.println("沒人了");
            return;
        }

        Node temp = first;
        // 首先將temp指向最后一個節點
        while (temp.getNext() != first) {
            temp = temp.getNext();
        }

        // 從1開始報數，報數到k
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
            temp = temp.getNext();
        }
        System.out.print(first.getNo() + "\t");
        first = first.getNext();
        temp.setNext(first);
    }

    public void list() {
        if (first == null) {
            System.out.println("鏈表為空");
            return;
        }

        Node temp = first;
        // 先列印再判斷
        do {
            System.out.println(temp.getNo());
            temp = temp.getNext();
        } while (temp != first);

    }
}

/**
 * 單向鏈表的節點
 */
class Node {
    private int no;
    private Node next;

    public Node() {
    }

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

    public int getNo() {
        return no;
    }

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

    public Node getNext() {
        return next;
    }

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

雙向鏈表

使用單鏈表時的缺點分析：

查找方向只能是一個方向，不能往前查找
不能自我洗掉，需要借助臨時結點

介紹

雙向鏈表其實就是在單向鏈表的基礎上添加的一個指向父結點的變數pre

雙鏈表實作代碼

package com.linkedlist;

/**
 * 定義一個節點
 */
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 pre;
    public HeroNode2 next;

    public HeroNode2() {
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

/**
 * 雙向鏈表，pre指向前一個節點，next指向后一個節點
 * 其實就是在單鏈表的基礎上加了pre
 */
public class DoubleLinkedList {
    private HeroNode2 head = new HeroNode2();

    // 獲得雙向鏈表的頭節點
    public HeroNode2 getHead() {
        return head;
    }

    public void setHead(HeroNode2 head) {
        this.head = head;
    }

    /**
     * 遍歷鏈表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("雙向鏈表為空");
            return;
        }
        HeroNode2 temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 逆向遍歷鏈表
     */
    public void reversalList() {
        if (head.next == null) {
            System.out.println("鏈表為空");
            return;
        }
        // 臨時變數遍歷
        HeroNode2 temp = head;
        // 先從頭跑到尾
        while (temp.next != null) {
            temp = temp.next;
        }
        // 再從尾開始往前列印
        while (temp.pre != null) {
            System.out.println(temp);
            temp = temp.pre;
        }
    }

    /**
     * 添加節點
     */
    public void add(HeroNode2 node) {
        HeroNode2 temp = head;
        // 首先找到最后一個節點
        while (temp.next != null) {
            temp = temp.next;
        }
        // 雙向鏈接
        temp.next = node;
        node.pre = temp;
    }

    /**
     * 根據編號順序添加
     * @param heroNode 添加的節點
     */
    public void addByOrder(HeroNode2 heroNode) {
        // 1.首先找到新節點的插入位置
        HeroNode2 temp = head.next;
        // 如果找到尾結點還沒有找到合適的位置，則尾插到最后
        while (temp != null && temp.no <= heroNode.no) {
            if (temp.no == heroNode.no) {
                System.out.println(heroNode.name+"已存在,不可添加");
                return;
            }
            temp = temp.next;
        }
        if (temp == null) {
            // 如果遍歷到最后還沒有合適的位置則變為尾插
            add(heroNode);
        } else {
            // 2.新節點指向當前的前節點和當前節點
            heroNode.pre = temp.pre;
            heroNode.next = temp;
            // 3.前后兩節點指向新節點
            temp.pre.next = heroNode;
            temp.pre = heroNode;
        }

    }

    /**
     * 修改
     */
    public void update(HeroNode2 node) {
        if (head.next == null) {
            System.out.println("雙向鏈表為空");
            return;
        }
        HeroNode2 temp = head.next;
        // 首先遍歷鏈表，匹配到就停止回圈
        while (temp != null && temp.no != node.no) {
            temp = temp.next;
        }
        // 匹配則找到 (空鏈有問題)
        if (temp != null) {
            temp.name = node.name;
            temp.nickname = node.nickname;
        } else {
            System.out.println("找不到修改節點");
        }

    }

    /**
     * 洗掉節點
     */
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("雙向鏈表為空");
            return;
        }

        HeroNode2 temp = head.next;
        while (temp != null && temp.no != no) {
            temp = temp.next;
        }
        if (temp != null) {
            // 自身洗掉， 前節點指向后節點，后節點指向前節點，
            temp.pre.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }

        } else {
            System.out.println("找不到洗掉節點");
        }

    }
}

總結

區別	單向鏈表	雙向鏈表
尾插添加	將鏈表的最后一個節點指向新節點	將鏈表的最后一個節點指向新節點，同時需要將新節點的父指標指向最后一個節點
通過編號排序添加	找到添加位置的【前一個】節點temp 新節點指向temp的下一個，temp指向新節點	找到添加位置的節點temp heroNode.pre = temp.pre; heroNode.next = temp; ttemp.pre.next = heroNode; temp.pre = heroNode;
洗掉節點判空！	匹配到洗掉節點的【前一個】節點temp temp.next = temp.next.next; //跳過洗掉節點	匹配到洗掉節點temp (若temp是鏈表的最后一節點，特殊處理) temp.pre.next = temp.next; // 父節點指向子節點 if (temp.next != null) { temp.next.pre = temp.pre;} // 如果子節點存在，子節點指向父節點，
修改節點判空！	匹配到修改節點的編號，修改資料，做不存在處理	和單向鏈表一樣
遍歷鏈表	從頭到尾遍歷	可雙向遍歷

鏈表總結回顧

線性表是0個或多個具有相同型別的資料元素的有限序列
線性表按存盤結構分為順序存盤結構和鏈式存盤結構
- 順序存盤 -- 用陣列實作，稱為順序表，有大小限制，增刪不方便
- 鏈式存盤 -- 用結點實作，分為多種鏈表

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

標籤：其他

上一篇：17.動態規劃之青蛙跳臺階代碼實作（JavaScript版）

下一篇：0107. Binary Tree Level Order Traversal II (E)