单向链表

介绍

链表是有序的列表，它在内存中的存储如下：

小结上图：

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

单链表(带头结点) 逻辑结构示意图如下：

单链表的应用实例

（1）

第一种方法在添加英雄时，直接添加到链表的尾部

思路说明

代码实现

代码实现

public class SingleLinkedListDemo {

  public static void main(String[] args) {
    HeroNode hero1 = new HeroNode(1,"宋江","及时雨");
    HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
    HeroNode hero3 = new HeroNode(3,"吴用","智多星");
    HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

    SingleLinkList singleLinkList = new SingleLinkList();
    singleLinkList.add(hero1);
    singleLinkList.add(hero2);
    singleLinkList.add(hero3);
    singleLinkList.add(hero4);

    singleLinkList.list();
  }

}

class SingleLinkList {

  //先初始化一个头节点，头节点不要动，不存放具体的数据
  private HeroNode head = new HeroNode(0, "", "");

  /*
    添加节点到单项链表
    先不考虑编号的顺序问题

    1。找到当前链表的最后一个节点
    2。将最后这个节点的next 指向 下一个新的节点
   */
  public void add(HeroNode heroNode) {
    //因为head节点不能动，因此我们需要一个辅助变量遍历 temp 帮助遍历
    HeroNode temp = head;

    while (true) {
      if (temp.next == null) {
        break;
      }
      temp = temp.next;
    }
    //退出while循环时，temp就指向了链表的最后
    temp.next = heroNode;
  }

  //显示链表【遍历】
  public void list() {
    //判断链表是否为空
    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;
    }
  }

}

//定义HeroNode，每个HeroNode对象就是一个节点
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 + '\'' +
        '}';
  }
}

说明：

? 以上代码只能将数据添加到链表的最后，不能按照序号来自动的添加。当前链表中的数据的排序是由main方法 add()的顺序决定的。

我实验中的问题

我在实验过程中主要困扰我的问题：

添加数据到链表时为什么temp.next就可以指向下一个节点？类似于C语言中的temp->next。定义节点类HeroNode的时候，没明白为什么next的类型要定义为HeroNode的类型？

解决方法：

我在程序中通过打断点，用debug模式让代码一步一步运行后明白。

例如，main方法中：

HeroNode hero1 = new HeroNode(1,"宋江","及时雨");

SingleLinkList singleLinkList = new SingleLinkList();

singleLinkList.add(hero1);

singleLinkList.list();

创建hero1对象和单链表对象，将hero1对象通过singleLinkList对象中的add()方法添加到链表中。创建单链表对象时，先初始化一个头节点，头节点不要动，不存放具体的数据：

private HeroNode head = new HeroNode(0, "", "");

要将数据插入到链表的最后，需要找到链表最后一个节点，这里用遍历链表来找到最后一个节点（后面可以定义一个尾节点），遍历的话需要一个辅助变量temp来帮助遍历。

public void add(HeroNode heroNode) {
    //因为head节点不能动，因此我们需要一个辅助变量遍历 temp 帮助遍历
    HeroNode temp = head; //将temp指向头节点head，这里的head还是空的，temp.next也是空的

	//用一个死循环来遍历
    while (true) {
      if (temp.next == null) { //这是的temp.next还是头节点中的，为空，true
        break; //然后退出循环
      }
      temp = temp.next;
    }
    
    //退出while循环时，temp就指向了链表的最后
    temp.next = heroNode; 
      //退出循环后，将传入的hero1对象赋给temp.next,hero1对象中有属性，
    	no:1 name:"宋江" nickname:"及时雨"
    	这样temp.next中就不是null了， 而是hero1对象。这里我就明白了定义节点类时，为什么next的类型要定		  义为HeroNode的类型，使用来存储下一个节点的信息的（也不知道这么说对不对）。
  }

用遍历显示链表的时候思路也一样。

（2）

在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)

思路说明

代码实现

  //第二种方式添加英雄时，根据排名将英雄插入到指定位置
  //如果有这个排名，则显示添加英雄失败
  public void addByOrder(HeroNode heroNode) {
    HeroNode temp = head;
    boolean flag = false; //flag标志添加的编号是否存在，否则插入不了
    while (true) {
      if (temp.next == null) {
        break;
      }
      if (temp.next.no > heroNode.no) {
        break;
      } else if (temp.next.no == heroNode.no) {
        flag = true;
        break;
      }
      temp = temp.next;
    }
    if (flag) {
      System.out.printf("准备插入的英雄的编号%d已经存在，不能加入\n", heroNode.no);
    } else {
      heroNode.next = temp.next;
      temp.next = heroNode;
    }
  }