数据结构之链表

  在链表数据结构中，我们需要使用到递归算法。
  递归算法是一种直接或间接地调用自身短发的过程，在计算机编写程序中，递归算法对解决一大类问题都是十分有效的，它往往使算法的描述简洁而且易于理解。

一、递归算法

1、不使用递归

public class Test1 {
    public static void main(String[] args){
        int num1 = jiecheng1(10);
        System.out.println(num1);
    }

    public static int jiecheng1(int num){
        int result = num;
        int i = num -1;
        do {
            result = result * i;
            i--;
        }while (i>1);
        return result;
    }
}

使用阶乘算法

public class Test1 {
    public static void main(String[] args){
        int num2 = jiecheng2(10);
        System.out.println(num2);
    }
    // 递归算法要有出口
   // 递归内存消耗大，容易发生内存溢出
   // 层次调用越多越危险
    public static int jiecheng2(int num){
        if(num == 1) return 1;
        return num * jiecheng2(num-1);
    }
}

二、链表

  链表（Linked list）一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存的是下一个节点的指针（Pointer）。

链表

public class Test1 {
    public static void main(String[] args){
       NodeManager nm = new NodeManager();
       nm.add(0);
       nm.add(1);
       nm.add(2);
       nm.add(3);
       nm.add(4);
       nm.print();
       nm.del(3);
       nm.print();
       System.out.println(nm.find(4));
       System.out.println(nm.find(5));
        System.out.println("=====update====");
        nm.update(4, 40);
        nm.print();

    }
}


class NodeManager{

    private Node root; // 根节点

    public void add(int data){
        if(root == null){
            root = new Node(data);
        } else {
            root.addNode(data);
        }
    }

    public void del(int data){
        if(root.getData()==data){
            root = root.next;
        } else {
            root.delNode(data);
        }
    }

    // 打印所有
    public void print(){
        if(root!=null){
            System.out.print(root.getData()+"->");
            root.printNode();
            System.out.println();
        }
    }

    public boolean find(int data){
        if(root==null) return false;
        if(root.getData()==data){
            return true;
        } else {
            return root.findNode(data);
        }
    }

    public boolean update(int oldData, int newData){
        if(root==null)return false;
        if(root.getData()==oldData){
            root.setData(oldData);
            return true;
        } else {
            return root.updateNode(oldData, newData);
        }
    }
    

    private class Node{
        private int data;
        private Node next;  // 把当前的类型作为类型

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

        public void setData(int data){
            this.data = data;
        }

        public int getData(){
            return data;
        }

        // 添加节点
        public void addNode(int data){
            if(this.next == null){
                this.next = new Node(data);
            } else {
                this.next.addNode(data);
            }
        }

        // 删除节点
        public void delNode(int data){
            if(this.next!=null){
                if(this.next.getData()==data){
                    this.next = this.next.next;
                } else {
                    this.next.delNode(data);
                }
            }
        }

        // 输出所有节点
        public void printNode(){
            if(this.next!=null){
                System.out.print(this.next.data+"->");
                this.next.printNode();
            }
        }

        // 查找节点
        public boolean findNode(int data){
            if(this.next!=null){
                if(this.next.data == data){
                    return true;
                } else {
                    return this.next.findNode(data);
                }
            }
            return false;
        }

        // 修改节点数据
        public boolean updateNode(int oldData, int newData){
            if(this.next!=null){
                if(this.next.data==oldData){
                    this.next.data=newData;
                    return true;
                }else{
                    return this.next.updateNode(oldData, newData);
                }
            }
            return false;
        }
    }
}