【数据结构】Java实现自定义单链表

Alan 516 2022-09-02
链表的特点
  1. 链表是以节点的形式存储数据,是链式存储。
  2. 每个节点包含data域,next域,data域存数据,next域存储下一个节点的地址。
  3. 链表的每个节点在内存中不一定是连续存储的。
  4. 链表分为带头节点的链表和不带头节点的链表,根据实际的需求来确定。

这里来看看怎么用带head头的带向链表实现水浒英雄的排行榜管理。

不带排序功能的单向链表

首先来看看如何实现一个不带排序功能的排行榜管理。

  1. 创建HeroNode类,有no编号,name名称,nickname昵称三个属性。创建构造器,重写toString方法。
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;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
  1. 创建SingleLinkedList类,初始化head头节点,创建添加元素的方法,添加元素的逻辑是:首先找到最后一个节点,然后将最后一个元素的next指针指向新加的节点。创建list方法,通过辅助变量获取下一个节点,如果辅助变量不为空,输出这个辅助变量,然后将辅助变量移动到下一位。
class SingleLinkedList {
    /**
     * 创建初始化节点
     */
    public HeroNode head = new HeroNode(0, "", "");

    /**
     * 如果不考虑顺序问题:
     * 1.找到最后一个节点
     * 2.将最后一个节点的next指针指向新加的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        //定义一个temp
        HeroNode temp = head;
        while (temp.next != null) {
            //找到最后一个了。
            temp = temp.next;
        }
        //当推出while循环时,temp指向了链表的最后。
        temp.next = heroNode;
    }

    public void list() {
        //判断链表是否为空。
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //需要辅助变量来遍历
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
  1. 创建测试方法,新增四个节点,然后调用list方法查看这个单向链表。
###public static void main(String[] args) {
    HeroNode node1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode node2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode node3 = new HeroNode(2, "吴用", "智多星");
    HeroNode node4 = new HeroNode(3, "林冲", "豹子头");

    SingleLinkedList singleListList = new SingleLinkedList();
    singleListList.add(node1);
    singleListList.add(node2);
    singleListList.add(node3);
    singleListList.add(node4);

    singleListList.list();
}

调用结果:

但是如果添加的时候不按照no顺序添加,list输出的HeroNode也不是按照顺序输出的。

带排序功能的单向链表

分析:在添加元素的时候,需要根据序号找到要插入的前一个元素temp,所以实现排序的功能只需要将自己的next指向后一个元素,然后将前一个元素的next指向自己即可。

前一个元素的指针指向自己,自己的指针指向后一个元素即可。

新增一个addAndSorted方法。定义一个临时节点temp,将临时节点指向head,定义boolean变量flag表示是否有编号重复的节点,创建循环,在循环中判断temp是不是最后一个节点(temp.next==null),是的话跳出循环。判断temp的下一个节点的值的编号是不是大于新增的节点的编号,如果是的话,这个temp就是要插入的前一个元素。然后跳出循环。判断temp的下一个节点的值的编号是不是等于新增的节点的编号,如果是的话,就表示有重复的节点。最后将temp往下移动一位。

/**
 * 乱序添加,顺序排列
 * @param heroNode
 */
public void addAndSorted(HeroNode heroNode) {
    //head.next来表示temp节点
    HeroNode temp = head;
    //定义变量表示是否有重复的节点
    boolean flag = false;
    while (true) {
        if (temp.next == null) {
            //表示是最后一个元素
            break;
        } else if (temp.next.no > heroNode.no) {
            //找到了要插入的位置
            break;
        } else if (temp.next.no == heroNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag) {
        //有重复的节点
        System.out.printf("已经存在编号为%d的节点", heroNode.no);
    } else {
        //将新加的节点的next指向temp.next
        heroNode.next = temp.next;
        //将temp的next指向自己
        temp.next = heroNode;
    }
}

改造测试方法,还是乱序添加:

    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 singleListList = new SingleLinkedList();
//        singleListList.add(node1);
//        singleListList.add(node4);
//        singleListList.add(node2);
//        singleListList.add(node3);

        singleListList.addAndSorted(node1);
        singleListList.addAndSorted(node2);
        singleListList.addAndSorted(node4);
        singleListList.addAndSorted(node3);
        singleListList.list();
    }

最后输出结果可以看到,已经对节点进行排序了。


# 数据结构 # 链表