学习目标：

• 简单实现链表增删改查

学习内容：

1. 外部类和内部类
2. 封装方法
3. 其他类使用内部类私有方法
4. 递归算法

代码块：

class test{
  public static void main(String[] args){
    Nodelianbiao nlb = new Nodelianbiao();
        nlb.add(10);
        nlb.add(9);
        nlb.add(8);
        nlb.add(7);		//添加数据
        nlb.print();	//输出所有数据
        nlb.del(9);		//删除元素为9的数据
        nlb.print();	
        System.out.println(nlb.find(11));	//查询元素是否存在
        nlb.update(7,8);	//修改元素（7改成8）
        nlb.print();		
        nlb.insert(3,11);	//插入元素（在小标为3的位置插入元素为11的数据）
        nlb.print();
  }
}

class Nodelianbiao{
    private Node root;      //根节点
    private int countindex = 0;
    public void add(int data){
        if(root == null){
            root = new Node(data);
            countindex++;
        }else{
            root.addNode(data);
        }
    }
    public void del(int data){
        if(root.getData() == data){
            root = root.next;
            countindex--;
        }else{
            root.delNode(data);
        }
    }
    public void print(){
        if(root!=null){
            System.out.print(root.data+"=>");
            root.printNode();
            System.out.println();
        }
    }
    public boolean find(int data){
        if (root.getData() == data) return true;
        else{
            if (root.findNode(data)) return true;
        }
        return false;
    }
    public void update(int olddata,int newdata){
        if(find(olddata)){
            if(root.getData() == olddata){
                root.setData(newdata);
            }
            else{
                root.updateNode(olddata,newdata);
            }
        }
        else{
            System.out.println("无此数据");
        }
    }
    public void insert(int index,int data){
        if(this.countindex>=index){
            int temp = 0;
            if(index == 0){
                Node root1 = new Node(data);
                root1.next = root;
                root = root1;
            }
            else{
                temp++;
                root.insertNode(index,data,temp);
            }
        }
    }

    private class Node{
        private int data;
        private Node next;

        private Node(int data){
            this.data = data;
        }
        private void setData(int data){
            this.data = data;
        }
        private int getData(){
            return data;
        }
        //添加节点
        private void addNode(int data){
            if(this.next == null){
                this.next = new Node(data);
                countindex++;
            }else{
                this.next.addNode(data);
            }
        }
        //删除节点
        private void delNode(int data){
            if(this.next!=null){
                if(this.next.data == data){
                    this.next = this.next.next;
                    countindex--;
                }
                else{
                    this.next.delNode(data);
                }
            }
        }
        //输出所有节点
        private void printNode(){
            if(this.next!=null){
                System.out.print(this.next.data+"=>");
                this.next.printNode();
            }
        }
        //查找节点是否存在
        private boolean findNode(int data){
            if (this.next!=null) {
                if (this.next.data == data) return true;
                else if (this.next.findNode(data)) return true;
            }
            return false;
        }
        //修改节点
        private void updateNode(int olddata,int newdata){
            if(this.next.data == olddata){
                this.next.setData(newdata);
            }
            else{
                this.next.updateNode(olddata,newdata);
            }
        }
        //插入节点
        private void insertNode(int index,int data,int temp){
            if(index == temp){
                Node count = new Node(data);
                count.next = this.next;
                next = count;
            }else{
                temp++;
                this.next.insertNode(index,data,temp);
            }
        }
    }
}

代码解析：

编写外部类和内部类

首先我们编写一个外部类叫Nodewaibulei

class Nodewaibulei{

}

在外部类中再编写一个私有的内部类叫Node

class Nodewaibulei{
	private class Node{
	
	}
}

在内部类定义一个私有的int类型数据data
再定义一个私有的内部类类型的数据next
给内部类定义构造方法
给data编写get，set方法

private class Node{
	private int data;
	private Node next;
	
	private Node(int data){
		this.data = data;
	}
	private void setData(int data){
		this.data = data;
	}
	private int getData(){
		return data;
	}
}

在内部类再编写六个方法，分别是：
addNode() \t添加
delNode() 删除
findNode() 查
printNode() 输出所有
updateNode() 修改
insertNode() 插入

private class Node{
	private int data;
	private Node next;

	private void setData(int data){
		this.data = data;
	}
	private int getData(){
		return data;
	}
	private void addNode(int data){		//添加数据

	}
	private void delNode(int data){			//删除数据
	
	}
	private boolean findNode(int date){		//查询数据（返回boolean)
		return false;
	}
	private void printNode(){		//输出所有数据
	
	}
	private void updateNode(int olddate,int newdata){		//修改数据，olddata为原数据，newdata新数据

	}
	private void insertNode(int index,int data){	//插入数据，index插入索引位置

	}
}

内部类私有方法虽然外部类可以使用，但其他类中无法调用，所以在外部类中编写共有的方法
外部类中：

class Nodewaibulei{
	public void add(int data){

	}
	public void del(int data){

	}
	public boolean find(int data){
		return false;
	}
	public void print(){

	}
	public void update(int olddate,int newdata){

	}
	public void insert(int index,int data){

	}
}

在外部类中定义内部类类型的数据，这也叫根节点。

class Nodewaibulei{
	private Node root;
}

添加数据

咱们回到main方法中
先创建一个Nodewaibulei类
再用add方法添加一个数据

public static void main(String[] args){
	Nodewaibulei nwbl = new Nodewaibulei();
	nwbl.add(10);
	
}

此时add方法接收到一个参数，我们要判断链表根节点是否为null，

1. 如果是，创建根节点并把参数直接赋给根节点
2. 如果否，调用内部类中的addNode()方法

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

		咱们回到内部类中的addNode()方法中，

判断内部类中的next是否为空

• 如果是，新建一个内部类，data数据赋给新类，并把新类赋给next
• 如果否，调用next中的addNode()方法，并把参数递过去。

private void addNode(int data){
    if(this.next == null){
        this.next = new Node(data);
    }else{
        this.next.addNode(data);
    }
}

这里有点绕，next本身就是一个内部类类型的数据，每次创建一个新的内部类时，它都会定义一个空的内部类对象next。也就是说每添加一个数据，就会多出一个空的next，为下一次添加新值准备。

比如咱们添加第一个数据时，在外部类中给内部类类型的root 创建一个新的内部类，

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

因为是第一个数据，所以root为空，当我们给root创建新的内部类时，内部类就定义了两个参数，一个是int类型的数据data，另一个是内部类类型的next。
data是有构造方法，定义类时就得提供参数，而next就不需要，所以定义一个新的内部类，就得空出一个next；
那什么时候用next？就是又要新添加数据时，new一个新的内部类，并把它赋给next。当然了，new出来的内部类又会空出一个next;

	回过头来看一下内部类中的add方法，

判断next是否为空：

• 如果是，新建一个内部类，data数据赋给新类，并把新类赋给next
• 如果否，调用next中的addNode()方法，并把参数递过去。

添加数据完成。

private void addNode(int data){
    if(this.next == null){
        this.next = new Node(data);
    }else{
        this.next.addNode(data);
    }
}

输出所有数据

		我们回到main方法中

咱们通过add方法多加几个数据，然后通过print方法输出所有数据。

public static void main(String[] args){
	Nodewaibulei nwbl = new Nodewaibulei();
	nwbl.add(10);
	nwbl.add(9);
	nwbl.add(11);
	nwbl.add(13);
	nwbl.add(15);
	nwbl.print();	//输出所有数据
}

		我们回到外部类print方法中。

首先要判断根节点是否为空，也就是第一个数字是否为空

• 如果否，就输出根节点（说明根节点有数据）
• 调用内部类中的printNode方法（继续输出其他节点上的数据）

public void print(){
    if(root!=null){
        System.out.print(root.data+"=>");
        root.printNode();
        System.out.println();
    }
}

		内部类中的printNode方法：

判断内部类中的next是否为空

• 如果否，输出该节点数据（说明该节点存在）
• 继续调用next中的printNode方法，直到nex为空。

输出所有数据完成。

private void printNode(){
    if(this.next!=null){
        System.out.print(this.next.data+"=>");
        this.next.printNode();
    }
}

删除数据

		我们回到main方法中

通过del方法删除数据

public static void main(String[] args){
	Nodewaibulei nwbl = new Nodewaibulei();
	nwbl.add(10);
	nwbl.add(9);
	nwbl.add(11);
	nwbl.add(13);
	nwbl.add(15);
	nwbl.del(11);		//删除元素为11的数据。
}

		我们回到外部类del方法中。

判断参数是否跟根节点相同

• 如果是，把第二个节点赋给第一个节点（根节点被覆盖，从而达到删除效果）
• 如果否，调用内部类中delNode方法，并把参数传递过去。

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

		内部类中的delNode方法

判断next是否为空，
如果否，再判断数据data跟参数data是否相等。

• 如果是，把数据next中的下一个next赋给现在的next。
• 如果否，继续调用next中的delNode()方法，并把参数传递过去。

删除数据完成。

private void delNode(int data){
    if(this.next!=null){
        if(this.next.data == data){
            this.next = this.next.next;
        }
        else{
            this.next.delNode(data);
        }
    }
}

其他几个方法也同样利用递归算法实现查找，插入，修改等操作。