链表（linked list）有序列表，但是存储不连续
特点：
以节点形式存储
每个节点包括data域，next域：指向下一节点
链表的各个节点不一定时连续存放的
链表分带头节点的链表和无头节点的链表，根据实际需求确定
使用带head节点的单向链表实现——水浒英雄排行榜管理
完成对英雄人物的增删改查操作
添加时两种方法，直接添加至链表尾部，或插入至指定位置
分析：
创建英雄节点（class，存放信息），创建头节点时，不存放数据表示单链表的头
/**
* 定义一个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;
}
?
public HeroNode() {
}
?
添加功能（不考虑顺序）
先创建head节点，作用是表示单链表的头
后面没添加一个节点，就直接加入到链表的尾部
/**
* 添加节点到单项链表
* 思路当不考虑编号顺序是
* 1.找到链表的最后一个节点
* 2.将最后节点的next指向新节点
* @param heroNode
*/
public void add(HeroNode heroNode){
//定义一个辅助变量
HeroNode temp = head;
?
//遍历链表，找到最后
while (true){
//找到链表最后
if (temp.next == null){
break;
}
//如果没有找到temp后移
temp = temp.next;
}
//退出循环找到最后的节点
//将最后这个节点指向新的节点
temp.next = heroNode;
}
添加功能（考虑顺序）
首先找到新添加节点的位置，通过辅助变量
新的节点.next = temp.next
将temp.next = 新的节点
/**
* 添加功能考虑顺序
* @param heroNode
*/
public void addOrder(HeroNode heroNode){
//定义辅助变量
HeroNode temp = head;
?
//标志添加编号是否存在，默认为false
boolean flag = false;
while (true){
if (temp.next == null){//已经在链表最后
break;
}
if (temp.next.no>heroNode.no){
//位置找到了，在temp后插入
break;
}else if (temp.next.no == heroNode.no){
//数据已存在
flag = true;
break;
}
temp = temp.next;//后移，遍历当前链表
}
?
//判断flag的值
if (flag == true){
//不能添加，编号存在
System.out.println("编号存在:"+temp.next.no+","+temp.next.name);
}else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
遍历：通过辅助变量，遍历单链表
修改功能
编号不变，昵称等其他信息改变
/**
* 根据根节点的id修改相应的值
* @param heroNode
*/
public void update(HeroNode heroNode){
HeroNode temp = head.next;
while (true){
if (temp.no == heroNode.no){
break;
}
temp = temp.next;
}
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}
删除节点
/**
* 根据id删除节点
* @param id
*/
public void delete(int id){
HeroNode temp = head;
while (true){
if (temp.next.no == id){
break;
}
temp = temp.next;
}
temp.next = temp.next.next;
}
清空链表
/**
* 清空链表
*/
public void clear(){
HeroNode temp = head;
temp = temp.next = null;
}
求单链表中节点的个数
/**
* 求单链表中节点的个数
* 遍历单链表
* 计数器
*/
public void getLen(){
?
HeroNode temp = head;
int count = 0;
while (true){
if (temp.next==null){
break;
}
temp = temp.next;
count++;
}
System.out.println("共有"+count+"个节点！");
}
查找单链表中倒数第k个节点
/**
* 查找单链表倒数第k个节点
* 思路：
* 链表 从头到尾遍历
* 链表长度-id，结尾查找的节点
* @param id
*/
public HeroNode selectByID(int id){
int len = getLen();
HeroNode temp = head.next;
for (int i = 0; i < len-id; i++) {
temp = temp.next;
}
return temp;
}
单链表的反转
/**
* 反转链表
* 思路：
* 1.定义一个节点reverseHead = new HeroNode()
* 2.从头到尾遍历原理啊的链表，每遍历一个节点，将其取出，并放在新的链表的最前端
* 3.原来的链表的head.next=reverseHead.next
*/
public void reverse(){
HeroNode reverseHead = new HeroNode();
HeroNode temp1 = head.next;
//指向当前节点的下一节点
HeroNode next = null;
if (temp1 == null || temp1.next == null){
return ;
}
?
//遍历原来的链表，每遍历一个节点，将其取出，并放在新的链表的最前端
while (temp1 != null){
next = temp1.next;//暂时保存当前节点的下一节点
temp1.next = reverseHead.next;//将temp1的下一节点指向新链表的最前端
reverseHead.next = temp1;//将temp1连接到新的链表上
temp1 = next;//后移一次
}
//将head.next指向reverseHead.next，实现反转
head.next = reverseHead.next;
}
}
从尾到头打印单链表【要求方式1：反向遍历。方式2：Stack栈】
/**
* 从尾到头打印单链表
* 思路一：
* 先将单链表反转，然后遍历
* 缺点：破坏原来单链表的结构
* 思路二：
* 利用栈，压栈后，利用栈先进后出的特点，实现逆序打印
*
*/
public void reversePrint(){
//创建栈
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head.next;
if (temp == null){
return;
}
while (temp != null){
stack.push(temp);
temp = temp.next;
}
while (stack.size()>0){
System.out.println(stack.pop());
}
}
}
合并两个有序的单链表，合并之后链表依然有序
package com.why.linkedlist;
?
/**
* @Description TODO 双向链表创建，功能和测试类
* @Author why
* @Date 2020/10/19 10:23
* Version 1.0
**/
?
import java.util.List;
?
/**
* 测试类
*/
public class BidirectionalListDemo {
public static void main(String[] args) {
BidirectionalList bl = new BidirectionalList();
ListNode node1 = new ListNode(1,"lrx","123");
ListNode node2 = new ListNode(2,"cjl","123");
ListNode node3 = new ListNode(3,"why","123");
ListNode node4 = new ListNode(3,"wl","123");
?
bl.insert(node1);
bl.insert(node2);
bl.insert(node3);
System.out.println("原数据");
bl.list();
?
System.out.println("修改");
System.out.println();
bl.update(node4);
bl.list();
?
System.out.println("删除");
System.out.println();
bl.delete(3);
bl.list();
}
}
?
/**
* 功能实现类
*/
class BidirectionalList{
?
//建立头节点
ListNode head = new ListNode(0,"","");
?
/**
* 判空
* @return
*/
public boolean isEmpty(){
if (head.next == null){
System.out.println("链表为空");
return true;
}
return false;
}
?
/**
* 从头至尾遍历，显示
* @return
*/
public void list(){
boolean empty = isEmpty();
ListNode temp = head.next;
if (empty == true){
return;
}
while (temp!=null){
System.out.println(temp);