Day03单链表学习

Day03单链表学习 单链表 一、链表介绍

链表是有序的列表，但是它在内存中是存储如下

小结:

1)链表是以节点的方式来存储,是链式存储

2)每个节点包含 data 域， next 域：指向下一个节点.

3)如图：发现链表的各个节点不一定是连续存储.

4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

二、单链表 2.1、单链表介绍

单链表(带头结点) 逻辑结构示意图如下

2.2、单链表的应用实例

使用带head头的单向链表实现 –水浒英雄排行榜管理

1)完成对英雄人物的增删改查 *** 作， 注: **删除和修改,查找
** 可以考虑学员独立完成，也可带学员完成

2)第一种方法在添加英雄时，直接添加到链表的尾部

3)第二种方式在添加英雄时，根据排名将英雄插入到指定位置
(如果有这个排名，则添加失败，并给出提示)

2.3、添加节点代码实现

未优化版本（即第一种添加方式)

package com.fafa.linkedlist;


public class SinglelinkedListDemo {

    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "李逵", "黑旋风");
        HeroNode node2 = new HeroNode(2, "宋江", "及时雨");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node4 = new HeroNode(4, "林冲", "豹子头");
        // 初始化链表
        SinglelinkedList linkedList = new SinglelinkedList();
        // 添加英雄
        linkedList.addlink(node1);
        linkedList.addlink(node4);
        linkedList.addlink(node3);
        linkedList.addlink(node2);
        // 遍历
        linkedList.findAlllink();
    }
}


class SinglelinkedList{

    private HeroNode head = null;

    public SinglelinkedList() {

        // 头结点
        head = new HeroNode(0,"","");
    }

    
    public void addlink(HeroNode heroNode){
        // 临时变量，用来寻找尾节点
        HeroNode temp = head;
        while(true){
            // 如果当前为尾结点
            if (temp.next == null){
                heroNode.next = null;
                temp.next = heroNode;
                break;
            }else {
                // 后移搜索
                temp = temp.next;
            }
        }
    }

    
    public void findAlllink(){
        HeroNode temp = head.next;
        int i = 1;
        if (isEmpty()){
            System.out.println("当前链表为空，无数据可以打印！");
            return;
        }
        while(temp != null){
            System.out.println("第"+ i +"个英雄信息如下:" + temp.toString());
            // 后移
            temp = temp.next;
            i++;
        }
    }

    
    public boolean isEmpty(){
        return head.next == null;
    }

}


class HeroNode{
    
    public int no;
    
    public String name;
    
    public String nickname;
    
    public HeroNode next;

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

    }

    public HeroNode() {

    }

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

2.4、添加节点代码优化

优化后的方法

可以直接在内存中就将数据排好，大大提升效率

public void addByOrder(HeroNode heroNode) {
    // 因为头结点不能动，所以需要辅助变量temp来找到添加位置
    // 因为是单链表，所以我们找的 temp 是位于 添加位置的前一个节点，否则添加不了
    HeroNode temp = head;
    // 用于判断是否有重复排名英雄
    boolean flag = false;
    
    // 1、要按排名进行添加，不分先来后到
    // 2、排名不得重复
    // 3、while循环里只有查找遍历，并无添加 *** 作
    while (true) {
        // 防止空指针,说明temp已经在链表最后了
        if (temp.next == null) {
            break;
        }
        // 和 当前位置的后一个比大小，如果小于后面的那个英雄的编号，那么就在此处添加即可
        if (temp.next.no > heroNode.no) {
            break;
        } else if (temp.next.no == heroNode.no) {
            // 排名重复
            flag = true;
            break;
        }
        // 指针后移
        temp = temp.next;
    }

    if (flag) {
        System.out.println("排名已经重复，无法再次添加编号：" + heroNode.no);
        return;
    } else {
        // 添加 *** 作
        heroNode.next = temp.next;
        temp.next = heroNode;
        System.out.println("添加成功！");
        return;
    }
}

测试代码

public class SinglelinkedListDemo {

    public static void main(String[] args) {
        HeroNode node1 = new HeroNode(1, "李逵", "黑旋风");
        HeroNode node2 = new HeroNode(2, "宋江", "及时雨");
        HeroNode node3 = new HeroNode(3, "吴用", "智多星");
        HeroNode node4 = new HeroNode(4, "林冲", "豹子头");
        // 初始化链表
        SinglelinkedList linkedList = new SinglelinkedList();
        // 添加英雄
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node3);
        linkedList.addByOrder(node4);
        linkedList.addByOrder(node2);

        // 遍历
        linkedList.findAlllink();
    }
}

效果图

2.5、修改节点代码的实现

public void updatelink(HeroNode heroNode) {
    if (isEmpty()) {
        System.out.println("链表为空,没有可以更改的元素！");
        return;
    }
    HeroNode temp = head;
    // 作为一个哨兵，判断是否找到要修改的目标
    boolean flag = false;
    while (true) {
        // 到了链表的最后了，也就是都遍历完毕了
        if (temp == null) {
            break;
        }
        if (temp.no == heroNode.no) {
            flag = true;
            break;
        }
        // 后移
        temp = temp.next;
    }

    if (flag) {
        temp.name = heroNode.name;
        temp.nickname = heroNode.nickname;
        return;
    } else {
        System.out.println("不好意思，没有定位到该元素，编号：" + heroNode.no);
        return;
    }
}

2.6、删除节点

public void deletelink(int no) {
    if (isEmpty()) {
        System.out.println("对不起，链表为空，无可删除对象！！！");
        return;
    }
    HeroNode temp = head;
    // 保留 temp 的值
    HeroNode front = temp;
    // 是否找到带删除节点的前一个节点
    boolean flag = false;
    while (true) {
        // 已经到链表的最后
        if (temp == null) {
            break;
        }
        if (temp.no == no) {
            flag = true;
            break;
        }
        front = temp;
        temp = temp.next;
    }

    if (flag) {
        front.next = temp.next;
        System.out.println("删除成功，编号：" + temp.no);
        return;
    } else {
        System.out.println("不好意思，没有找到编号：" + no + "的节点");
    }
}