資料結構單鏈表SingleLinkedList，Java實作單鏈表增刪改查

鏈表介紹

鏈表是有序的串列，但是它在記憶體中是存盤是不連續的，如下：

鏈表是以節點的方式來存盤，是鏈式存盤：
①每個節點包含data域存盤資料，next域指向下一個節點
②鏈表的各個節點不一定是連續存盤
③鏈表分帶頭節點的鏈表和沒有頭節點的鏈表，根據實際的需求來確定

單鏈表(帶頭結點)邏輯結構示意圖如下：

應用示例

使用帶head頭的單向鏈表實作水滸英雄排行榜管理完成對英雄人物的增刪改查操作，

①節點類

//定義HeroNode，每個HeroNode就是一個鏈表節點
class HeroNode {
    //data域
    public int no; //編號排名
    public String name; //名字
    public String nikeName; //昵稱
    //next域
    public HeroNode next;

    //構造器
    public HeroNode(int no, String name, String nikeName) {
        this.no = no;
        this.name = name;
        this.nikeName = nikeName;
    }

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

②鏈表類

//定義SingleLinkedList管理英雄人物，相當于是鏈表
class SingleLinkedList {
    //先初始化一個頭節點，不存放具體資料，注意頭節點保持不動，后面不能直接操作它
    private HeroNode head = new HeroNode(0,null,null);

    //添加鏈表節點

    //1、不考慮編號排名（找到最后一個節點，使得最后一個節點的next指向新的節點）
    public void add1(HeroNode heroNode){
        //因為頭節點不能動，因此要一個輔助變數temp
        HeroNode temp = head;
        //遍歷找到最后
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        //當退出while就意味著找到最后一個節點了
        temp.next = heroNode;
    }

    //2、考慮編號排名（根據排名編號從小到大，若已存在則添加失敗）
    public void add2(HeroNode heroNode){
        //因為頭節點不能動，因此要一個輔助變數temp
        //因為是單鏈表，temp位于添加位置的前一個節點，否則插入不了
        HeroNode temp = head;
        boolean flag = false; //用來標記排名編號是否存在，默認不存在
        while (true){
            if (temp.next == null){ //說明temp已經在最后，直接添加
                break;
            }
            if (temp.next.no > heroNode.no){ //位置找到了，temp即在heroNode前
                break;
            }
            if (temp.next.no == heroNode.no){ //該排名編號已經存在
                flag = true;
                break;
            }
            temp = temp.next; //后移遍歷
        }
        if (flag){
            System.out.printf("編號%d已經存在，添加失敗！\n",heroNode.no);
        }else {
            //將heroNode添加進鏈表，在temp后一個
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //根據編號修改節點中的資訊，即編號不能改
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("鏈表為空!");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false; //標記是否在鏈表中找到該編號
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nikeName = newHeroNode.nikeName;
        }else {
            System.out.printf("未找到編號為%d的英雄人物",newHeroNode.no);
        }
    }

    //根據編號洗掉節點
    public void remove(HeroNode delHeroNode){
        if (head.next == null){
            System.out.println("鏈表為空！");
        }
        HeroNode temp = head;
        boolean flag = false; //標記是否找到要洗掉的節點
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.next.no == delHeroNode.no){ //應該找到的是要洗掉節點的前一個節點
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }
        else {
            System.out.println("未在鏈表中找到該編號的節點！");
        }

    }


    //顯示鏈表(遍歷)
    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.next;
        }
    }
}

③測驗類

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //英雄人物
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及時雨");
        HeroNode heroNode2 = new HeroNode(2, "盧俊義", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吳用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林沖", "豹子頭");

        //創建一個串列并采用方式一添加節點
//        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
//        singleLinkedList1.add1(heroNode1);
//        singleLinkedList1.add1(heroNode2);
//        singleLinkedList1.add1(heroNode3);
//        singleLinkedList1.add1(heroNode4);

        //創建一個串列并采用方式二添加節點
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.add2(heroNode4);
        singleLinkedList2.add2(heroNode1);
        singleLinkedList2.add2(heroNode3);
        singleLinkedList2.add2(heroNode2);
        singleLinkedList2.add2(heroNode3);

        //修改
        HeroNode newHeroNode = new HeroNode(3, "吳先生", "智much星");
        singleLinkedList2.update(newHeroNode);

        //洗掉
        singleLinkedList2.remove(heroNode2);

        //遍歷顯示鏈表
        singleLinkedList2.list();
    }
}