单链表
-
单链表的逻辑结构：
-
单链表在内存中的存储：
小结：
1）链表是以结点的方式来存储，是链式存储
2）每个结点包括data域和next域（指向下一个结点）
3）链表的各个结点不一定是链式存储，逻辑结构上连续，物理结构上不一定连续
4）根据实际需求来确定链表是否需要头结点 -
单链表的创建和遍历
添加操作：
// 添加结点到链表（直接添加到链表的最后）
public void add(HeroNode heronode) {
// 因为头结点不能动,辅助指针帮忙遍历
HeroNode temp = firstnode;
while (true) {
// 找到链表的最后
if (temp.next == null) {
break;
}
temp = temp.next;
}
// 当退出while循环时,就找到了链表的最后
// 将最后这个结点的next指向新结点
temp.next = heronode;
}
遍历：
// 显示链表
public void list() {
// 判断链表是否为空
if (firstnode.next == null) {
System.out.println("链表为空");
return;
}
// 因为头结点不能动,所以需要一个辅助指针
HeroNode temp = firstnode.next;
while (true) {
// 判断链表是否到最后
if (temp == null) {
break;
}
// 输出结点的信息
System.out.println(temp);
temp = temp.next;
}
}
对添加的优化（根据no添加到指定位置）：
// 首先找到新添加的结点的位置(通过辅助指针),通过遍历
// 将辅助指针.next赋值给新添加的结点 新结点.next = temp.next
// 把新添加结点的地址赋值给辅助指针.next temp.next = 新结点
public void addByOrder(HeroNode heronode) {
HeroNode temp = firstnode;
boolean flag = false;
// 头结点不能动,通过辅助指针找到添加的位置
// 因为单链表,因为我们找的temp是位于添加位置的前一个结点,否则插入不了
while (true) {
// 说明temp已经在链表最后
if (temp.next == null) {
break;
}
// 位置找到
if (temp.next.number > heronode.number) {
break;
// 新添加结点的编号已存在
} else if (temp.next.number == heronode.number) {
flag = true;
break;
}
// 后移遍历当前链表
temp = temp.next;
}
// 判断flag的值,flag为true即编号已存在,不能添加
if (flag) {
System.out.println("准备插入的编号:" + heronode.number + "\n" + "已存在");
} else {
// 插入到链表
heronode.next = temp.next;
temp.next = heronode;
}
}
单链表结点的修改：
// 单链表结点的修改
// 1.根据newheronode的编号number来修改
public void update(HeroNode newheronode) {
if (firstnode.next == null) {
System.out.println("链表为空");
}
// 链表不为空,根据编号找到需要修改的结点,通过辅助指针
HeroNode temp = firstnode.next;
boolean flag = false;// 表示是否找到
while (true) {
// 已经遍历完链表
if (temp == null) {
break;
}
// 找到需要修改的结点
if (temp.number == newheronode.number) {
flag = true;
break;
}
temp = temp.next;
}
// 根据flag判断是否找到需要修改的结点
if (flag) {
temp.name = newheronode.name;
temp.nickname = newheronode.nickname;
} else {
System.out.println("没有找到编号为 " + newheronode.number + "的结点" + "\t" + "不能修改");
}
}
删除：
注意：因为此时是单链表，必须找到待删除结点的前一个结点，否则删除不了。
public void dellist(HeroNode heronode) {
HeroNode temp = firstnode;
// HeroNode temp = firstnode.next
// 这样写会导致当要删除的结点为第一个的时候,遍历不到
boolean flag = false;
while (true) {
// 链表已经到最后
if (temp.next == null) {
break;
}
// 找到待删除结点的前一个结点
if (temp.next.number == heronode.number) {
flag = true; // 将指向需要删除的结点再往后移,此时需要删除的结
break; // 点无指向,所以遍历不到,即删除
}
// 后移
temp = temp.next;
}
// flag为true即找到
if (flag) {
temp.next = temp.next.next;
// temp.next = heronode.next;
} else {
System.out.println("要删除的结点:" + heronode.number + "\t" + "不存在");
}
}
- 求单链表有效结点的个数
// 不包含头结点
public static int count(HeroNode head) {
HeroNode temp = head.next;
int count = 0;
while (true) {
if (temp == null) {
break;
}
temp = temp.next;
count++;
}
return count;
}
- 查找单链表中倒数第k个结点
核心：通过[ 链表的大小（有效结点）-k = 移动的次数 ] 定位到查找的结点。
// 查找单链表中倒数第k个结点
public static HeroNode getLastNode(HeroNode head, int index) {
HeroNode temp = head.next;
int size = getLength(head);
if (head.next == null) {
return null;
}
if (index <= 0 || index > size) {
return null;
}
// for循环定位到倒数的index
for (int i = 0; i < size - index; i++) {
temp = temp.next;
}
return temp;
}
- 单链表的反转
头插法：
核心：将新链表的next域赋值给要插入结点的next域 —> node.next = reverse.next
将要插入的结点赋值给新链表的next域 —>reverse.next = node
public static void reverseList(HeroNode head) {
// 判断当前链表是否为空或者只有一个结点，是则无需反转
if (head.next == null || head.next.next == null) {
return;
}
HeroNode newNode = new HeroNode(0, "", "");
HeroNode temp = null;
// HeroNode temp = head.next;
HeroNode cur = head.next;
while (cur != null) {
temp = cur.next;
// temp = temp.next;
// 这一步解释了为什么需要temp指针
// 如果没有temp指针，那么原先链表后面的结点遍历不到了
cur.next = newNode.next;
newNode.next = cur;
cur = temp;
}
head.next = newNode.next;
}