关于链表
链表是有序的列表链表是以节点的方式来存储每个节点包含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()); } } /** * 添加节点 * @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; } 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; } }