单链表
一、链表介绍
二、单链表介绍
三、单链表应用实例
1、插入数据，插入单链表尾部案例
package com.achang.linkedlist;
/**
* @Author Achang
* @Date 2022/3/8 21:26
* 单链表
**/
public class SingleLinkedListDemo {
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 singleLinkedList = new SingleLinkedList();
singleLinkedList.add(node1);
singleLinkedList.add(node2);
singleLinkedList.add(node3);
singleLinkedList.add(node4);
singleLinkedList.list();
}
}
class SingleLinkedList{
//初始化有节点，不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
public void add(HeroNode node){
HeroNode temp = head;
while (true){
//找到链表最后
if (temp.next == null){
break;
}else {
temp = temp.next;
}
}
temp.next = node;
}
public void list(){
if (head.next == null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (true){
//判断是否是链表的最后
if (temp==null){
break;
}
//输出节点信息
System.out.println(temp);
//next后移
temp = temp.next;
}
}
}
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next;
@Override
public String toString() {
return "no="+no+",name="+name+",nickName="+nickName;
}
public HeroNode(int no, String name, String nickName){
this.name=name;
this.nickName = nickName;
this.no = no;
}
}
二、根据Node序号，插入指定链表位置案例
如果存在就添加失败，并给出提示
class SingleLinkedList{
//初始化有节点，不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
//第二种添加方式，根据排名插入到指定位置（如果存在就添加失败，并给出提示）
public void addByNo(HeroNode node){
//因为头节点不能动，因为我们使用辅助指针，来帮助找到添加的位置
HeroNode temp = this.head;
boolean flag = false;//标志添加的编号是否存在，默认为false
while (true){
//说明在链表的最后
if (temp.next==null){
break;
}
//位置找到，就在temp的后面插入
if (temp.next.no > node.no){
break;
}
//说明需要添加的编号已经存在
if (temp.next.no== node.no){
flag = true;//说明编号存在
break;
}
temp = temp.next;//后移，遍历当前链表
}
//判断是否需要添加
if (flag){//说明编号存在，不能添加
System.out.println("准备的插入的Node的No序号已经存在，不能在添加");
}else {
//插入到链表中，temp的后面
node.next = temp.next;
temp.next = node;
}
}
public void list(){
if (head.next == null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (true){
//判断是否是链表的最后
if (temp==null){
break;
}
//输出节点信息
System.out.println(temp);
//next后移
temp = temp.next;
}
}
}
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next;
@Override
public String toString() {
return "no="+no+",name="+name+",nickName="+nickName;
}
public HeroNode(int no, String name, String nickName){
this.name=name;
this.nickName = nickName;
this.no = no;
}
}
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 singleLinkedList = new SingleLinkedList();
singleLinkedList.addByNo(node1);
singleLinkedList.addByNo(node3);
singleLinkedList.addByNo(node2);
singleLinkedList.addByNo(node4);
singleLinkedList.list();
}
三、单向链表的修改
编号不变，名字和昵称可变
//修改节点，根据编号修改，编号不可变
public void update(HeroNode node){
//当前链表为空
if (head.next==null){
System.out.println("当前链表为空");
return;
}
HeroNode temp = head;
boolean flag = false;//表示是否找到该节点
while (true){
if (temp == null){
break;//到了链表的最后
}
//找到了
if (temp.no == node.no){
flag = true;
break;
}
temp = temp.next;//后移，遍历链表
}
if (flag){
temp.nickName = node.nickName;
temp.name = node.name;
}else {
System.out.println("未找到节点");
}
}
四、删除节点
//删除节点
//根据no序号，来删除节点
public void deleteNode(int no){
HeroNode temp = head;
boolean flag = false;
while (true){
if (temp.next == null){
System.out.println("已经到链表的最后");
break;
}
if (temp.next.no ==no){
System.out.println("找到了待删除的前一个节点");
flag = true;
}
temp = temp.next;
}
if (flag){
temp.next = temp.next.next;
}else {
System.out.println("要删除的节点不存在");
}
}
五、获取链表中有效节点个数
//获取到单链表节点的个数，有头节点就不统计头节点
public static int getLength(HeroNode head){
if (head.next == null){
return 0;
}
int length = 0;
HeroNode temp = head.next;//不算头节点
while (temp != null){
length++;
temp = temp.next;//后移遍历
}
return length;
}
六、查找单链表中倒数第k个节点
//查找单链表中倒数第k个节点
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}
int size = getLength(head);
if (index <= 0 || index > size) {
return null;
}
HeroNode temp = head.next;
for (int i=0;i<size-index;i++){
temp = temp.next;
}
return temp;
}
七、单链表的反转
//反转链表
public void reverse(HeroNode head){
//当前链表为空，则无需反转
if (head.next == null || head.next.next == null){
return;
}
HeroNode temp = head.next;
HeroNode next = null;//指向当前节点的下一个节点
HeroNode reverseHead = new HeroNode(0,"","");
while (temp != null){
next = temp.next;
temp.next = reverseHead.next;//将temp的下一个节点指向新链表的最前端
reverseHead.next = temp;//将temp连接到新的链表上
temp = next;
}
head.next = reverseHead.next;
}
八、逆序打印链表
通过栈结构【先进后出】
//逆序打印链表 通过栈结构【先进后出】
public void reversePrint(HeroNode head){
if (head.next == null){
System.out.println("当前为空链表，无法打印");
return;
}
Stack<HeroNode> stack = new Stack<>();
HeroNode temp = head;
while (temp != null){
stack.push(temp.next);
temp = temp.next;
}
while (stack.size()>0){
System.out.println(stack.pop());//逆序弹出
}
}