单链表的介绍

线性表的链式存储又称单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表结构如下所示，其中data为数据域，存放数据元素，next为指针域，存放其后继结点的地址。

由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的数据结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

链表分带头结点的链表和没有头结点的链表，根据实际的需求来确定。通常用头指针来标识一个单链表，如单链表L，头指针为null时表示一个空表。此外，为了操作方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不存放任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

头指针和头结点的区分

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点的好处

• 由于第一个数据结点的位置被存放在头结点的指针域中，所以链表的第一个位置上的操作和在表的其他位置上的操作一致，无需进行特殊处理。
• 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表的实现思路

单链表的创建

• 先创建一个head 结点，作用就是表示单链表的头部
• 后面我们每添加一个结点，就直接加入到链表的最后（尾插法）

单链表的遍历

• 由于头指针不能动，需要通过一个辅助指针帮助遍历整个链表。

插入新节点

• ① 首先找到新添加的结点位置，是通过辅助指针，通过遍历来实现
• ② 新的结点.next = tmp.next
• ③ 将tmp.next指向新的结点

修改结点

• ① 先通过遍历找到该结点
• ② tmp.name = node.name
  tmp.nickname = node.nickname

删除节点

• ① 我们先找到需要删除的这个结点的前一个结点 tmp
• ② tmp.next = tmp.next.next
• ③ 被删除的结点，将不会有其他引用指向，会被垃圾回收机制回收。

代码实现

package cn.kuetr.linkedlist;

public class SingleLinkedListTest {
    public static void main(String[] args) {
    //测试
        //先创建结点
        LinkNode hero1 = new LinkNode(1, "宋江", "及时雨");
        LinkNode hero2 = new LinkNode(2, "卢俊义", "玉麒麟");
        LinkNode hero3 = new LinkNode(3, "吴用", "智多星");
        LinkNode hero4 = new LinkNode(4, "林冲", "豹子头");
        
        //创建链表
        SingleLinkedList l = new SingleLinkedList();
        l.insert(hero1);
        l.insert(hero4);
        l.insert(hero2);
        l.insert(hero3);
        l.list();
        
        //测试修改结点
        LinkNode info = new LinkNode(2, "小卢", "小尾巴");
        l.modify(info);
        
        //显示链表
        l.list();
        
        //删除一个节点
        l.delete(1);
        l.delete(4);
        l.delete(2);
        l.delete(3);
        
        //显示链表
        l.list();
        
    }
}

//定义一个SingleLinkedList来管理结点
class SingleLinkedList {
    // 先初始化一个头结点，头结点不要动，也不存放具体数据
    private LinkNode head = new LinkNode(0, "", "");

    // 添加结点到单向链表
    /*
     * 思路，当不考虑编号顺序时， 1.找到当前链表的最后结点 2.将最后这个结点指向新结点。
     */
    public void addNode(LinkNode node) {
        // 因为head结点不能动，因此需要一个辅助指针
        LinkNode tmp = head;
        // 遍历链表，找到最后
        while (true) {
            // 如果tmp.next == null 说明tmp是尾节点
            if (tmp.next == null) {
                break;
            } else {
                tmp = tmp.next; // 如果没有找到，就把指针后移
            }
        }
        // 当退出while循环时，tmp指向链表的最后，此时链接上即可
        tmp.next = node;
    }
    
    //在链表中插入结点：
    public void insert(LinkNode node) {
        //由于头指针不能动，因此必须要通过辅助指针来帮助找到添加的位置
        //因为是单链表，因此我们找的tmp是位于添加位置的前一个结点，否则无法插入
        LinkNode tmp = head;
        boolean flag = false;  //标识添加的编号是否存在，默认为false
        while(true) {
            if(tmp.next == null) { //说明tmp已经在链表的最后
                break;
            }
            if(tmp.next.id > node.id) { //找到位置，在tmp的后面插入
                break;
            }else if(tmp.next.id == node.id) {
                flag = true; //说明编号存在
                break;
            }
            tmp = tmp.next; //后移，遍历当前链表
        }
        //判断flag的值，是否进行添加
        if(flag) { //不能添加，因为编号存在
            System.out.printf("由于编号%s存在，不能完成添加操作！\n",node.id);
        }else {
            //插入到链表中
            node.next = tmp.next;
            tmp.next = node;
        }
    }

    //删除结点
    //思路：
    //1.因为head结点不能动，因此需要tmp辅助结点，找到待删除结点的前一个结点。
    //2.我们在比较时，是tmp.next.id和需要删除的结点的id比较
    public void delete(int id) {
        LinkNode tmp = head;
        boolean flag = false; //标识是否找到待删除结点
        while(true) {
            if(tmp.next == null) {
                break;
            }
            if(tmp.next.id == id) {
                //找到了待删除结点的前一个结点
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag) { //找到结点
            //此时可以删除
            tmp.next = tmp.next.next;
        }else {
            System.out.println("要删除的结点不存在");
        }
    }
    //修改结点的信息，根据编号来修改，即id不能改
    //1.根据node的id来进行修改
    public void modify(LinkNode node) {
        //判断是否为空
        if(head.next == null) {
            System.out.println("链表为空。");
            return;
        }
        //找到需要修改的结点：
        //先定义一个辅助变量
        LinkNode tmp = head.next;
        boolean flag = false; //表示是否找到该结点
        while(true) {
            if(tmp.next == null) {
                break; //已经到了链表的最后，已经遍历完链表
            }
            if(tmp.id == node.id) {
                //找到 
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        //根据flag是否找到要修改的结点
        if(flag) {
            tmp.name = node.name;
            tmp.nickname = node.nickname;
        }else {
            System.out.println("没有找到要修改的结点，请检查传入参数是否正确！");
        }
    }
    
    
    // 显示链表[遍历]
    public void list() {
        // 先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头结点不能动，因此需要辅助指针来帮助遍历
        LinkNode tmp = head.next;
        while (true) {
            //判断是否
            if (tmp == null) {
                break;
            }
            //输出结点信息
            System.out.println(tmp);
            //将tmp后移，必须要注意
            tmp = tmp.next;
        }
    }
}

//定义一个LinkNode，每个LinkNode就是一个结点
class LinkNode {
    public int id;
    public String name;
    public String nickname;
    public LinkNode next; // 指向下一个结点

    public LinkNode(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;
    }

    // 为了显示方便，我们重写toString方法
    @Override
    public String toString() {
        return "HeroNode [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
    }

}