一、链表基础

链表是一种常见的数据结构，其中运用到了结构体指针，链表可以实现动态存储分配，换而言之，链表是一个功能强大的数组，可以在某个节点定义多种数据类型，可以实现任意的添加，删除，插入节点等。链表分为两类，一种是有头节点的链表，另一种是无头节点的链表。头节点没有数据域的，其他每个节点都有两部分，一是数据域，二是指针域。下面对单向链表进行详细介绍。
操作包括：链表的创建、修改、删除、插入等。

二、单向链表

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
​链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

三、单向链表结构

1. 存储多个元素，另外一个选择就是使用链表。
2. 链表是以节点的方式存储数据
3. 不同于数组，链表中的元素在内存中不必是连续的空间。
4. 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。

四、单向链表的优点

1. 单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
2. 结点的删除非常方便，不需要像线性结构那样移动剩下的数据
3. 结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

五、单向链表缺点

1. 只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
2. 在进行查询时，搜索一个节点需要遍历链表，在情况不好的情况下可能下需要到链表尾才能找到。
3. 链表需要多维护一个next的域，占据了更多的内存

六、代码实现

1.创建链表节点

/**
 * 链表节点
 */
class SingLeLinkedNode {
    /**
     * 节点编号
     */
    public int no;
    /**
     * 下一个节点
     */
    public SingLeLinkedNode next;
    /**
     * 节点属性名称
     */
    public String name;
    public SingLeLinkedNode(int no, SingLeLinkedNode next, String name) {
        this.no = no;
        this.next = next;
        this.name = name;
    }
    @Override
    public String toString() {
        return "SingLeLinkedNode{" +
                "no=" + no +
                ", next=" + next +
                ", name='" + name + '\'' +
                '}';
    }
}

2.链表实现

/**
 * 单向链表
 */
class SingLeLinkList {
    private final static Logger log = LoggerFactory.getLogger(SingLeLinkList.class);
    /**
     * 链表头部 head -> node -> node- >node
     */
    private final SingLeLinkedNode head = new SingLeLinkedNode(0, "");
    public SingLeLinkedNode getHead() {
        return head;
    }
    /**
     * 添加节点到单项链表
     * 当不考虑编号顺序时
     * 找到当前链表的最后节点
     * 将最后的这个节点的next，指向新的节点
     *
     * @param singLeLinkedNode SingLeLinkedNode
     */
    public void add(SingLeLinkedNode singLeLinkedNode) {
        // 因为head节点不能动，因此我们需要一个辅助变量遍历temp
        SingLeLinkedNode temp = head;
        // 遍历链表，找到最后
        while (temp.next != null) {
            // 找到链表最后
            // 如果没有找到最后，将temp后移
            temp = temp.next;
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 将最后这个接地那的next，指向新的节点
        temp.next = singLeLinkedNode;
    }
    /**
     * 第二种方式在添加节点时，根据排名将节点插入到指定位置
     * 如果有这个排名，则添加失败，并给出提示
     */
    public void addOrder(SingLeLinkedNode singLeLinkedNode) {
        // 因为头节点不能动，因此我们任然通过一个辅助指针（变量）
        // 因为单链表，找的temp是位于添加位置的前一个节点，否则插入不了
        SingLeLinkedNode temp = head;
        // flag标志添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > singLeLinkedNode.no) {
                // 位置找到，就在temp的后面char
                break;
            } else if (temp.next.no == singLeLinkedNode.no) {
                // s明希望添加的SingLeLinkedNode的编号已然存在
                flag = true;
                break;
            }
            // 后移，遍历当前链表
            temp = temp.next;
        }
        // 不能移动，说明编号存在
        if (flag) {
            log.error("准备插入的编号：{}已经存在了，不能加入\n", singLeLinkedNode.no);
        } else {
            // 插入到链表中，temp的后面
            singLeLinkedNode.next = temp.next;
            temp.next = singLeLinkedNode;
        }
    }
    /**
     * 修改节点的信息，根据no标号来修改，即no编号不能改
     *
     * @param newHeroNode SingLeLinkedNode
     */
    public void update(SingLeLinkedNode newHeroNode) {
        if (head.next == null) {
            log.error("链表为空");
            return;
        }
        // 找到需要修改的接地那，根据no标号
        // 定义一个辅助变量
        SingLeLinkedNode temp = head.next;
        // 表示是否知道该节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                // 到链表的尾部
                break;
            }
            if (temp.no == newHeroNode.no) {
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
        } else {
            log.error("没有找到编号为{}的节点，不能被修改\n", newHeroNode.no);
        }
    }
    /**
     * 删除节点
     * head不能动，因此我们需要一个temp辅助节点找到待删除节点前一个节点
     * 说明我们在比较时，是temp.next.no和需要删除的节点的no比较
     */
    public void delete(int no) {
        SingLeLinkedNode temp = head;
        // 标记是否找到待删除节点
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                // 已经找到脸部的最后
                break;
            }
            if (temp.next.no == no) {
                // 找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }
            // temp 后移，遍历
            temp = temp.next;
        }
        // 判断flag
        if (flag) {
            // 可以删除
            temp.next = temp.next.next;
        } else {
            log.error("要删除的{}节点不存在", no);
        }
    }
    /**
     * 显示链表
     */
    public void list() {
        // 判断是否为空
        if (head.next == null) {
            log.error("链表为空");
            return;
        }
        // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
        SingLeLinkedNode temp = head.next;
        while (temp != null) {
            // 判断是否到链表最后
            log.info("{}", temp);
            // 将temp后移，一定小心
            temp = temp.next;
        }
    }
}