【数据结构与算法】单向链表(添加节点、顺序添加节点、更新节点、删除节点、反转链表、获取链表长度、获取倒数第几个节点、打印链表、反转打印链表)

1. 单向链表的介绍

单向链表是有序的列表。以节点的方式来存储，是链式存储，每个节点包含data域和next域(指向下一个节点)，所以单向链表在内存中的储存是无序的

单向链表分带头节点的单向链表，和没有头节点的单向链表

2. 带head头的单向链表实现

实现对单向链表的增、删、改、查等操作

单向链表各节点说明：

• head节点：不储存数据，next指向下一个节点
• 最后一个节点：next为空，不指向任何节点

单向链表各方法说明：

• add：向单向链表添加一个节点
• addByOrder：按照Node的id升序，将Node添加到指定位置。如果id已存在，则添加失败并给出提示
• update：通过新节点的id，去更新单向链表中对应id的节点的数据
• deleteById：根据id删除单向链表中的节点
• reverseList：将单向链表的各个节点进行反转
• length：获取单向链表的节点个数
• getLastIndexNode：获取单向链表倒数第index个节点
• show：遍历显示链表所有节点的数据
• reversePrint：反向打印链表

单向链表的实现：

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {

        // 先创建节点
        Node node1 = new Node(1, "node1");
        Node node2 = new Node(2, "node2");

        // 创建单向链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 先添加node2，再添加node1
        singleLinkedList.add(node2);
        singleLinkedList.addByOrder(node1);

        // 更新id = 2的节点
        Node newNode2 = new Node(2, "newNode2");
        singleLinkedList.update(newNode2);

        // 删除id = 1的节点
        singleLinkedList.deleteById(1);

        // 打印单向链表的长度
        System.out.println(singleLinkedList.length());

        // 获取倒数第一个节点，并打印
        System.out.println(singleLinkedList.getLastIndexNode(1));

        // 将单向链表进行反转
        singleLinkedList.reverseList();

        // 查看单向链表所有节点数据
        singleLinkedList.show();

        // 反向打印单向链表
        singleLinkedList.reversePrint();

    }
}

class SingleLinkedList {

    // 初始化一个head节点
    private Node headNode = new Node(0, "");

    // 先找到单向链表的最后一个节点(最后一个节点的next为null)，然后将next指向新节点
    public void add(Node node) {
        Node tmpNode = this.headNode;

        while (true) {
            // 如果找到最后一个节点，则添加新节点
            if (tmpNode.next == null) {
                tmpNode.next = node;
                break;
            } else {
                // 如果没有找到最后一个节点，则循环处理后面的节点
                tmpNode = tmpNode.next;
            }
        }
    }


    // 按照Node的id升序，将Node添加到指定位置。如果id已存在，则添加失败并给出提示
    public void addByOrder(Node node) {
        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则直接将新节点添加到单向链表的后面
            if (tmpNode.next == null) {
                tmpNode.next = node;
                break;
                // 如果下一个节点的id比新节点的id大，则将新节点添加到当前节点的后面
            } else if (tmpNode.next.id > node.id) {
                node.next = tmpNode.next;
                tmpNode.next = node;
                break;
                // 如果下一个节点的id和新节点的id相等，则不能添加
            } else if (tmpNode.next.id == node.id) {
                System.out.printf("准备添加的节点的id：%d已经在单向链表中存在，不能添加\n", node.id);
                break;
                // 否则，循环处理下一个节点
            } else {
                tmpNode = tmpNode.next;
            }
        }

    }


    // 通过新节点的id，去更新单向链表中对应id的节点的数据
    public void update(Node node) {

        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示未找到，不能更新
            if (tmpNode.next == null) {
                System.out.println("单向链表没有该节点的id，不能更新");
                break;
                // 如果找到了，则进行更新
            } else if (tmpNode.next.id == node.id) {
                tmpNode.next.name = node.name;
                break;
                // 否则，循环处理下一个节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 根据id删除单向链表中的节点
    public void deleteById(int id) {
        Node tmpNode = this.headNode;
        while (true) {
            // 如果没有下一个节点，则表示为找到要删除的节点
            if (tmpNode.next == null) {
                System.out.println("未找到要删除的节点");
                break;
                // 如果找到要删除的节点，则进行删除
            } else if (tmpNode.next.id == id) {
                //被删除的节点没有被引用，会被自动垃圾回收
                tmpNode.next = tmpNode.next.next;
                break;
                // 否则，循环处理后面的节点
            } else {
                tmpNode = tmpNode.next;
            }
        }
    }

    // 将单向链表的各个节点进行反转
    public void reverseList() {
        // 当前处理节点
        Node currentNode = this.headNode.next;
        // 当前处理节点的下一个节点
        Node tmpNextNode;
        // 创建一个临时的反转单向链表的头
        Node tmpReverseHead = new Node(0, "");

        while (true) {
            // 如果当前节点为null，则表示反转结束
            if (currentNode == null) {
                // 反转结束，将临时的反转单向链表的头的next，赋值给单向链表的头的next
                this.headNode.next = tmpReverseHead.next;
                break;
                // 否则，从单向链表中依次取出节点，插入到临时的反转单向链表的头后面
            } else {
                // 将当前节点的下一个节点，赋值给临时的tmpNextNode
                tmpNextNode = currentNode.next;
                // 将反转单向链表的头的后面部分，放到当前节点的后面
                currentNode.next = tmpReverseHead.next;
                // 然后再将当前节点，放到反转单向链表的头的后面
                tmpReverseHead.next = currentNode;
                // 将临时的的tmpNextNode，赋值给当前节点，循环处理后面的节点
                currentNode = tmpNextNode;
            }
        }

    }


    // 获取单向链表的节点个数
    public int length() {
        Node tmpNode = this.headNode;
        int nodeCount = 0;
        while (true) {
            // 如果没有下一个节点了，则返回统计的节点个数
            if (tmpNode.next == null) {
                return nodeCount;
                // 否则，节点个数进行加1，然后循环处理后面的节点
            } else {
                nodeCount++;
                tmpNode = tmpNode.next;
            }
        }
    }


    // 获取单向链表倒数第index个节点
    public Node getLastIndexNode(int index) {
        Node tmpNode = this.headNode;

        int nodeCount = this.length();
        // 进行index的验证，如果不符合要求，则返回null
        if (index  nodeCount) {
            System.out.println("传入的index小于等于0， 或超过的单向链表的最大长度");
            return null;
            // 如果index符合要求，则循环获取倒数第index个节点
        } else {
            for (int i = 0; i