链表

单链表

一、链表结构

逻辑结构

二、添加

2.1直接添加到最后面

2.2找到某一位置添加=

2.3 删除

package com.love.xu.linkedList; ; /** * 单链表 * @author：下一个一千年 * @date：2020/9/3 */ public class SingleLinkedList { //先初始化一个头节点,头节点不用动，不存放具体的数据 private HeroNode head = new HeroNode(0,"",""); /** * 添加节点到单向链表 * 思路：1、找到当前链表的最后节点 * 2、将最后这个节点的next 指向 新的节点 */ public void add(HeroNode heroNode){ //因为头节点不能动，我们需要一个辅助变量,把temp当作指针一个一个向后移动 HeroNode temp = head; //遍历链表 while (true){ if(temp.next == null){ break; } //如果没有找到就向后移动 temp = temp.next; } //当推出while循环时，链表指向最后节点temp（最后节点的next为null） temp.next = heroNode; } /** * 根据排名，按顺序添加 * （如果有这个排名则添加失败） * @param heroNode */ public void addByOrder(HeroNode heroNode){ //因为头节点不能动，任然通过辅助指针来帮助找到添加的位置 //因为是单链表，我们找的temp是位于添加位置的前一个点，否则插入不进去 HeroNode temp = head; boolean flag = false; //标识添加的编号是否存在，默认为false while(true){ if(temp.next == null){ //说明temp在链表的最后 break; } if(temp.next.no > heroNode.no){ //位置找到了，就在temp的后面插入 break; }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode的编号已然存在 flag = true; break; } temp = temp.next; //后移 } //判断flag 值 if(flag){ //不能添加，说明编号存在 System.out.printf("准备插入的英雄编号 %d 已经存在了，不能加了\n",heroNode.no); }else { heroNode.next = temp.next; temp.next = heroNode; } } /** * 修改某一结点 * @param heroNode */ public void update(HeroNode heroNode){ if(head.next == null){ System.out.println("链表为空"); return; } //找到需要修改的节点 //定义一个辅助节点 HeroNode temp = head.next; 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; }else { //没有找到 System.out.printf("没有找到 编号 %d 的节点，不能修改",heroNode.no); } } /** * 删除 */ public void delete(int no){ //定义一个辅助节点 HeroNode temp = head; boolean flag = false; while (true){ //这里是判断链表移动之后的结尾了 if(temp == null){ System.out.println("链表为空"); break; } if(temp.next.no == no){ //这里是关键点temp.next.no 相当于 heroNode的上一个节点 //找到了 flag = true; break; } temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.printf("没有找到 编号 %d 的节点，不能删除",no); } } /** * 显示链表 (学会移动指针的思想) */ 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 = temp.next; } } } //每个HeroNode就是一个节点 class HeroNode{ int no; String name; String nickname; 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 + '\'' + '}'; } }