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<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;

}

}

来源：https://blog.csdn.net/weixin_44107140/article/details/122831673