链表是以节点的方式来存储，是链式存储，如下图所示，每个节点包含data域和next域，next域指向下一个节点，每个节点不一定是连续存储，链表分为带头节点的链表和不带头节点的链表。
单向链表（带头节点）逻辑结构示意图如下：
使用带head头的单向链表实现 “水浒英雄排行榜”管理
(1) 第一种方法在添加英雄时，直接添加到链表的尾部；
(2) 第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)。
（1）定义HeroNode类，每个HeroNode对象就是一个节点
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;
}
//重写toString方法
public String toString(){
return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
}
}
（2）定义SingleLinkedList来管理英雄
① 先初始化一个头节点，头节点不要动，不存放具体数据
private HeroNode head = new HeroNode(0,"","");
②添加节点到单向链表
思路（当不考虑编号顺序时）：
1.找到当前链表的最后节点
2.将最后这个节点的next指向新的节点
public void add(HeroNode heroNode){
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head;
//遍历链表，找到最后节点
while (true){
if(temp.next == null){//找到链表最后节点
break;
}
//如果没有找到链表最后节点，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点
temp.next = heroNode;
}
(3)显示链表（遍历）
public void show(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head.next;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
(4)编写主程序，创建节点，调用添加函数和显示函数
System.out.println("====不考虑编号顺序的添加节点到单向链表===");
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode hero3 = new HeroNode(3,"吴用","智多星");
HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
SingleLikedList singleLikedList = new SingleLikedList();
singleLikedList.add(hero1);
singleLikedList.add(hero2);
singleLikedList.add(hero3);
singleLikedList.add(hero4);
singleLikedList.show();
public class SingleLinedListDemo1 {
public static void main(String[] args) {
System.out.println("====不考虑编号顺序的添加节点到单向链表===");
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode hero3 = new HeroNode(3,"吴用","智多星");
HeroNode hero4 = new HeroNode(4,"林冲","豹子头");
SingleLikedList singleLikedList = new SingleLikedList();
singleLikedList.add(hero1);
singleLikedList.add(hero2);
singleLikedList.add(hero3);
singleLikedList.add(hero4);
singleLikedList.show();
}
}
//定义SingleLinkedList来管理英雄
class SingleLikedList{
//先初始化一个头节点，头节点不要动，不存放具体数据
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
/*思路（当不考虑编号顺序时）：
1.找到当前链表的最后节点
2.将最后这个节点的next指向新的节点
* */
public void add(HeroNode heroNode){
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head;
//遍历链表，找到最后节点
while (true){
if(temp.next == null){//找到链表最后节点
break;
}
//如果没有找到链表最后节点，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点
temp.next = heroNode;
}
//显示链表（遍历）
public void show(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head.next;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
}
//定义HeroNode类，每个HeroNode对象就是一个节点
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;
}
//重写toString方法
public String toString(){
return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
}
}
（1）定义HeroNode类，每个HeroNode对象就是一个节点
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;
}
//重写toString方法
public String toString(){
return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
}
}
（2）定义SingleLinkedList来管理英雄
① 先初始化一个头节点，头节点不要动，不存放具体数据
private HeroNode head = new HeroNode(0,"","");
②添加节点到单向链表
public void addByOrder(HeroNode heroNode){
//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点
HeroNode temp = head;
boolean flag = false;//flag标识添加的编号是否存在，默认为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;//temp后移,遍历当前链表
}
//判断flag的值
if(flag){
System.out.printf("准备插入节点的编号%d已经存在了，不能再插入\n",heroNode.no);
}
else//可以插入到链表中，在temp的后面
{
heroNode.next = temp.next;
temp.next = heroNode;
}
//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点
temp.next = heroNode;
}
(3)显示链表（遍历）
public void show(){
//判断链表是否为空
if(head.next == null){
System.out.println(“链表为空”);
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head.next;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
(4)编写主程序，创建节点，调用添加函数和显示函数
public static void main(String[] args) {
System.out.println("====考虑编号顺序的添加节点到单向链表===");
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode hero3 = new HeroNode(4,"吴用","智多星");
HeroNode hero4 = new HeroNode(3,"林冲","豹子头");
SingleLikedList singleLikedList = new SingleLikedList();
singleLikedList.addByOrder(hero1);
singleLikedList.addByOrder(hero2);
singleLikedList.addByOrder(hero3);
singleLikedList.addByOrder(hero4);
singleLikedList.addByOrder(hero4);
singleLikedList.show();
}
}
（1）按编号顺序添加节点到单向链表中
（2）编号已经存在的节点无法添加到单向链表中
public class SingleLinedListDemo2 {
public static void main(String[] args) {
System.out.println("====考虑编号顺序的添加节点到单向链表===");
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode hero3 = new HeroNode(4,"吴用","智多星");
HeroNode hero4 = new HeroNode(3,"林冲","豹子头");
SingleLikedList singleLikedList = new SingleLikedList();
singleLikedList.addByOrder(hero1);
singleLikedList.addByOrder(hero2);
singleLikedList.addByOrder(hero3);
singleLikedList.addByOrder(hero4);
singleLikedList.addByOrder(hero4);
singleLikedList.show();
}
}
//定义SingleLinkedList来管理英雄
class SingleLikedList{
//先初始化一个头节点，头节点不要动，不存放具体数据
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
/*思路（当不考虑编号顺序时）：
1.找到当前链表的最后节点
2.将最后这个节点的next指向新的节点
* */
public void addByOrder(HeroNode heroNode){
//因为head节点不能动，因此需要新建一个辅助变量temp,temp是位于添加位置的前一个节点
HeroNode temp = head;
boolean flag = false;//flag标识添加的编号是否存在，默认为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;//temp后移,遍历当前链表
}
//判断flag的值
if(flag){
System.out.printf("准备插入节点的编号%d已经存在了，不能再插入\n",heroNode.no);
}
else//可以插入到链表中，在temp的后面
{
heroNode.next = temp.next;
temp.next = heroNode;
}
//当退出while循环时，temp就指向了链表最后节点，将temp的next指向新的节点
temp.next = heroNode;
}
//显示链表（遍历）
public void show(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为head节点不能动，因此需要新建一个辅助变量temp
HeroNode temp = head.next;
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
}
//定义HeroNode类，每个HeroNode对象就是一个节点
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;
}
//重写toString方法
public String toString(){
return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）