链表的理解

小结

1. 链表是以节点的方式来储存的
2. 每个节点包括 data域：存放数据，next域：指向下一个节点
3. 如图：发现链表的各个节点不一定是连续储存的
4. 链表分为带头节点的链表和没有头结点的链表，这样根据实际需求而定。

单向链表

添加

添加到最后

1. 找到链表的最后一个节点[通过节点的next == null]

2. 将最后这个节点的next指向新的节点

   //初始化一个头结点,里面什么都不放
   HeroNode head = new HeroNode(0, "", "");

   /**
    * 向链表中添加一个节点
    * 不考虑编号顺序
    */
   public void add(HeroNode heroNode) {
       //因为头节点是不能动的，使用中间变量temp来保存头节点
       HeroNode temp = head;
       //遍历节点，找到最后一个节点【通过最后一个节点next指向为 null】
       while (true) {
           if (temp.next == null) {
               //找到最后一个节点
               break;
           }
           //没有找到就将temp后移一个
           temp = temp.next;
       }
       // 当循环退出的时候temp就指向节点的最后一个
       temp.next = heroNode;
   }

考虑编号顺序添加

1. 找到新添加节点的位置，通过辅助变量(temp)[遍历找到新节点的位置]

2. 新的节点.next = temp.next

3. temp.next = 新的节点

   /**
   * 考虑排序编号添加
   *
   * @param heroNode
   */
   public void addByOrder(HeroNode heroNode) {
   //因为头节点是不能动的,使用辅助变量temp寻找位置
   HeroNode temp = head;

       //用来代表当前添加的节点的编号是否存在，默认false不存在
       boolean flag = false;
   while (true) {
       if (temp.next == null) {
           //当前temp为链表最后一个
           break;
       }
       if (temp.next.no > heroNode.no) {
           //找到需要添加的位置，就在temp后面添加
           break;
       } else if (temp.next.no == heroNode.no) {
           //需要添加的节点已经存在
           flag = true;
           break;
       }
       //三个条件不成立  temp后移
       temp = temp.next;
   }
   if (flag) {
       //不能添加，编号存在
       System.out.printf("当前添加的英雄编号 %d 已经存在， 不能添加\n", heroNode.no);
   } else {
       //在temp后面进行添加
       heroNode.next = temp.next;
       temp.next = heroNode;
   }
   }

修改

• 使用temp.no == newHeroNode.no判断是否为需要修改的节点

  /**
  * 更新节点
  *
  * @param newHeroNode
  */
  public void update(HeroNode newHeroNode) {
  if (head.next == null) {
  System.out.println("当前链表为空");
  return;
  }
  //因为头节点是不能动的，使用中间变量temp来保存头节点
  HeroNode temp = head;
  boolean flag = false; //用来表示链表中是否存在需要修改的节点
  while (true) {
  if (temp.next == null) {
  break;
  }
  if (temp.no == newHeroNode.no) {
  flag = true;
  break;
  }
  temp = temp.next; //temp后移
  }
  if (flag) {
  temp.name = newHeroNode.name;
  temp.nickName = newHeroNode.nickName;
  } else {
  System.out.printf("没有找到编号为：%d 节点", newHeroNode.no);
  }
  }

删除

1. 找到需要删除的节点的前一个节点temp

2. temp.next = temp.next.next

3. 被删除的节点 将不会有其他引用指向，会被垃圾回收机制回收

   /**
   * 删除节点
   *
   * @param no
   */
   public void del(int no) {
   if (head.next == null) {
   System.out.println("当前链表为空");
   return;
   }
   //因为头节点是不能动的，使用中间变量temp来保存头节点
   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;
   } else {
       System.out.printf("不存在编号为 %d 的节点  删除失败\n", no);
   }
   }

dataStructures: gitee

dataStructures: github