单链表的java实现及其常用操作

单链表的实现

单链表介绍 1.链表是以节点的方式来存储,是链式存储 2.每个节点包含 data 域， next 域：指向下一个节点. 3.链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定 单链表的java实现 import java.util.Stack; /** * @author zl * @create 2020--09--03--10:17 */ public class LinkedListDemo { public static void main(String[] args) { HeroNode node = new HeroNode(1, "hahaha"); HeroNode node1 = new HeroNode(2, "heihei"); HeroNode node2 = new HeroNode(3, "youyou"); SingleLinkedList linkedList = new SingleLinkedList(); linkedList.addNode(node); linkedList.addNode(node1); linkedList.addNode(node2); linkedList.showNode(); linkedList.delNode(2); linkedList.showNode(); HeroNode node3 = new HeroNode(3, "youyouxiugai"); linkedList.updateNode(node3); linkedList.showNode(); //倒数第k个node // System.out.println(linkedList.kNode(1)); //反转链表 linkedList.reverseNode(); linkedList.showNode(); linkedList.reverseList(); } } //定义节点 class HeroNode { public int no; public String name; public HeroNode next; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", next=" + next + '}'; } } class SingleLinkedList { //初始化一个头结点，不存放任何数据 HeroNode head = new HeroNode(0, ""); //新增节点 public void addNode(HeroNode heroNode) { HeroNode temp = head;// while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = heroNode; } //删除节点 public void delNode(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 == true) { temp.next = temp.next.next; } else { System.out.println("没有该节点"); } } public void del(HeroNode node) { HeroNode temp = head; boolean flag = false; while (true) { if (temp.next == null) { break; } if (temp.next.no == node.no) { flag = false; break; } temp = temp.next; } if (flag == true) { temp.next = temp.next.next; }else{ System.out.println("没有找到该节点"); } } //修改节点 public void updateNode(HeroNode heroNode) { if (head.next == null) { System.out.println("链表为空"); return; } boolean flag = false; HeroNode temp = head.next; while (true) { if (temp == null) { break; } if (temp.no == heroNode.no) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; } else { System.out.printf("没有找到编号为:%d的用户数据", heroNode.no); } } //查看链表 public void showNode() { HeroNode temp = head.next; while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.next; } } //求单链表有效节点的个数 public int numNode() { HeroNode temp = head.next; if (temp == null) { System.out.println("链表没有数据"); return 0; } int length = 0; while (temp != null) { length++; temp = temp.next; } return length; } //求倒数第k个节点 public HeroNode kNode(int index) { if (head.next == null) { return null; } int size = numNode(); if (size < index || index <= 0) { return null; } HeroNode temp = head.next; for (int i = 0; i < size - index; i++) { temp = temp.next; } return temp; } //单链表的反转 public void reverseNode() { HeroNode newHeroNodeHead = new HeroNode(0, ""); HeroNode cur = head.next; HeroNode temp = null; //如果只有一个节点或者没有节点不用反转 if (cur == null || cur.next == null) { return; } while (cur != null) { // 保存当前节点的下一个节点，方便后面使用 temp = cur.next; //先暂时保存当前的节点，因为后面需要使用 cur.next = newHeroNodeHead.next; newHeroNodeHead.next = cur; cur = temp;//让cur后移 } head.next = newHeroNodeHead.next; } public void reverse(){ HeroNode newNode = new HeroNode(0,""); HeroNode temp = null;//临时节点 HeroNode cur = head.next; if(cur == null && cur.next == null){ return; } while(cur!=null){ temp = cur.next; cur.next = newNode.next; newNode.next = cur; cur = temp; } head.next = newNode.next; } //单链表逆序打印 public void reverseList() { HeroNode temp = head.next; if (temp == null) { System.out.println("链表为空"); return; } Stack<HeroNode> stack = new Stack<HeroNode>(); while (temp != null) { stack.add(temp); temp = temp.next; } while (stack.size() > 0) { System.out.println("反转" + stack.pop()); } } }