[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+"->");
}
~~~
