总目录：地址如下看总纲
前言：
案例以水浒传 108 好汉排行为例，建议先看一遍水浒传(看了一周，看的38集 2020.11.22 日)
链表得学好，因为它是后面数据结构树和图的基础。
一、单向链表
1、链表：是有序的列表
(1)带头单链表内存中的存储：
image.png
1、链表是以节点的方式来存储,是链式存储
2、每个节点包含 data 域， next 域：指向下一个节点.
3、如图：发现链表的各个节点不一定是连续存储.
4、链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
(2)带头单链表逻辑结构示意图：
image.png
1、逻辑上看就是，根据头连续，但是内存中的排布则未必连续存储
2、就像你的爷爷，父亲，你(三代人，是连续的)，但是你们三人家族在这个世界
不同的角落，身边出现的可能是其他家族的人，他们也是这样的连续子代关系
3、宗族看逻辑图，世界看内存图(世界是广度现实)
(3)小结：
对这两幅图，我想了一个口令：逻辑有序，内存无序
2、单链表：直接插入(按插入顺序插入)，无考虑到排行
(1)思路：
image.png
一、添加（创建）
1、先创建一个head 头节点， 作用就是表示单链表的头
2、后面我们每添加一个节点，就直接加入到 链表的最后
二、遍历：
1、通过一个辅助变量遍历，帮助遍历整个链表，为null 终止
(2)代码：
package com.kk.datastructure.linkedlist;
/**
* title: 单链表案例
* @author 阿K
* 2020年11月22日 下午7:41:20
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
//先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
//创建要给链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//加入
singleLinkedList.add(hero1);
singleLinkedList.add(hero4);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.list();
}
}
//定义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
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
// 定义 SingleLinkedList 管理梁山英雄
class SingleLinkedList{
// 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
private HeroNode head = new HeroNode(0, null, null);
// 返回头结点
public HeroNode getHead() {
return head;
}
// 添加节点到单向链表
// 思路，当不考虑编号顺序时
// 1. 找到当前链表的最后节点
// 2. 将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode) {
// 因为head节点不能动，因此我们需要一个辅助变量 temp（可以理解为晁天王）
HeroNode temp = head;
// 遍历链表，找到最后
while(true) {
// 找到链表的最后是null
if(temp.next == null)break;
// 若没有找到最后，则后移(这里是n+1次的，n个有效数据)
temp = temp.next;
}
// 当退出while循环时，temp就指向了链表的最后
// 将最后这个节点的next 指向 新的节点
temp.next = heroNode;
}
// 遍历链表
public void list() {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表为空~~~");
return;
}
// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true) {
// 判断是否到链表的最后
if (temp == null)
return;
// 输出节点信息
System.out.println(temp);
// 将节点后移，注意要加！！
temp = temp.next;
}
}
}
(3)缺点：
1、无法按照英雄编号排序，只能按照插入顺序。
2、并且重复了同排行序号的英雄，也随意可以添加，这是在梁山不被允许的。
3、单链表：按顺序插入，删除，修改，重复排行不得添加
(1)添加<按照编号顺序>的思路：
image.png
1、首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
2、新的节点 a，a.next = temp.next
3、将temp.next = a ，新的节点
(2)修改：
编号不变，姓名和外号可变
(3)删除节点的思路
image.png
1、我们先找到 需要删除的这个节点的前一个节点 temp
2、temp.next = temp.next.next
3、被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收
(4)以上增、改、删的代码：
package com.kk.datastructure.linkedlist.improve;
/**
* title: 单链表案例(增强版)
* @author 阿K
* 2020年11月22日 下午10:00:09
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
//先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
//创建要给链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
// singleLinkedList.addByOrder(hero3);
// singleLinkedList.list();
// 修改
// singleLinkedList.update(new HeroNode(1, "送浆", "白日"));
// singleLinkedList.list();
// 删除
singleLinkedList.delete(1);
singleLinkedList.delete(2);
singleLinkedList.delete(3);
singleLinkedList.delete(4);
singleLinkedList.list();
}
}
//定义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
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
// 定义 SingleLinkedList 管理梁山英雄
class SingleLinkedList{
// 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
private HeroNode head = new HeroNode(0, null, null);
// 返回头结点
public HeroNode getHead() {
return head;
}
// 删除
//1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
//2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
public void delete(int no) {
HeroNode temp = head;
boolean flag = false;// 标志是否找到待删除节点
while(true) {
if(temp.next ==null)
// 已经到链表的最后
break;
if(temp.next.no == no) {
// 已经找到
flag = true;
break;
}
// 移动继续找
temp = temp.next;
}
// 通过 flag 进行判断
if(flag) {
// 已经找到，指向后一个引用
temp.next = temp.next.next;
}else
System.out.printf("没有找到排行为【%d】要修改的英雄",no);
}
// 更新节点的信息, 根据no编号来修改，即no编号不能改
public void update(HeroNode heroNode) {
// 判空
if(head.next == null) {
System.out.println("链表为空~~");
return;
}
// 根据 no 找到需要修改的节点
// 定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false;// 表示是否找到节点
while (true) {
if (temp == null)
// 链表已经遍历完
break;
if(temp.no == heroNode.no) {
// 节点已经找到
flag = true;
break;
}
// 节点移动，继续找
temp = temp.next;
}
// 根据 flag 判断
if(flag) {
// 找到，修改姓名和外号
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.printf("没有找到排行为【%d】要修改的英雄",heroNode.no);
}
}
// 按编号顺序添加（如果有这个排名，则添加失败，并给出提示）
public void addByOrder(HeroNode heroNode) {
// 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
// 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false;// flag标志添加的编号是否存在，默认为false
while(true) {
if(temp.next == null) break;
if(temp.next.no > heroNode.no)
// 位置找到，就在 temp后面
// 因为 它满足了 按顺序 ，所以可以插入
break;
if(temp.next.no == heroNode.no) {
// 已经存在改排行的编号(不可重复)
flag = true;
break;
}
// 没满足以上，后移下一次节点继续找
temp = temp.next;
}
// 对 flag 进行判断
if(flag)
// 不能添加，说明编号已经存在
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
else {
// 插入到链表中，temp的后面
heroNode.next = temp.next;// 我后面的是6号，现在你后面是6号
temp.next = heroNode;// 我后面是你
}
}
// 遍历链表
public void list() {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表为空~~~");
return;
}
// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true) {
// 判断是否到链表的最后
if (temp == null)
return;
// 输出节点信息
System.out.println(temp);
// 将节点后移，注意要加！！
temp = temp.next;
}
}
}
4、单向链表经典面试题(新浪，百度，腾讯) --- 5题
1、题目以及思路：
1、求单链表中有效节点的个数
(1)遍历节点后的个数即可
2、查找单链表中的倒数第k个结点 【新浪面试题】
(1) 有效的总长度 - 要查询的位置 = 倒数的位置 【8-2=6】
3、单链表的反转【腾讯面试题，有点难度】
image.png
image.png
(1)先定义一个节点 reverseHead = new HeroNode()
(2)从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
(3)原来的链表的head.next = reverseHead.next
4、从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
(1) 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议
(2) 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.
image.png
5、合并两个有序的单链表，合并之后的链表依然有序
(1)创建一个新链表，然后比较两个链表谁排行高，则先存入新链表中
image.png
1-2-3-4-5 五题的代码：
package com.kk.datastructure.linkedlist.interview;
import java.util.Stack;
/**
* title: 单链表的面试题
* @author 阿K
* 2020年11月22日 下午10:36:50
*/
public class SingleLinkedListInterview {
/**
* @param args
*/
public static void main(String[] args) {
// 先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
HeroNode hero5 = new HeroNode(5, "鲁智深", "花和尚");
HeroNode hero6 = new HeroNode(6, "武松", "行者");
// 创建要给链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
// singleLinkedList.addByOrder(hero1);
// singleLinkedList.addByOrder(hero4);
// singleLinkedList.addByOrder(hero2);
// singleLinkedList.addByOrder(hero3);
singleLinkedList.list();
// 有效个数
int length = singleLinkedList.getLength(singleLinkedList.getHead());
System.out.printf("有效个数为：%d\n",length);
// 倒数第 K 的节点
HeroNode resultNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 3);
System.out.println(resultNode);
// 链表反转
singleLinkedList.reversetList(singleLinkedList.getHead());
singleLinkedList.list();
// 利用栈反向打印
singleLinkedList.reversetPrint(singleLinkedList.getHead());
System.out.println("--------------------美丽的分割线---------------------------");
SingleLinkedList singleLinkedList1 = new SingleLinkedList();
SingleLinkedList singleLinkedList2 = new SingleLinkedList();
singleLinkedList1.add(hero6);
singleLinkedList1.add(hero2);
singleLinkedList1.add(hero4);
singleLinkedList2.add(hero5);
singleLinkedList2.add(hero1);
singleLinkedList2.add(hero3);
// singleLinkedList1.list();
// singleLinkedList2.list();
System.out.println("--------------------美丽的分割线---------------------------");
HeroNode newHead = singleLinkedList.sumLinkedList(singleLinkedList1.getHead(),
singleLinkedList2.getHead());
SingleLinkedList singleLinkedList3 = new SingleLinkedList();
singleLinkedList3.setHead(newHead);
singleLinkedList3.list();
}
}
//定义 SingleLinkedList 管理梁山英雄
class SingleLinkedList {
// 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
private HeroNode head = new HeroNode(0, null, null);
// 返回头结点
public HeroNode getHead() {
return head;
}
public void setHead(HeroNode head) {
this.head = head;
}
/**
* 题目五：合并两个有序的单链表，合并之后的链表依然有序
* @param head1
* @param head2
* 想了很久，有两个解法：只实现方案一
* 方案一：遍历A 链表找出最小的号，再遍历B链表找出最小，然后比较
* 小的先插入到新链表中，依次重复(每一次最小的，要被摘除)--有问题未解决
* 方案二：就是模仿数组的冒泡排序，左右比较交换，未实现
* @return
*/
public static HeroNode sumLinkedList(HeroNode head1,HeroNode head2) {
// 判空
if(head1.next ==null || head2.next == null)return null;
// 定义一个新链表 用于存储合并
//SingleLinkedList singleLinkedList = new SingleLinkedList();
// 定义一个新链表的头
HeroNode newHead = new HeroNode(0, "", "");
// 先合并再排序
// 合并 head1 链表最后一个接 head2的后米面一个
HeroNode cuc1 = head1.next;
HeroNode temp = null;
while(cuc1!=null) {
// 最后一个为null 将他前一个先保存
temp = cuc1;
cuc1 = cuc1.next;
}
// head2 绑定head1 的后面一个
temp.next = head2.next;
// 现在已经输合并的无序链表 head1
// 遍历得到最小
HeroNode minNode = null;
// 最小的前一个，用于摘除原始最小
HeroNode minNodeFront = null;
// 辅助遍历最小
HeroNode minTemp1 = head1.next;
// 填充 次数为 链表长度
int lengt1 = SingleLinkedList.getLength(newHead);
int lengt2 = SingleLinkedList.getLength(head1);
while(SingleLinkedList.getLength(newHead)<=lengt2)
{
while(minTemp1.next != null) {
minNode = minTemp1;
// 临时保存 用于摘除它后面的
//HeroNode minTemp2 = minTemp1;
if(minNode.no > minNode.next.no) {
// 赋值
minNodeFront = minTemp1;
minNode = minNode.next;
}
// 后移
minTemp1 = minTemp1.next;
}
// 摘除最小
minNodeFront.next = minNodeFront.next.next;
// 绑定到 新链表
minNode.next = newHead.next;
newHead.next = minNode;
}
return newHead;
}
/**
* 题目四：反向打印链表(栈)
* @param head
*/
public static void reversetPrint(HeroNode head) {
// 判空
if(head.next == null)return;
// 创建一个栈，用于节点出入栈，实现反向打印
Stack<HeroNode> stack = new Stack();
// 定义辅助指针，用于遍历原始链表
HeroNode cuc = head.next;
// 将链表所有节点入栈
while (cuc != null) {
stack.push(cuc);// 节点 入栈
cuc = cuc.next;// 节点后移
}
// 所有节点依次出栈
while( stack.size() >0) {
//stack的特点是先进后出
System.out.println(stack.pop());
}
}
/**
* 题目三：单链表的反转【腾讯面试题，有点难度】
*
* @param head
*/
public static void reversetList(HeroNode head) {
// 若链表为空，或者只有一个则不需要反转
if (head.next == null || head.next.next == null) {
return;
}
// 定义一个辅助指针，用户遍历原始未反转的那个链表
HeroNode cuc = head.next;
// 用于动态指向 当前节点【cuc】的 下一个节点
HeroNode next = null;
// 新链表(反转后的)的链表头
HeroNode reversetHead = new HeroNode(0, "", "");
// 思路： 遍历原始链表，没遍历一个节点将其取出，并放在新链表头(reversetHead)的后面的最前端
// 每一个新节点，都会取代旧的，与新链表头牵手
while (cuc != null) {
// 暂时先保存当前节点的下一个节点，用于后移
next = cuc.next;
// 将要 遍历出来的新节点，指向 新链表头 后面的最前端(将情敌的手，从她手上拨开)
cuc.next = reversetHead.next;
// 将 cuc 连接到 新的链表头后面的最前端(她的手和你牵了)
reversetHead.next = cuc;
// cuc 后移，换下一个情敌来打你
cuc = next;
}
// 将head.next 指向 reverseHead.next , 实现单链表的反转
// 新链表(她)池塘养的鱼和旧链表头(她的闺蜜)共享
head.next = reversetHead.next;
}
/**
* 题目二：查找单链表中的倒数第k个结点 【新浪面试题】
*
* @param head 传入的头结点
* @param HeroNode 需要查找的 倒数节点数据
* @return
*/
// 思路：
// 1、先遍历得到 有效数据个数（总长度--不包括头节点）
// 2、有效个数 - index = 倒数 K(size-index = k )
// 3、找到则返回当前节点，找不到返回 null
public static HeroNode findLastIndexNode(HeroNode head, int index) {
// 判空
if (head.next == null)
return null;
// 第一个遍历得到链表的长度(节点个数)
int size = getLength(head);
// 第二次遍历 size-index 位置，就是我们倒数的第K个节点
// 先做一个index的校验
if (index <= 0 || index > size) {
// 查找的位置不能大过总长
return null;
}
// 定义给辅助变量， for 循环定位到倒数的index
HeroNode cuc = head.next;// 8-2=6,倒数第二个就是第六个
for (int i = 0; i < size - index; i++) {
cuc = cuc.next;
}
return cuc;
}
/**
* 题目一：获取有效节点个数
*
* @param head 头结点(不统计)
* @return 返回有效节点个数
*/
public static int getLength(HeroNode head) {
// 判空
if (head.next == null)
return 0;
int length = 0;
// 定义辅助变量 cuc,此处没有统计 头节点
HeroNode cuc = head.next;
while (cuc != null) {
length++;
cuc = cuc.next;// 指向下一个，继续遍历
}
return length;
}
// 按编号顺序添加（如果有这个排名，则添加失败，并给出提示）
public void addByOrder(HeroNode heroNode) {
// 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
// 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false;// flag标志添加的编号是否存在，默认为false
while (true) {
if (temp.next == null)
break;
if (temp.next.no > heroNode.no)
// 位置找到，就在 temp后面
// 因为 它满足了 按顺序 ，所以可以插入
break;
if (temp.next.no == heroNode.no) {
// 已经存在改排行的编号(不可重复)
flag = true;
break;
}
// 没满足以上，后移下一次节点继续找
temp = temp.next;
}
// 对 flag 进行判断
if (flag)
// 不能添加，说明编号已经存在
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
else {
// 插入到链表中，temp的后面
heroNode.next = temp.next;// 我后面的是6号，然后我上前走过去，你走了，现在你后面是6号
temp.next = heroNode;// 我后面是你，上下两句顺序不可对调
}
}
public void add(HeroNode heroNode) {
// 因为head节点不能动，因此我们需要一个辅助变量 temp（可以理解为晁天王）
HeroNode temp = head;
// 遍历链表，找到最后
while(true) {
// 找到链表的最后是null
if(temp.next == null)break;
// 若没有找到最后，则后移(这里是n+1次的，n个有效数据)
temp = temp.next;
}
// 当退出while循环时，temp就指向了链表的最后
// 将最后这个节点的next 指向 新的节点
temp.next = heroNode;
}
// 遍历链表
public void list() {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表为空~~~");
return;
}
// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true) {
// 判断是否到链表的最后
if (temp == null)
return;
// 输出节点信息
System.out.println(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
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
二、双向链表
1、双向链表优于单向链表特点
1、单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2、单向链表不能自我删除，需要靠辅助(前一个)节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp.next = temp.next.next 待删除节点的前一个节点
2、增删改查以及思路图解
image.png
- 遍历 方和 单链表一样，只是可以向前，也可以向后查找
- 添加 (默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;- 修改 思路和 原来的单向链表一样.
- 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
3、代码实现
package com.kk.datastructure.linkedlist.doublea;
/**
* title: 双向链表
* @author 阿K
* 2020年11月26日 下午9:46:14
*/
public class DoubleLinkedListDemo {
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, "林冲", "豹子头");
// 创建一个双向链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
// doubleLinkedList.add(hero1);
// doubleLinkedList.add(hero2);
// doubleLinkedList.add(hero3);
// doubleLinkedList.add(hero4);
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.list();
// // 修改
// HeroNode newHeroNode = new HeroNode(4, "公孙胜", "入云龙");
// doubleLinkedList.update(newHeroNode);
// System.out.println("修改后的链表情况");
// doubleLinkedList.list();
////
// // 删除
// doubleLinkedList.delete(3);
// System.out.println("删除后的链表情况~~");
// doubleLinkedList.list();
}
}
// 修改和遍历不变和单链表一样
class DoubleLinkedList {
// 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
private HeroNode head = new HeroNode(0, null, null);
// 返回头结点
public HeroNode getHead() {
return head;
}
// 乱序添加
public void add(HeroNode heroNode) {
// 辅助
HeroNode temp = head;
// 找到最后一个
while (temp.next != null) {
temp = temp.next;
}
// 插入到最后
temp.next = heroNode;
heroNode.pre = temp;
}
// 有序添加
public void addByOrder(HeroNode heroNode) {
// 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
// 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false;// flag标志添加的编号是否存在，默认为false
while (true) {
if (temp.next == null)
break;
if (temp.next.no > heroNode.no)
// 位置找到，就在 temp后面
// 因为 它满足了 按顺序 ，所以可以插入
break;
if (temp.next.no == heroNode.no) {
// 已经存在改排行的编号(不可重复)
flag = true;
break;
}
// 没满足以上，后移下一次节点继续找
temp = temp.next;
}
// 对 flag 进行判断
if (flag)
// 不能添加，说明编号已经存在
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
else {
// 插入到链表中，temp的后面
temp.next = heroNode;// 我后面是你
temp = heroNode.pre;
}
}
// 删除
public void delete(int no) {
// 判空
if (head.next == null)
return;
HeroNode temp = head.next;// 不在是需要前一个来删除
boolean flag = false;// 标志是否找到待删除节点
while (true) {
if (temp.next == null)
// 已经到链表的最后
break;
if (temp.next.no == no) {
// 已经找到
flag = true;
break;
}
// 移动继续找
temp = temp.next;
}
// 通过 flag 进行判断
if (flag) {
temp.pre.next = temp.next;// 我前面说他后面 是 我后面
// 这里我们的代码有问题?
// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
if (temp.next != null)
temp.next.pre = temp.pre;// 我后面说他前面 是 我前面
} else
System.out.printf("没有找到排行为【%d】要修改的英雄", no);
}
// 更新节点的信息, 根据no编号来修改，即no编号不能改
public void update(HeroNode heroNode) {
// 判空
if (head.next == null) {
System.out.println("链表为空~~");
return;
}
// 根据 no 找到需要修改的节点
// 定义一个辅助变量
HeroNode temp = head.next;
boolean flag = false;// 表示是否找到节点
while (true) {
if (temp == null)
// 链表已经遍历完
break;
if (temp.no == heroNode.no) {
// 节点已经找到
flag = true;
break;
}
// 节点移动，继续找
temp = temp.next;
}
// 根据 flag 判断
if (flag) {
// 找到，修改姓名和外号
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
} else {
System.out.printf("没有找到排行为【%d】要修改的英雄", heroNode.no);
}
}
// 遍历链表
public void list() {
// 判断链表是否为空
if (head.next == null) {
System.out.println("链表为空~~~");
return;
}
// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
HeroNode temp = head.next;
while (true) {
// 判断是否到链表的最后
if (temp == null)
return;
// 输出节点信息
System.out.println(temp);
// 将节点后移，注意要加！！
temp = temp.next;
}
}
}
//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
public int no; // 好汉排行
public String name; // 好汉姓名
public String nickname;// 好汉外号
public HeroNode next; // 指向下一个节点（好汉），默认为Null
public HeroNode pre; // 指向上一个节点（好汉），默认为Null
// 构造器
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
// 为了显示方法，我们重新toString
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
