水浒传排名榜：数据结构--单向链表

一、链表的概念：

        1.链表也是一个有序的列表

        2.链表是以节点的方式存储数据，是链式存储

        3.链表中每个节点包含俩部分：data域【保存数据】，next域【保存下一节点地址】

       注意：链表中的节点并不一定是连续的

head是头节点，头节点并不保存任何数据，只保存下一节点地址。可以看出 a1和a2并不是连续的

a6是尾节点，他的next域是null。

---

二、使用链表完成对水浒传英雄榜排名的管理【注意：在进行对链表的操作时，头节点不能动】

        1、要求：完成对英雄的增删改查操作。增加操作分为俩种：一是直接插入尾部，二是按顺序插入。英雄的属性：no【排名】，name【姓名】，nickName【昵称】

       2.思路：

                首先对英雄类的属性进行定义：

//英雄类class Hero{ int no ; // 排名 String name ; //姓名 String nickName ; //昵称 Hero next ; //next域，指向下一节点 public Hero(int no, String name, String nickName) { this.no = no; this.name = name; this.nickName = nickName; } @Override public String toString() { return "Hero{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; }}

               (1)、增加--直接插入链表尾部：

                       1、 创建头节点

//创建头节点 Hero head = new Hero(0,"","");

    

                       首先要找到链表的尾部，怎么找到链表的尾部呢？

                        我们知道链表中最后一个节点next==null。可以利用这一条件判断是否到达链表的尾部。将最后节点的next域指向增加的节点

 代码实现：

//增加 public void add(Hero hero){ //需要先将头节点保存到一个变量中，因为头节点是不能动的。 Hero temp = head; while(true){ if (temp.next == null){ break ; } temp = temp.next ; //temp后移，继续判断 } temp.next = hero ; //退出while循环时，说明到达了链表的尾部 }

---

 (2)、按顺序增加

                1)、首先要明白我们在按顺序增加的时候，是通过比较No的大小进行增加 

                2)、我们找到的位置并不是增加节点的位置，而是增加节点的前一个位置。如果不找到前一个节点的位置，由于是单向链表，所以无法对增加节点进行连接。  

                3)、对前一个位置的next域指向新增加节点，将新增加节点的next域指向后一个节点进行连接           

 图解：

代码实现：

//按顺序增加 public void addByID(Hero hero){ Hero temp = head; boolean flag = false ; //标记no是否重复 while(true){ /* 终止循环的三个条件： 1、不管找没找到位置，遍历到最后一个节点时都要结束 2、no重复不允许增加，也要结束循环 3、找到了位置，结束循环 */ if (temp.next == null){ //到最后一个节点 break; } if (temp.next.no == hero.no){ //说明no重复 flag = true ; break ; }else if (temp.next.no > hero.no){ //找到了增加的位置 break ; } temp = temp.next ; //节点后移继续进行判断 } if (flag){ System.out.println("No重复"); }else{ //这里进行插入新节点 hero.next = temp.next ; temp.next = hero ; } }

           

---

(4)、删除节点    

        1)、也是通过no进行查找

        2)、找到是待删除节点的前一个节点，与按顺序插入相同。

        3)、找到删除节点后，直接将前一个节点的next域指向删除节点的后一个next域【temp.next= temp.next.next】。

 图解：

 代码实现：

//删除节点 public void del(int no){ if (head.next == null){ System.out.println("空链表"); return ; } Hero temp = head ; boolean flag = false ; //标记是否找到待删除的节点 while(true){ if (temp.next.no == no){ flag = true ; break ; } temp = temp.next ; //temp后移，继续判断下一个节点 } if (flag){ //将删除节点的前一个节点的next域指向删除节点的后一个节点的next域 temp.next = temp.next.next ; }else{ System.out.println("输入的No不存在"); } }

       (5)、遍历链表

//遍历链表 public void show(){ if(head.next == null){ System.out.println("空链表"); return ; } //从第一个节点开始 Hero temp = head.next ; while(true){ if (temp == null){ //只要temp不等于null就一直遍历 break; } //进行遍历 System.out.println(temp); temp = temp.next ; } }

(6)、实现对单链表的反转

图解：

       思路：   

                      1）、将新节点的下一节点先保存到next变量中。用于temp后移【因为在后续反转中temp的值会被改变，不保存下一节点，无法向后移动】【next = temp.next】

                       2)、  将新节点的next域指向反转链表头结点的下一节点。【temp.next = reverseHead.next】

                       3)、、将反转链表头结点的next域指向新节点【reverseHead.next = temp】

                        4)、将temp后移【temp= next】

                       5)、 所有节点遍历完，最后将原链表的头结点与反转之后的链表进行连接【head.next = reverseHead.next】

代码实现：

//实现链表反转 public void reverseLink(Hero head) { if (head.next == null || head.next.next == null) { //如果是空链表或者只有一个节点，无需进行反转 return; } Hero temp = head.next; Hero next = null;//用于保存temp的下一个节点,方便temp进行后移 Hero reverseHead = new Hero();//反转链表的 头节点 while (temp != null) { next = temp.next; //将temp的下一个节点保存到next中 temp.next = reverseHead.next; //将新节点与反转链表后面的节点进行连接 reverseHead.next = temp; //将新节点放到反转链表头结点的后边 temp = next;//temp后移 } //退出while循环时，将原链表与反转后的链表连接上 head.next = reverseHead.next; }