单链表

特点

  • 单链表是一种有序的数据结构
  • 除头结点外每个节点都有前驱节点
  • 除尾节点外每个节点都有后继节点
  • 头结点的数据域为空的话就是一个空链表
  • 如果要查找某个元素则只能从头顺序查找

    代码实现

    ```java import javax.sound.midi.Soundbank; import java.sql.SQLOutput;

/**

  • @author laoduan
  • @create 2020-04-08-16:22 */ public class SingleLinkedListDemo { public static void main(String[] args) {
  1.     HeroNode hero1 = new HeroNode(1, "贾克斯", "武器大师");
  2.     HeroNode hero2 = new HeroNode(2, "李青", "盲僧");
  3.     HeroNode hero3 = new HeroNode(3, "凯瑟琳", "皮城女警");
  4.     HeroNode hero4 = new HeroNode(4, "提莫", "迅捷斥候");
  6.     SingleLinkedList singleLinkedList = new SingleLinkedList();

// singleLinkedList.add(hero1); // singleLinkedList.add(hero4); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); singleLinkedList.orderadd(hero1); singleLinkedList.orderadd(hero4); singleLinkedList.orderadd(hero2); singleLinkedList.orderadd(hero3); // // singleLinkedList.list(); // System.out.println(); // System.out.println(); // System.out.println(); // // HeroNode hero22 = new HeroNode(2, “瞎子”, “4396”); // singleLinkedList.update(hero22); // singleLinkedList.list();

  1.     System.out.println("----------------倒序后的链表----------------");
  2.     singleLinkedList.reverse(singleLinkedList.getHead());
  3.     singleLinkedList.list();

// // // singleLinkedList.dele(hero3); // singleLinkedList.dele(hero2); // singleLinkedList.dele(hero1); // singleLinkedList.dele(hero4); // System.out.println(“删除后的链表”); // singleLinkedList.list();

  1.     //System.out.println("倒数第k个结点");

// singleLinkedList.list(); // singleLinkedList.count(singleLinkedList.getHead()); // singleLinkedList.revek(singleLinkedList.getlength(singleLinkedList.getHead()),2);

  1. }

}

//定义singlelinkedList管理英雄 class SingleLinkedList{ private HeroNode head = new HeroNode(0,””,””);

  1. public HeroNode getHead() {
  2.     return head;
  3. }
  5. //添加
  6. public void add(HeroNode heroNode){
  7.     HeroNode temp = head;
  8.     //遍历链表，找到最后
  9.     while (true){
  10.         if(temp.next==null){
  11.             break;
  12.         }else {
  13.             //如果没有找到，就后移
  14.             temp=temp.next;
  15.         }
  16.     }
  17.     temp.next=heroNode;
  18. }
  21. //顺序添加
  22. public void orderadd(HeroNode heroNode){
  23.     HeroNode temp=head;
  24.     boolean flag=false;
  25.     while (true){
  26.         if (temp.next==null){
  27.             break;
  28.         }if(temp.next.no>heroNode.no){//找到要添加的位置了
  30.             break;
  31.         }else if(heroNode.no==temp.next.no){
  32.             flag=true;
  33.             System.out.println("要插入的元素已经存在");
  34.             break;
  35.         }
  36.         temp=temp.next;
  37.     }
  38.     if(flag){
  39.         System.out.printf("待插入的英雄 %d 已经存在，不能添加\n",heroNode.no);
  40.     }else{
  41.         heroNode.next=temp.next;
  42.         temp.next=heroNode;
  43.     }
  45. }
  47. //修改
  48. public void update(HeroNode heroNode){
  49.     if (head.next==null){
  50.         System.out.println("链表为空");
  51.     }
  52.     HeroNode temp = head;
  53.     boolean flag = false;
  54.     while (true){
  55.         if(temp.next.no==heroNode.no){
  56.             flag=true;
  57.             break;
  58.         }if(temp.next==null){
  59.             System.out.println("链表中没有你要找的结点");
  60.             break;
  61.         }
  62.         temp=temp.next;
  63.     }
  64.     if(flag){
  65.         temp.next.nickname=heroNode.nickname;
  66.         temp.next.name=heroNode.name;
  67.     }
  68. }
  69. //删除
  70. public void dele(HeroNode heroNode){
  71.     if(head==null){
  72.         System.out.println("链表为空");
  73.     }
  74.     HeroNode temp = head;
  76.     while (true){
  77.         if(temp==null){
  78.             System.out.println("链表中没有你要删的结点");
  79.             break;
  80.         }if(temp.next.no==heroNode.no){
  81.             temp.next=temp.next.next;
  82.             break;
  83.         }
  84.         temp=temp.next;
  85.     }
  86. }
  88. //求单链表结点个数
  89. public int count(HeroNode head){
  90.     HeroNode temp = head.next;
  91.     int count=0;
  92.     if(head==null){
  93.         System.out.println("链表长度为0");
  94.     }
  95.     while (true){
  96.         if(temp==null){
  97.             System.out.printf("链表的长度为%d",count);
  98.             break;
  99.         }
  100.         count++;
  101.         temp=temp.next;
  102.     }
  103.     return count;
  104. }
  106. //翻转单链表
  107. public void reverse(HeroNode head){
  108.     if(head==null){
  109.         System.out.println("链表为空");
  110.     }
  111.     HeroNode temp = head.next;
  112.     HeroNode next = null;
  113.     HeroNode reversehead = new HeroNode(0,"","");
  114.     while (temp!=null){
  115.         next=temp.next;
  116.         temp.next=reversehead.next;
  117.         reversehead.next=temp;
  118.         temp=next;
  120.     }
  121.     head.next=reversehead.next;
  122. }
  123. //获取长度
  124. public int getlength(HeroNode head){
  125.     int count=0;
  126.     if(head.next==null){
  127.         System.out.println("链表为空");
  128.     }
  129.     HeroNode temp = head;
  131.     while (true) {
  132.         if (temp.next == null) {
  133.             break;
  134.         }
  135.         temp = temp.next;
  136.         count += 1;
  137.     }
  138.     return count;
  139. }
  140. //倒数第k个结点
  141. public void revek(int length,int k){
  142.     HeroNode temp =head;
  143.     for(int l=0;l<=length-k;l++){
  144.         temp=temp.next;
  145.     }
  146.     System.out.printf("倒数第%d个结点是"+temp,k);
  147. }
  151. //显示
  152. public void list(){
  153.     if(head.next==null){
  154.         System.out.println("链表为空");
  155.         return;
  156.     }
  157.     //头结点不能动，创建一个temp
  158.     HeroNode temp=head.next;
  159.     while (true){
  160.         if(temp==null){
  161.             break;
  162.         }
  163.         System.out.println(temp);
  164.         //将temp后移
  165.         temp=temp.next;
  166.     }
  167. }

}

class HeroNode{ public int no; public String name; public String nickname; public HeroNode next;

  1. //构造器
  2. public HeroNode(int hNo,String hName,String hNickname){
  3.     this.no=hNo;
  4.     this.name=hName;
  5.     this.nickname=hNickname;
  6. }
  8. //重写toString
  9. @Override
  10. public String toString() {
  11.     return "HeroNode{" +
  12.             "no=" + no +
  13.             ", name='" + name + '\'' +
  14.             ", nickname='" + nickname + '\'' +
  15.             '}';
  16. }

} ```