Java实现单链表基础操作

Java实现单链表基础操作

关于链表

链表是有序的列表链表是以节点的方式来存储每个节点包含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 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());

}

}

/**

* 添加节点

* @param heroNode

*/

public void add(HeroNode heroNode) {

HeroNode temp = head;

while (true) {

if (temp.next == null) {

break;

}

temp = temp.next;

}

temp.next = heroNode;

}

/**

* 有序添加节点

* @param herNode

*/

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;

}

}

/**

* 更新节点数据

* @param newHeroNode

*/

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 + "的节点，不能修改");

}

}

/**

* 刪除节点

* @param no

*/

public void del(int no) {

HeroNode temp = head;

boolean flag = false;

while (true) {

if (temp.next == null) {

break;

http:// }

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;

}

/**

* 求倒数第index个节点

* @param head 头节点

* @param index 倒数第k个

* @return

*/

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;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。