关于链表:java实现单向链表

单向链表

• 以节点的形式来存储，蕴含 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 + '\'' +
                '}';
    }
}