算法与数据结构03-单链表与双链表

算法与数据结构03-单链表与双链表

== 说明：文章内容为跟着视频学习的文章，算不上原创，就是总结记录自己的学习过程==

单链表

package com.kele;

/**
 * @author 12402
 */
public class Node {

    // 节点内容
    int data;

    //下一个节点
    Node next;

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

    // 追加节点
    public Node append(Node node){
        Node currentNode = this;

        while (true){
            Node nextNode = currentNode.next;

            if (nextNode == null){
                break;
            }
            currentNode = nextNode;
        }
        currentNode.next = node;
        return this;
    }

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

    // 获取节点数据
    public int getData(){
        return this.data;
    }

    //判断是否为最后一个节点
    public boolean isLast(){
       return this.next == null;
    }

    // 删除节点
    public void remove(){
        Node nextNode = next.next;
        this.next = nextNode;
    }

    // 显示每个节点
    public void show(){
        Node currentNode = this;
        while (true){
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.next;
            if (currentNode == null){
                break;
            }
        }
        System.out.println();
    }

    // 插入一个节点
    public void insert(Node node){
        // 将下一个节点定义为：再下一个节点
        Node nextNext = next;
        // 给下一个节点赋值
        this.next = node;
        // 将nextNext赋值给新节点的下一个节点，完成节点插入
        node.next = nextNext;

    }
}

双链表

package com.kele;

/**
 * @author 12402
 */
public class DoubleNode {

    //上一个节点
    DoubleNode pre = this;

    // 下一个节点
    DoubleNode next = this;

    int data;

    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 getData(){
        return this.data;
    }
}

循环链表

package com.kele;

/**
 * @author 12402
 */
public class LoopNode {

    // 节点内容
    int data;

    //当前节点指向开始节点，完成循环链表
    LoopNode next = this;

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


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

    // 获取节点数据
    public int getData(){
        return this.data;
    }


    // 删除节点
    public void remove(){
        LoopNode nextNode = next.next;
        this.next = nextNode;
    }

    // 插入一个节点
    public void insert(LoopNode node){
        // 将下一个节点定义为：再下一个节点
        LoopNode nextNext = next;
        // 给下一个节点赋值
        this.next = node;
        // 将nextNext赋值给新节点的下一个节点，完成节点插入
        node.next = nextNext;

    }
}

总结

• 删除节点：将三个节点的最后一个节点赋值给中间节点，完成删除，是没有办法
  直接删除节点的。
• 追加节点：先定义一个当前节点C，然后再定义一个下一个节点N， 将当前节点C的下一个节点赋值给定义的下一个节点N，
  判断N节点是否为空，如果为空直接跳出循环，将新节点n 赋值给C节点的下一个节点，完成节点插入。如果不为空，将N节点再赋值给当前节点C，继续寻找下一节点为空的
  的节点，找到后跳出循环，将新节点n赋值给C 节点，完成插入。

// 删除节点
public void append(Node node){
       Node currentNode = node;

       while (true){
           Node nextNode = currentNode.next;
           if (nextNode == null){
               break;
           }

           currentNode = nextNode;
       }

       currentNode.next = node;
   }

• 插入节点：就是将下一个节点nextNode，往后推一个节点成为nextNext节点，然后给nextNode赋值，
  ，将nextNext节点赋值给nextNode节点的next节点，完成节点插入。

// 插入节点
   public void insert(Node node){
       LoopNode nextNext = next;

       this.next = node;

       node.next = nextNext;
   }