数据结构与算法第三天：单链表（带头节点）

数据结构与算法第三天：单链表（带头节点） 1、链表概述

• 链表是以节点的方式存储，又称链式存储
  • 节点包含：date域、next域，next域指向下一个节点
• 链表各个节点不一定是连续存储
• 链表分为带头节点链表和不带头节点链表

2、单链表应用

public class Demo01_SinglelinkedList {
    public static void main(String[] args) {
        // 创建节点
        Animal animal1 = new Animal(1, "小花", 1, 100);
        Animal animal2 = new Animal(3, "小黑", 3, 300);
        Animal animal3 = new Animal(2, "小黄", 2, 500);
        Animal animal4 = new Animal(6, "小猫", 6, 700);
        Animal animal5 = new Animal(5, "小白", 7, 900);

        // 添加节点
        AnimallinkedList animallinkedList = new AnimallinkedList();

        animallinkedList.addByMoney(animal1);
        animallinkedList.addByMoney(animal4);
        animallinkedList.addByMoney(animal5);
        animallinkedList.addByMoney(animal2);
        animallinkedList.addByMoney(animal3);

        // 修改节点
        Animal animal6 = new Animal(6, "笑笑", 2, 1000);

        animallinkedList.update(animal6);

        // 删除节点
        animallinkedList.delete(6);

        // 遍历链表
        animallinkedList.showlinkedList();
    }
}

// 创建带头节点的单链表
class AnimallinkedList {
    // 定义头节点
    private Animal headAnimal = new Animal(0, "", 0, 0.0);

    // 添加节点-----按添加顺序加入
    
    public void add(Animal newAnimal) {
        // 1、新建一个指针，指向当前链表的头节点
        Animal temp = headAnimal;

        // 2、使用指针，遍历整个单链表，找到最后一个节点
        while (true) {
            // 判断是否为最后一个节点
            if (temp.nextAnimal == null) {
                break;
            }

            temp = temp.nextAnimal;
        }

        // 3、修改指针指向的最后一个节点next值，并使指针指向新节点
        temp.nextAnimal = newAnimal;
    }

    // 添加节点-----按编号大小的顺序加入
    
    public void addByMoney(Animal newAnimal) {
        // 1、新建一个指针，指向当前链表的头节点
        Animal temp = headAnimal;

        boolean flag = false;//用来判断编号是否重复

        // 2、遍历链表，找到新添加节点的位置
        while (true) {
            // 已经到最后一个节点
            if (temp.nextAnimal == null) {
                break;
            }

            // 寻找新节点位置
            if (temp.nextAnimal.no > newAnimal.no) {
                break;
            } else if (temp.nextAnimal.no == newAnimal.no) {
                flag = true;//编号已经存在
                break;
            }

            temp = temp.nextAnimal;
        }

        if (flag) {
            System.out.println("编号已经存在，无法添加");
        } else {
            // 3、添加新节点
            newAnimal.nextAnimal = temp.nextAnimal;
            temp.nextAnimal = newAnimal;
        }

    }

    // 修改节点信息
    public void update(Animal newAnimal) {
        // 判断节点是否为空
        if (headAnimal.nextAnimal == null){
            System.out.println("链表为空");
            return;
        }

        // 遍历链表，修改节点信息
        // 定义一个指针
        Animal temp = headAnimal.nextAnimal;

        boolean flag = false;// 标识节点是否找到

        while (true){
            // 判断节点是否为最后一个节点
            if (temp == null){
                break;
            }
            // 找到节点
            if (temp.no == newAnimal.no){
                flag = true;
                break;
            }
            // 指针后移
            temp = temp.nextAnimal;
        }

        if (flag){
            temp.name = newAnimal.name;
            temp.money = newAnimal.money;
            temp.age = newAnimal.age;
        }else {
            System.out.println("节点没有找到");
        }
    }

    // 删除节点
    public void delete(int no){
        // 判断链表是否为空
        if (headAnimal.nextAnimal == null){
            System.out.println("链表为空");
            return;
        }

        // 遍历链表
        Animal temp = headAnimal;
        boolean flag = false;

        while (true){
            // 判断是否为最后一个节点
            if (temp.nextAnimal == null){
                break;
            }
            // 是否找到节点
            if (temp.nextAnimal.no == no){
                flag = true;
                break;
            }
            temp = temp.nextAnimal;
        }

        // 删除已找到的节点
        if (flag){
            temp.nextAnimal = temp.nextAnimal.nextAnimal;
        }else {
            System.out.println("未找到节点");
        }
    }

    // 显示链表
    public void showlinkedList() {
        // 判断链表是否为空
        if (headAnimal.nextAnimal == null) {
            System.out.println("链表为空");
            return;
        }

        // 遍历链表
        // 定义一个指针
        Animal temp = headAnimal.nextAnimal;
        while (true) {
            if (temp == null) {
                break;
            }

            // 输出节点
            System.out.println(temp);

            // 指针向后移一位
            temp = temp.nextAnimal;
        }
    }


}

// 定义节点
class Animal {

    public int no;
    public String name;
    public int age;
    public double money;
    public Animal nextAnimal;

    public Animal(int no, String name, int age, double money) {
        this.no = no;
        this.name = name;
        this.age = age;
        this.money = money;
    }

    @Override
    public String toString() {
        return "Animal{" +
                "no='" + no + ''' +
                ", name='" + name + ''' +
                ", age=" + age +
                ", money=" + money +
                '}';
    }
}

声明：如有文章侵权，请及时联系本人，以便后续及时作出修改。