四、链表的学习

单链表：

/**
 * @author zhou
 * @date 2021-5-7 14:57
 * 
 * 单链表  MyNode就代表一个节点
 */
public class MyNode {
    // 节点内容
    // 下一个节点

    int date;
    MyNode next;

    public MyNode(int date) {
        this.date = date;
    }

    /**
     * 为节点追加节点
     * @param node
     * @date 2021-5-8 19:40
     */
    public MyNode append(MyNode node) {
        // 当前节点
        MyNode currentNode = this;
        // 循环向后找
        while(true){
            // 取出下一个节点
            MyNode nextNode = currentNode.next;
            // 如果下一个节点为null 当前节点已经是最后一个节点了
            if (nextNode == null) {
                break;
            }
            // 赋值给当前节点
            currentNode = nextNode;
        }
        // 把需要追加的节点 追加为 找到的当前节点的下一个节点
        currentNode.next = node;
        return this;
    }

    public MyNode next(){ // 获取下一个节点
        return this.next;
    }
    public int getDate(){ // 获取节点中的数据
        return this.date;
    }

    public boolean isLastNode(){ // 当前节点是否是最后一个节点
        return this.next == null;
    }

    public void removeNext() { // 删除下一个节点 这里删除的都是它下一个节点
        // 取出下下一个节点
        MyNode nextNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = nextNext;
    }

    public void show(){ // 显示所有节点信息
        MyNode currentNode = this;
        while (true) {
            System.out.print(currentNode.date + " ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if (currentNode == null) {
                break;
            }
        }
        System.out.println();
    }

    public void after(MyNode node) { // 插入一个节点作为当前节点的下一个节点
        // 取出下一个节点 作为下下一个节点
        MyNode nextNext = next;
        // 把新节点作为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点设置为 新节点的下一个节点
        node.next = nextNext;
    }

}

单链表测试类：

/**
 * @author zhou
 * @date 2021-5-7 15:00
 * 测试手写的链表
 */
public class TestNode {
    public static void main(String[] args) {
        // 创建节点
        MyNode n1 = new MyNode(1);
        MyNode n2 = new MyNode(2);
        MyNode n3 = new MyNode(3);
        // 追加节点
        n1.append(n2).append(n3).append(new MyNode(4));
        // 取出下一个节点
        System.out.println(n1.next().next().next().getDate());
        // 判读是否是最后一个节点
        System.out.println(n1.isLastNode());
        System.out.println(n1.next().next().next().isLastNode());
        // 显示所有节点
        n1.show();
        // 删除一个节点 这里删除的都是它下一个节点
//        n1.next().removeNext();
        n1.show();
        MyNode node = new MyNode(5);
        n1.next().after(node);
        n1.show();
    }
}

运行结果：

4
false
true
1 2 3 4
1 2 3 4
1 2 5 3 4

循环链表：

package com.zhou.loop;

/**
 * @author zhou
 * @date 2021-5-8 20：32
 * 循环链表
 */
public class LoopNode {
    // 节点内容
    // 下一个节点

    int date;
    LoopNode next=this;

    public LoopNode(int date) {
        this.date = date;
    }

    public LoopNode next(){ // 获取下一个节点
        return this.next;
    }

    public int getDate(){ // 获取节点中的数据
        return this.date;
    }

    public void removeNext() { // 删除下一个节点 这里删除的都是它下一个节点
        // 取出下下一个节点
        LoopNode nextNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = nextNext;
    }

    public void after(LoopNode node) { // 插入一个节点作为当前节点的下一个节点
        // 取出下一个节点 作为下下一个节点
        LoopNode nextNext = next;
        // 把新节点作为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点设置为 新节点的下一个节点
        node.next = nextNext;
    }

}

循环链表测试类：

package com.zhou.loop;

/**
 * @author zhou
 * @date 2021-5-8 20:36
 * 测试
 */
public class TestLoop {
    public static void main(String[] args) {
        LoopNode n1=new LoopNode(1);
        LoopNode n2=new LoopNode(2);
        LoopNode n3=new LoopNode(3);
        LoopNode n4=new LoopNode(4);
        // 增加节点
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getDate());
        System.out.println(n2.next().getDate());
        System.out.println(n3.next().getDate());
        System.out.println(n4.next().getDate());
    }
}

运行结果：

2
3
4
1

双向循环链表：

package com.zhou.doubleloop;

/**
 * @author zhou
 * @date 2021-5-8 20:38
 * 双向循环链表
 */
public class DoubleNode {
    // 结点数据
    // 上一个节点
    // 下一个节点

    int data;
    DoubleNode pre = this;
    DoubleNode next = this;

    public DoubleNode(int data) {
        this.data = data;
    }

    public void after(DoubleNode node) { // 增加节点
        // 原来的下一个节点
        DoubleNode nextNext = next;
        // 把新节点作为当前节点的下一个节点
        this.next = node;
        // 把当前节点作为新节点的前一个节点
        node.pre = this;
        // 让原来的下一个节点 作为 新节点的下一个节点
        node.next = nextNext;
        // 让原来的下一个节点的上一个节点为新节点
        nextNext.pre = node;
    }

    public DoubleNode next(){ // 下一个节点
        return this.next;
    }

    public DoubleNode pre(){
        return this.pre;
    }
    public int getDate(){
        return this.data;
    }

}

双向循环链表测试类：

package com.zhou.doubleloop;

/**
 * @author zhou
 * @date 2021-5-8 20:50
 */
public class TestDoubleNode {
    public static void main(String[] args) {
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);
        // 追加节点
        n1.after(n2);
        n2.after(n3);

        // 查看上一个、自己、下一个节点的内容
        System.out.println(n2.pre().getDate());
        System.out.println(n2.getDate());
        System.out.println(n2.next().getDate());

        System.out.println(n3.next().getDate());
        System.out.println(n1.pre().getDate());

    }
}

运行结果：

1
2
3
1
3