单向链表

• 以节点的方式来存储，包含data和next
• 在内存中，链表的各个节点不一定是连续存储的
• 链表分有头节点的链表和没有头节点的链表，头节点用head表示
• 代码主要是单向链表的增删改查

import java.util.Stack;

public class Demo2 {
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        //创建用户节点，并插入链表
        UserNode user1 = new UserNode(1, "一一");
        UserNode user3 = new UserNode(3, "三三");
        UserNode user2 = new UserNode(2, "二二");
        linkedList.addNode(user1);
        linkedList.addNode(user3);
        linkedList.addNode(user2);
        linkedList.getList();
        System.out.println();

        //按id大小插入
        System.out.println("有序插入");
        UserNode user5 = new UserNode(5, "五五");
        UserNode user4 = new UserNode(4, "四四");
        linkedList.addByOrder(user5);
        linkedList.addByOrder(user4);
        linkedList.getList();
        System.out.println();

        //按id修改用户信息
        System.out.println("修改用户信息");
        UserNode userEdit = new UserNode(1, "新一一");
        linkedList.changeNode(userEdit);
        linkedList.getList();
        System.out.println();

        //根据id删除用户信息
        System.out.println("删除用户信息");
        linkedList.deleteNode(new UserNode(3, ""));
        linkedList.getList();
        System.out.println();

        //获得倒数第几个节点
        System.out.println("获得倒数节点");
        System.out.println(linkedList.getUserByRec(2));
        System.out.println();

        //翻转链表
        System.out.println("翻转链表");
        MyLinkedList newLinkedList = linkedList.reverseList();
        newLinkedList.getList();
        System.out.println();

        //倒叙遍历链表
        System.out.println("倒序遍历链表");
        newLinkedList.reverseTraverse();

    }
}

/**
 * 创建链表
 */
class MyLinkedList {
    private UserNode head = new UserNode(0, "");

    /**
     * 在链表尾部添加节点
     *
     * @param node 要添加的节点
     */
    public void addNode(UserNode node) {
        //创建一个辅助节点,用于遍历
        UserNode temp = head;
        //找到最后一个节点
        while (true) {
            //temp是尾节点就停止循环
            if (temp.next == null) {
                break;
            }
            //不是尾结点就向后移动
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 遍历链表
     */
    public void getList() {
        System.out.println("开始遍历链表");
        if (head.next == null) {
            System.out.println("链表为空");
        }
        //创建辅助节点
        UserNode temp = head.next;
        while (true) {
            //遍历完成就停止循环
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 按id顺序插入节点
     *
     * @param node
     */
    public void addByOrder(UserNode node) {
        //如果一个节点都没用，直接插入
        if (head.next == null) {
            head.next = node;
            return;
        }
        UserNode temp = head;
        while (temp.next != null && temp.next.id < node.id) {
            temp = temp.next;
        }
        //当目标node的id最大时，则不会执行if中的语句
        if (temp.next != null) {
            node.next = temp.next;
        }
        temp.next = node;
    }

    /**
     * 根据id来修改节点信息
     *
     * @param node 修改信息的节点
     */
    public void changeNode(UserNode node) {
        UserNode temp = head;
        //遍历链表，找到要修改的节点
        while (temp.next != null && temp.id != node.id) {
            temp = temp.next;
        }
        //如果temp已经是最后一个节点，判断id是否相等
        if (temp.id != node.id) {
            System.out.println("未找到该用户的信息，请先创建该用户的信息");
            return;
        }
        //修改用户信息
        temp.name = node.name;
    }

    /**
     * 根据id删除节点,找到待删除节点的上一个节点
     *
     * @param node 要删除的节点
     */
    public void deleteNode(UserNode node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        UserNode temp = head;
        //遍历链表，找到要删除的节点
        while (temp.next != null && temp.next.id != node.id) {
            temp = temp.next;
        }
        //判断最后一个节点的是否要删除的节点
        if (temp.next.id != node.id) {
            System.out.println("请先插入该用户信息");
            return;
        }
        //删除该节点
        temp.next = temp.next.next;
    }

    /**
     * 得到倒数的节点
     *
     * @param index 倒数第几个数
     * @return
     */
    public UserNode getUserByRec(int index) {
        if (head.next == null) {
            System.out.println("链表为空!");
        }
        UserNode temp = head.next;
        //记录链表长度
        //所以length初始化为1
        int length = 1;
        while (temp.next != null) {
            temp = temp.next;
            length++;
        }
        if (length < index) {
            throw new RuntimeException("链表越界");
        }
        //假设有五个，倒数第一个相当于正数第五个
        temp = head.next;
        for (int i = 0; i < length - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 翻转链表
     *
     * @return 反转后的链表
     */
    public MyLinkedList reverseList() {
        //链表为空或者只有一个节点，无需翻转
        if (head.next == null || head.next.next == null) {
            System.out.println("无需翻转");
        }
        MyLinkedList newLinkedList = new MyLinkedList();
        //用于保存正在遍历的节点
        UserNode temp = head.next;
        //用于保存正在遍历节点的下一个节点
        UserNode nextNode = temp.next;
        while (true) {
            //插入新链表
            temp.next = newLinkedList.head.next;
            newLinkedList.head.next = temp;
            //移动到下一个节点
            temp = nextNode;
            nextNode = nextNode.next;
            if (temp.next == null) {
                //插入最后一个节点
                temp.next = newLinkedList.head.next;
                newLinkedList.head.next = temp;
                head.next = null;
                return newLinkedList;
            }
        }
    }

    public void reverseTraverse() {
        if (head == null) {
            System.out.println("链表为空");
        }

        UserNode temp = head.next;
        //创建栈，用于存放遍历到的节点
        Stack<UserNode> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

/**
 * 定义节点
 */
class UserNode {
    int id;
    String name;
    //用于保存下一个节点的地址
    UserNode next;

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

    @Override
    public String toString() {
        return "UserNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}