单链表数据格式 : 数据 +指针 指针是指向下一个元素的 地址
增加(在最后节点增加):直接遍历
增加(根据 节点序号 去添加,有序[升序]):遍历 找到 插入位置的上节点 因为需要用到上节点的指针域 temp.next.getno()> heroNode.getno() [ parameter ] 从而找到了 上节点 修改上节点的下指针与参数节点的下指针域就行了
删: 遍历 找到与 parameterNode no匹配的即可 也是需要找到上节点 修改指针
改:遍历 找到parameterNode no 匹配 直接修改
查:逆向查询 需要 知道当前节点长度 指针后移次数(cur.length - lastIndex)
反转 :思路1:
借助辅助节点 每次 都将被反转链表的下一个节点 放入辅助节点的 第一位
核心:两个辅助节点 一个装 被反转链表下一个(不然会断) 一个是辅助头节点
最后将被反转链表指向 辅助节点的下一个节点 完成反转
思路2:栈
栈:stack add入栈 pop出栈
package com.qf.linkedlistdemo;
//单向链表
import java.util.Stack;
public class SingleLinkedList {
//初始化头节点 ,不存放数据, 成员变量都有默认初始化值
static final HeroNode head = new HeroNode(0, "", "");
public void addNode(HeroNode heroNode) {
//辅助节点
HeroNode temp = head;
//遍历链表
while (true) {
//遍历到最后
if (temp.getNext() == null) {
break;
}
//如果没有 遍历到最后 temp 后移
temp = temp.getNext();
}
//退出while 节点已经是最后一个了 添加
temp.setNext(heroNode);
}
public void addNodeByOrder(HeroNode heroNode) {
//因为头节点不能动 所以 需要 一个辅助节点 来帮助 找到添加的位置
//并且 因为是单链表 加入节点 所以
// 必须 要找到 添加位置 的前一个节点 不然没法加入 因为需要指针
HeroNode temp = head;
boolean flag = false; //编号是否存在 默认不存在
//遍历链表
while (true) {
//遍历到最后一个 ,说明要插入的地方 在最后一个
if (temp.getNext() == null) {
break;
}
// 找到要插入的位置 temp 不能 与 前面的一个比较 要跟后面的比较 这样才能找到 temp(插入位置的前一个介节点)
//后面的节点 肯定 要比插入的节点大
if (temp.getNext().getNo() > heroNode.getNo()) {
break;
}
if (temp.getNext().getNo() == heroNode.getNo()) {
//改变flag 值
flag = true;
break;
}
//后移
temp = temp.getNext();
}
//证明 已经遍历完毕 判断 flag 是否改变
if (flag) { //存在
System.out.println("节点已存在");
} else {
//修改 next 指向
heroNode.setNext(temp.getNext());
temp.setNext(heroNode);
}
}
public void updateByNodeNO(HeroNode heroNode) {
if (head.getNext() == null) {
System.out.println("空链表");
//表示当前链表为空 直接返回即可
return;
}
//借助 辅助 变量
HeroNode temp = head.getNext();
// 定义表示 是否找到 后续需要根据 其进行修改
boolean flag = false;
//变量 当前 链表
while (true) {
//表示最后一个元素
if (temp == null) {
break; //遍历完
}
//表示找到了
if (temp.getNo() == heroNode.getNo()) {
flag = true;
break;
}
//后移
temp = temp.getNext();
}
//根据 flag 去判断是否找到
if (flag) { //找到了
temp.setName(heroNode.getName());
temp.setNickName(heroNode.getNickName());
} else {
System.out.println("未找到 你所指定的节点" + heroNode.getNo());
}
}
public void deleteByNodeNo(int no) {
//空链表
if (head.getNext() == null) {
System.out.println("这是一个空链表");
return;
}
//声明辅助变量 ,头节点 可以忽略
HeroNode temp = head.getNext();
boolean flag = false;
while (true) {
if (temp == null) {
break;//表示到最后一个
}
if (temp.getNext().getNo() == no) {
//表示找到 该节点的 上一个节点
flag = true;
break;
}
//后移
temp = temp.getNext();
}
//判断 true 就是 找到了该节点的上一个节点
if (flag) {
//修改节点指向
temp.setNext(temp.getNext().getNext());
} else {
System.out.println("未找到要删除的 节点" + no);
}
}
public void showSingleLinkedList() {
//判断链表是否为空
if (head.getNext() == null) {
System.out.println("链表为空");
return;
}
//遍历 借助 辅助接点 节点就不遍历了
HeroNode temp = head.getNext();
while (true) {
//说明到最后了 ,不用next 如果用了 下一个节点 为空的话 就会产生最后一个数据 不能正常打印
//主要是 当前链表也需要做操作 所以使用temp
if (temp == null) {
break;
}
//不是最后一个节点
System.out.println(temp);
//后移
temp = temp.getNext();
}
}
public static int getLength() {
//链表为空
if (head.getNext() == null) {
return 0;
}
//声明变量
int length = 0;
//借助辅助变量 去遍历
HeroNode cur = head.getNext();
while (cur != null) {
length++;
cur = cur.getNext();
}
return length;
}
public static HeroNode findHeroNodeByLastIndex(int lastIndex) {
//判断 当前链表是否为空
if (head.getNext() == null) {
return null;
}
//检验输入数据是否合法
if (lastIndex < 0 || lastIndex > getLength()) {
throw new RuntimeException("输入数据不合法");
}
//当前指针指向第一个元素
HeroNode cur = head.getNext();
//四个数 倒数 第二个 指针需要移动 2 次 类推
for (int i = 0; i < getLength() - lastIndex; i++) {
cur = cur.getNext();
}
return cur;
}
public void reverseCurrentHeroNode() {
//判断是否为空 或者当前链表只有一个单个数据
if (head.getNext() == null || head.getNext().getNext() == null) {
return;
}
//定义辅助变量
HeroNode cur = head.getNext();//第一个元素
HeroNode next;
//定义反转 单链表的头节点
HeroNode reverseHead = new HeroNode(0, "", "");
// 遍历原来的链表 每遍历一个 放在新链表的最前端
while (cur != null) {
next = cur.getNext();//保存当前节点的下一个元素 因为后面要用 不然找不到了
cur.setNext(reverseHead.getNext());//将 当前元素的下一个 元素 指向新 链表的头
reverseHead.setNext(cur); //把当前已经拿到的对象 放在 新的单链表的首部
cur = next;//后移 (之前保存的 下一个元素直接赋值 )
}
head.setNext(reverseHead.getNext());
}
public void reverseCurrentPrintHeroNode(HeroNode headNode) {
//判断是否为空
if (headNode.getNext() == null) {
return;//为空
}
//不为空
//声明空间
Stack heroNodeStack = new Stack<>();
HeroNode cur = headNode.getNext();
while (cur != null) {
//压栈
heroNodeStack.add(cur);
cur = cur.getNext();
}
//出栈
while (heroNodeStack.size() > 0) {
//出栈
System.out.println(heroNodeStack.pop());
}
}
}



