資料結構與算法Java實作-03建立一個單連結清單

day02-建立一個單連結清單

package aStudy.day2;

import sun.font.EAttribute;

import javax.sql.rowset.CachedRowSet;
import java.io.PrintWriter;
import java.time.temporal.Temporal;
import java.util.TreeMap;

/**
 * @author haoqi
 * @Date 2020/9/26 - 13:33
 *
 * 01.建立一個單連結清單
 */
public class data01 {
    public static void main(String[] args) {
        //test
        //1建立節點
        HeroNode hero1 = new HeroNode(1,"haoqi","black");
        HeroNode hero2 = new HeroNode(2,"xuxuchao","shouzi");
        HeroNode hero3 = new HeroNode(3,"dapeng","pangzi");
        HeroNode hero4 = new HeroNode(4,"saifei","liuzi");

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

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


        //按序号排列
        singleLinkedList.addOrder(hero1);
        singleLinkedList.addOrder(hero4);
        singleLinkedList.addOrder(hero2);
        singleLinkedList.addOrder(hero3);
        //4顯示沒有修改之前的
        singleLinkedList.list();
        System.out.println("\n==============\n");
        //測試要修改的節點
        HeroNode newHeroNode = new HeroNode(2,"wuzhen","xiaohai");
        singleLinkedList.update(newHeroNode);
        //4顯示
        singleLinkedList.list();
        System.out.println("\n==============\n");
        //删除節點
        singleLinkedList.deldet(1);
        singleLinkedList.deldet(4);
        singleLinkedList.list();

    }

}

//1.定義HeroNode，連結清單節點
class HeroNode{
    public int no;
    public String name;
    public String niloName;
    public HeroNode next; //指向下一個節點

    //構造器
    public HeroNode(int no, String name, String niloName) {
        this.no = no;
        this.name = name;
        this.niloName = niloName;
    }
    //顯示方法，重新toString
    @Override
    public String toString() {
        return "LinkList{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", niloName='" + niloName + '\'' +
                '}';
    }
}

//2.定義singleList 管理我們的英雄
class SingleLinkedList{
    //1初始化一個頭節點，（不能移動，Java沒有指針的概念）不存放具體資料
    private HeroNode head = new HeroNode(0,"","");

    //2傳回頭節點
    public HeroNode getHead(){
        return head;
    }
    //--->添加節點到單向連結清單，不考錄編号順序
    //3找到目前連結清單未節點，将尾節點指向新的節點
    public void add(HeroNode heroNode){
        //1因為head不能動，此時需要一個輔助節點temp
        HeroNode temp = head;
        //2周遊單連結清單
        while (true){
            //找到單連結清單末尾
            if (temp.next == null)  break;
            //不是尾節點則後移一位
            temp = temp.next;
        }
        //3while 結束表明連結清單到尾部了
        //将尾節點的next指向新增節點
        temp.next = heroNode;
    }


    //--->添加節點到單向連結清單，考錄編号順序
    //若添加元素重複，則提示添加失敗
    public void addOrder(HeroNode heroNode) {
        //1head不能移動
        //由于是單連結清單，temp輔助節點要位于插入位置之前
        HeroNode temp = head;
        boolean flag = false; //flag标志添加元素是否重複，預設false

        while (true) {
            if (temp.next == null) break;//達到尾部
            if (temp.next.no > heroNode.no) break;//位置找到在temp後面插入
            if (temp.next.no == heroNode.no) {
                flag = true;
                break;
            } //插入的元素已經重複
            //後移
            temp = temp.next;
        }
        //判斷flag值
        if (flag){
            //為真，不能添加，說明元素重複
            System.out.printf("要添加的編号 %d 已經存在，不能加入\n",heroNode.no);
        } else {
            //進行插入操作
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //3.改節點資訊，根據no編号修改
    //1利用newHeroNode 的 no 修改
    public void update(HeroNode newHeroNode){
        //判斷是否為空
        if (head.next == null){
            System.out.println("連結清單為空");
            return;
        }
        //找到需要修改的節點，定義輔助變量
        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.niloName = newHeroNode.niloName;
        } else System.out.printf("沒有找到編号 %d 的節點，無法修改",newHeroNode.no);
    }

    //4.删除節點
    //head不能移動，需要temp輔助節點
    //利用temp.next.no == no 的特性，進行操作
    public void deldet(int no){
        HeroNode temp = head;
        boolean flag = false; //标志是否找到待删除的節點
        while (true){
            if (temp.next == null) break;//達到尾部
            if (temp.next.no == no){
                //已經找到
                flag = true;
                break;
            }
            temp = temp.next; //未找到，後移
        }
        //判斷flag
        if(flag){
            // 找到，并删除
            temp.next = temp.next.next;
        }else
            System.out.printf("delete error %d\n",no);

    }


    //4顯示連結清單【周遊】
    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;
        }
    }
}