关于链表
链表是有序的列表链表是以节点的方式来存储每个节点包含data域,next域(指向下一个节点)分带头节点的链表和没有头节点的链表
定义一个节点:
package linkedQueue;
public 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;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
定义一个链表:
实现以下功能:
添加节点
按序添加节点
删除节点
修改节点
遍历节点
反向打印节点
链表反转
统计节点个数
打印倒数第n个节点
程序:
package linkedQueue;
import java.util.Stack;
public class SingleLinkedList {
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
//反向打印节点
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return;
}
// 创建一个栈
Stack<HeroNode> heroNodes = new Stack<>();
HeroNode cur = head.next;
while (cur != null) {
heroNodes.push(cur); //入栈
cur = cur.next;
}
// 出栈打印
while (heroNodes.size() > 0) {
System.out.println(heroNodes.pop());
}
}
public void add(HeroNode heroNode) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}
public void addByOrder(HeroNode herNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > herNode.no) {
break;
} else if (temp.next.no==herNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("你要插入的节点的编号已经存在!!!!");
} else {
herNode.next = temp.next;
temp.next = herNode;
}
}
public void update(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("链表为空!!!!");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.no == newHeroNode.no) {
// 找到
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
} else {
// 没有找到
System.out.println("没有找到编号" + newHeroNode.no + "的节点,不能修改");
}
}
public void del(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;
}
if (flag) {
temp.next = temp.next.next;
}
}
public void showList() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
HeroNode temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
public static int getLength(HeroNode head) {
if (head.next == null) { //空链表
return 0;
}
int length = 0;
HeroNode herNode = head.next;
while (herNode != null) {
length++; // 计数
herNode=herNode.next; // 指针后移
}
return length;
}
public static HeroNode findLastIndexNode(HeroNode head, int index) {
// 判断是否是空链表
if (head.next == null) {
return null;
}
// 拿到链表的长度
int size = getLength(head);
// index校验,看是否在范围内
if (index <= 0 || index > size) {
return null;
}
// 定位倒数第index个节点
HeroNode herNode = head.next;
for (int i = 0; i < size - index; i++) {
herNode = herNode.next;
}
return herNode;
}
//单链表反转
public static void reverseList(HeroNode head) {
// 如果当前链表为空或者只有一个节点,直接返回
if (head.next == null || head.next.next == null) {
return;
}
// 定义辅助变量来遍历链表
HeroNode cur = head.next;
HeroNode next = null;//指向当前节点[cur]的下一个节点
HeroNode reverseHead = new HeroNode(0, "", "");
// 遍历原来节点,每遍历一个节点,将其取出,并放在新的链表的最前端
while (cur != null) {
next = cur.next;//暂时保存当前节点的下一个节点
cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
reverseHead.next=cur;//将cur链接到新的链表
cur = next;
}
head.next = reverseHead.next;
}
}
到此这篇关于Java实现单链表基础操作的文章就介绍到这了,更多相关Java单链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!