数据结构之单向链表

单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表，并且是由一个个结点组装起来的，因此又称为结点列表。

图中结构很清晰，一条链表是由多个节点通过指针next指向下一个节点串连而成的，每个节点中都包含了data域和next域，data的域作用是保存数据，next域则是作为指针指向下一个节点的地址，另外还有一个头指针节点head,它表示一个链表头，此节点data域无数据。当指针next=null时，链表终止下一个节点，最终返回的是next=null这个节点到链表头指针head节点长度的单向链表。

案例

下面我想通过一个简单案例来描述一个单向链表的结构及使用方式，这个案例也很简单，输出此案例旨在更好的理解单向链表的数据结构。通过单向链表实现水浒英雄人物增删改查的操作，不做过多的文字赘述，直接上代码，代码中附有更详细的注释。

一、无序添加节点（数据）

首先需要在单链表中定义节点Node，节点中包含data域（存放对象的相关属性数据）和next域（指向下一个Node的指针）；
通过Node创建一个head头，这个head中的data域不需要数据，另外需要定义一个临时辅助指针temp，令temp=head；
对于被添加的（数据）节点node，当temp.next=null，表示终止当前单链表，否则继续指向下一个节点：temp=temp.next;
当退出链表时，拿到最后一个数据：temp.next=node。


 public static void main(String[] args) {
        //创建链表
        AtomSingleLinkedList list = new AtomSingleLinkedList();
        //创建节点
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨", "翻天覆地");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟", "翻江倒海");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星", "风卷残云");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头", "千军万马");
        //打乱顺序的添加节点
        list.add(h3);
        list.add(h1);
        list.add(h4);
        list.add(h2);
        //显示数据
        list.queryList();
     
        /**
        * 打印结果：
        * HeroNode{number=3, name='吴用', nickName='智多星', skill='风卷残云'}
        * HeroNode{number=1, name='宋江', nickName='及时雨', skill='翻天覆地'}
        * HeroNode{number=4, name='林冲', nickName='豹子头', skill='千军万马'}
        * HeroNode{number=2, name='卢俊义', nickName='玉麒麟', skill='翻江倒海'}
        */
 }

 
 class AtomSingleLinkedList {
     //1、先创建一个头节点，头节点不存放数据,头节点不能乱动，否则后面无法查找链表
      private final HeroNode head = new HeroNode(-1, "", "", "");
     
      public void add(HeroNode heroNode) {
         HeroNode temp = head;
          while (temp.next != null) {
            //说明找到链表最后一个节点,退出死循环
            //如果未找到，temp指针的next向后移动
            temp = temp.next;
         }
        //退出循环时，此时的temp指向了链表的最后一个节点
        temp.next = heroNode;
      }
 }
 
 /**
 * 定义一个HeroNode，每一个HeroNode就是一个节点，里面
 * 定义了英雄的属性数据
 */
class HeroNode {
    public int number;
    public String name;
    public String nickName;
    public String skill;
    public HeroNode next;
    
    //其他代码就不去写了。。。
}

二、有序添加节点（数据）

首先需要在单链表中定义Node节点类，节点中包含data域（存放对象的相关属性数据）和next域（指向下一个Node的指针）
通过Node创建一个head头，这个head不许要传参，另外需要定义一个临时辅助指针temp，用来存放head的下一个指向的节点
满足单向链表排序添加数据的条件有以下几点： a、定义一个temp临时指针存放head节点 Node temp=head； b、对于新增的数据（节点）node,当temp.next=0时，则表示链表终止，当前要被添加的数据 node会被移到temp的后面； c、当temp.next.num>node.num时，说明待加入的节点在单链表中找到位置，则有： node.next=temp.next; temp.next=node d、当temp.next.node=node.num时，说明这个位置已经存在了一个一样的的数据，无需添加 e、每次判断循环必须将指针指向下一个节点：temp=temp.next


 public static void main(String[] args) {
        //创建链表
        AtomSingleLinkedList list = new AtomSingleLinkedList();
        //创建节点
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨", "翻天覆地");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟", "翻江倒海");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星", "风卷残云");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头", "千军万马");
        //打乱顺序的添加
        list.addOrderByNum(h3);
        list.addOrderByNum(h1);
        list.addOrderByNum(h4);
        list.addOrderByNum(h2);
     
        //显示数据
        list.queryList();
        /**
        * 打印结果（发现即便是添加时是乱序的，但最终结果都是有序的排列）：
        * HeroNode{number=1, name='宋江', nickName='及时雨', skill='翻天覆地'}
        * HeroNode{number=2, name='卢俊义', nickName='玉麒麟', skill='翻江倒海'}
        * HeroNode{number=3, name='吴用', nickName='智多星', skill='风卷残云'}
        * HeroNode{number=4, name='林冲', nickName='豹子头', skill='千军万马'}
        */
 }

 /**
 *有序添加数据
 */
public void addOrderByNum(HeroNode heroNode) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
               //没有数据，直接添加到head后
                heroNode.next = null;
                temp.next = heroNode;
                break;
            }
               //说明要插入链表中的位置找到
            if (temp.next.number > heroNode.number) {
                //先将heroNode的指针指向heroNode后面一个元素
                heroNode.next = temp.next;
                //然年后heroNode前面一个元素的指针指向heroNode
                temp.next = heroNode;
                break;
            } else if (temp.next.number == heroNode.number) {
                System.out.print("当前水浒人物" + heroNode.name + "已存在，无法再加入序列\n");
                break;
            }
            //指针下移
            temp = temp.next;
        }

三、根据序列号删除节点

同样需要一个临时指针temp(Node temp=head),当temp.next=null时，则说明链表中无可删除节点；
当temp.next.num=num（需要删除的节点序号）时，此时令temp的指针指向下下个节点，即：temp.next=temp.next.next;这时直接跳过序号为num的节点来达到删除节点的目的，有人会问，没有被指向的那个num序号节点（被删除的这个节点）不会占内存吗？不会，因为没有被指针next指向的节点是不可达对象（非GC Root对象）,最终会被GC回收！
每做一个判断指针next必须下移：temp=temp.next。

 public static void main(String[] args) {
        //创建链表
        AtomSingleLinkedList list = new AtomSingleLinkedList();
        //创建节点
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨", "翻天覆地");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟", "翻江倒海");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星", "风卷残云");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头", "千军万马");
        //打乱顺序的添加
        list.addOrderByNum(h3);
        list.addOrderByNum(h1);
        list.addOrderByNum(h4);
        list.addOrderByNum(h2);
        //删除序号为2的节点
        list.deleteByNum(2);
     
        //显示数据
        list.queryList();
        /**
        * 打印结果（序号为2的英雄被删除）：
        * HeroNode{number=1, name='宋江', nickName='及时雨', skill='翻天覆地'}
        * HeroNode{number=3, name='吴用', nickName='智多星', skill='风卷残云'}
        * HeroNode{number=4, name='林冲', nickName='豹子头', skill='千军万马'}
        */
 }


  /**
  * 根据序号删除节点
  */
public void deleteByNum(int num) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                System.out.printf("编号--%d的数据不存在，无法为您删除数据~",num);
                break;
            }
            if (temp.next.number == num) {
                temp.next = temp.next.next;
                System.out.println(temp + "  删除成功！！\n\n");
                break;
            }
            temp = temp.next;
        }
    }

四、修改数据

首先需要一个临时指针temp，令temp=head，当temp.next=null时，说明链表中没有数据，退出修改；
对于传入的修改数据node,这里需要注意的是数据是根据序列号num来做修改的，当temp.next.num=node.num时，对temp.next中的数据进行修改，将node的数据赋值给temp.next中（序列号除外）；
指针要下移，保证遍历可以正常进行，否则会出现死循环：temp=temp.next。

 public static void main(String[] args) {
        //创建链表
        AtomSingleLinkedList list = new AtomSingleLinkedList();
        //创建节点
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨", "翻天覆地");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟", "翻江倒海");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星", "风卷残云");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头", "千军万马");
        //打乱顺序的添加
        list.addOrderByNum(h3);
        list.addOrderByNum(h1);
        list.addOrderByNum(h4);
        list.addOrderByNum(h2);
        //删除序号为2的节点
        list.updateNode(new HeroNode(2, "小卢", "玉麒麟！！", "天崩地裂") );
     
        //显示数据
        list.queryList();
        /**
        * 打印结果（序号为2的英雄被修改）：
        * HeroNode{number=1, name='宋江', nickName='及时雨', skill='翻天覆地'}
        * HeroNode{number=2, name='小卢', nickName='玉麒麟！！', skill='天崩地裂'}
        * HeroNode{number=3, name='吴用', nickName='智多星', skill='风卷残云'}
        * HeroNode{number=4, name='林冲', nickName='豹子头', skill='千军万马'}
        */
 }

 /**
 *修改数据
 */
public void updateNode(HeroNode updateNode) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                System.out.printf("没有找到编号: %d\n", updateNode.number);
                break;
            }
            if (temp.next.number == updateNode.number) {
                //把需要修改的节点 temp.next的数据替换成updateNode的数据
                temp.next.name = updateNode.name;
                temp.next.nickName = updateNode.nickName;
                temp.next.skill = updateNode.skill;
                break;
            }
            //指针下移
            temp = temp.next;
        }
    }

五、查询数据

同样需要一个临时变量temp,令temp=head.next，当temp=null时，终止链表，则表示无数据；
当temp!=null时，在死循环中遍历temp,取出temp的值，指针要下移：temp=temp.next;当遍历到temp=null时退出死循环。


public static void main(String[] args) {
        //创建链表
        AtomSingleLinkedList list = new AtomSingleLinkedList();
        //创建节点
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨", "翻天覆地");
        HeroNode h2 = new HeroNode(2, "卢俊义", "玉麒麟", "翻江倒海");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星", "风卷残云");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头", "千军万马");
        //打乱顺序的添加
        list.addOrderByNum(h3);
        list.addOrderByNum(h1);
        list.addOrderByNum(h4);
        list.addOrderByNum(h2);
     
        //显示数据
        list.queryList();
        /**
        * 打印结果：
        * HeroNode{number=1, name='宋江', nickName='及时雨', skill='翻天覆地'}
        * HeroNode{number=2, name='卢俊义', nickName='玉麒麟', skill='翻江倒海'}
        * HeroNode{number=3, name='吴用', nickName='智多星', skill='风卷残云'}
        * HeroNode{number=4, name='林冲', nickName='豹子头', skill='千军万马'}
        */
 }



/**
 * 显示链表中的数据
 */
public void queryList() {
    //因为head不可动
    HeroNode temp = head.next;

    if (temp == null) {
        System.out.println("当前链表为空，没数据可显示~~");
        return;
    }
   
    while (temp != null) {
        //当temp指针指向null,则代表是最后一个节点，退出当前死循环
        System.out.println(temp);
        //temp指针一定要后移，否则一直会处于死循环中
        temp = temp.next;
    }
}