链表的特点
- 链表是以节点的形式存储数据，是链式存储。
- 每个节点包含data域，next域，data域存数据，next域存储下一个节点的地址。
- 链表的每个节点在内存中不一定是连续存储的。
- 链表分为带头节点的链表和不带头节点的链表，根据实际的需求来确定。
这里来看看怎么用带head头的带向链表实现水浒英雄的排行榜管理。
不带排序功能的单向链表
首先来看看如何实现一个不带排序功能的排行榜管理。
- 创建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 + '\'' +
'}';
}
}
- 创建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;
}
}
}
- 创建测试方法，新增四个节点，然后调用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();
}
最后输出结果可以看到，已经对节点进行排序了。
