[toc]
### 链表
链表用内部类实现，外部类叫class LinkList，提供根节点和一些提供给外部的增删改查的方法。内部类叫class Node，用来表示节点的内部结构--date+next。
~~~
public class LinkList {
private Node root;//作为根节点
private int currentIndex = 0;//节点的序号，每次操作从0开始(插入操作时使用)
private class Node{
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
}
~~~
#### 链表增加节点操作
~~~
//给外部提供的增添数据方法
public void add(int data){
if(root==null){
root=new Node(data);
}else{
root.addNode(data);
}
}
//内部递归实现的
public void addNode(int data){
if(this.next==null){
this.next = new Node(data);
}else{
this.next.addNode(data);
}
}
~~~
#### 链表删除节点操作
~~~
//给外部提供的删除节点的方法
public void del(int data){
if(root.getData()== data){
root=root.next;
}else{
root.delNode(data);
}
}
//内部
public void delNode(int data){
if (this.next!= null){
if (this.next.data==data){
this.next = this.next.next;
}else{
this.next.delNode(data);
}
}
}
~~~
#### 链表插入节点操作
~~~
//插入数据,前插法（向索引之前插）
public void insert(int index,int data){
if (index<0) return;
currentIndex=0;
if (index==currentIndex){
Node newdata = new Node(data);
newdata.next = root;
root = newdata;
}else{
root.insertNode(index,data);
}
}
//内部
public void insertNode(int index,int data){
currentIndex++;
if (index==currentIndex){
Node newdata = new Node(data);
newdata.next=this.next;
this.next=newdata;
}else{
this.next.insertNode(index,data);
}
}
~~~
#### 链表修改节点操作
~~~
//外部修改节点的方法
public void updataNode(int olddata,int newdata){
if (this.next!=null){
if (this.next.data==olddata){
this.next.data = newdata;
return;
}else{
this.next.updataNode(olddata,newdata);
}
}
}
//内部的递归
public void updataNode(int olddata,int newdata){
if (this.next!=null){
if (this.next.data==olddata){
this.next.data = newdata;
return;
}else{
this.next.updataNode(olddata,newdata);
}
}
}
~~~
#### 链表操作总结
各种操作的入口都是外部类提供的，外部给的方法思想都是一样的：先看这个操作是不是和**根节点**有关，如果是外部类给的方法直接解决问题，如果不是就调用**内部类**对应的方法。
内部类方法的特点就是有**递归性**，当进入到内部类的方法里后，如果是**查找、删除、输出、修改**这些操作的时候要在**this.next!=null**的空的情况下进行下一步操作，下一步操作也很简单：
~~~
if(满足条件){
执行操作
}else{递归}
~~~
### 二叉树
二叉树也可以用内部类来实现，外部类叫class BinaryTree，用来存root节点；内部类叫Node，存数据data，左节点left和右节点right。
~~~
public class BinaryTree {
private Node root;
private class Node{
private int data;
private Node left;
private Node right;}
}
~~~
#### 输出节点
~~~
//外部类很简单，只需要root.printNode();
public void print(){
root.printNode();
}
//内部类中序遍历（从小到大输出）
public void printNode(){
if (this.left!=null){
this.left.printNode();
}
System.out.print(this.data+"->");
if (this.right!=null){
this.right.printNode();
}
}
//内部类前序遍历（
public void printNode(){
System.out.print(this.data+"->");
if (this.left!=null){
this.left.printNode();
}
if (this.right!=null){
this.right.printNode();
}
}
//内部类后序遍历
public void printNode(){
if (this.left!=null){
this.left.printNode();
}
if (this.right!=null){
this.right.printNode();
}
System.out.print(this.data+"->");
}
~~~
