??在鏈表數(shù)據(jù)結(jié)構(gòu)中，我們需要使用到遞歸算法。
??遞歸算法是一種直接或間接地調(diào)用自身短發(fā)的過(guò)程，在計(jì)算機(jī)編寫(xiě)程序中，遞歸算法對(duì)解決一大類問(wèn)題都是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。

一、遞歸算法

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);
    }
    // 遞歸算法要有出口
   // 遞歸內(nèi)存消耗大，容易發(fā)生內(nèi)存溢出
   // 層次調(diào)用越多越危險(xiǎn)
    public static int jiecheng2(int num){
        if(num == 1) return 1;
        return num * jiecheng2(num-1);
    }
}

二、鏈表

??鏈表（Linked list）一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存的是下一個(gè)節(jié)點(diǎn)的指針（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; // 根節(jié)點(diǎn)

    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;  // 把當(dāng)前的類型作為類型

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

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

        public int getData(){
            return data;
        }

        // 添加節(jié)點(diǎn)
        public void addNode(int data){
            if(this.next == null){
                this.next = new Node(data);
            } else {
                this.next.addNode(data);
            }
        }

        // 刪除節(jié)點(diǎn)
        public void delNode(int data){
            if(this.next!=null){
                if(this.next.getData()==data){
                    this.next = this.next.next;
                } else {
                    this.next.delNode(data);
                }
            }
        }

        // 輸出所有節(jié)點(diǎn)
        public void printNode(){
            if(this.next!=null){
                System.out.print(this.next.data+"->");
                this.next.printNode();
            }
        }

        // 查找節(jié)點(diǎn)
        public boolean findNode(int data){
            if(this.next!=null){
                if(this.next.data == data){
                    return true;
                } else {
                    return this.next.findNode(data);
                }
            }
            return false;
        }

        // 修改節(jié)點(diǎn)數(shù)據(jù)
        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;
        }
    }
}