目录

 一：链表的定义 

 二：链表的改进

---

链表的实现可以为后面JAVA的类集框架服务。

链表是一种最简单的数据结构，其主要目的是依靠引用关系实现多个数据的保存。

一：链表的定义 

 

 定义一个Node类，保存的数据是String型，同时存储下一个数据的引用。

Node类只负责保存节点关系，但是具体的保存由其他类负责

class Node{/*链表的属性*/private String data;//数据private Node next;//下一个节点/*链表的构造*/public Node(String data) {//构造函数，定义数据this.data=data;}public void setNode(Node next) {//存储下一个节点信息this.next=next;}/*功能函数：取出数据或下一节点*/public String getData() {return this.data;}public Node getNode() {return this.next;}
}

 取数据：主程序法

 public static void main(String[] args) {/*第一步：创建链表*/Node root=new Node("火车头");Node n1=new Node("车厢A");Node n2=new Node("车厢B");root.setNode(n1);n1.setNode(n2);n2.setNode(null);/*第二步：取出所有数据*/	   Node curNode=root;while(curNode!=null) {System.out.println(curNode.getData());curNode=curNode.getNode();}}

 public static void print(Node cur) {if(cur==null) return;System.out.println(cur.getData());print(cur.getNode());//递归调用print()}

最后程序：

class Node{/*链表的属性*/private String data;//数据private Node next;//下一个节点/*链表的构造*/public Node(String data) {//构造函数，定义数据this.data=data;}public void setNode(Node next) {//存储下一个节点信息this.next=next;}/*功能函数：取出数据或下一节点*/public String getData() {return this.data;}public Node getNode() {return this.next;}
}
public class transfer {public static void main(String[] args) {/*第一步：创建链表*/Node root=new Node("火车头");Node n1=new Node("车厢A");Node n2=new Node("车厢B");root.setNode(n1);n1.setNode(n2);n2.setNode(null);print(root);//调用函数}public static void print(Node cur) {if(cur==null) return;System.out.println(cur.getData());print(cur.getNode());//递归调用print()}
}

由于取数据无法知道长度，一般只能用while，但是由于定义函数递归调用会比while更直观更易读。
核心：封装Node类的数据，然后利用Node的引用传递去排序数据。

 二：链表的改进

上述定义存在的问题：
1：用户在操作链表功能时没必要知道Node类的存在。
2：节点的引用关系不应该由用户处理，需要一个专门工具类
总之：客户端应该向用户隐藏链表的具体细节，用户只需要知道怎么存数据和取数据

这里选用尾插法，目的是为了在已有节点的最后插入新节点，根节点root不存数据 

class Node{//作为隐藏类，用户无需清楚/*节点的添加：目的找到已有数据的最后一个节点*/public void addNode(Node newNode) {//第一次调用：Link.rootif(this.next==null) {//根节点后为空，直接连this.next=newNode;}else {//根节点后有数据，递归this.next.addNode(newNode);}}public void printNode() {System.out.println(this.data);if(this.next!=null) {this.next.printNode();}}
}

 在Node类新加入两个函数：addNode()和printNode(),目的在于为用户操作的LinkNode类提供打印和添加节点操作。

class Link{//负责数据的设置和输出private Node root;//起始标志/*增加数据*/public void add(String data) {Node newNode=new Node(data);if(this.root==null)  this.root=newNode;//没有根节点时执行，且执行一次else   this.root.addNode(newNode);//根节点已经存在了，采取尾插法}/*取出数据*/public void print() {if(this.root!=null) {this.root.printNode();}}
}

创建链表的逻辑：
首先利用new关键字，在内存中开辟出空间（Node newNode=new Node(data);）
然后判断有无根节点，这是链表创建的初始化，如果有了根节点，接下来的操作也就是节点next的指向通过调用Node类的：addNode()
下面进行尾插法：（找到最后一个节点）
1：根节点后无新节点，直接：（this.next=newNode;）
2：根节点有新节点，递归调用addprint()去寻找，找到后执行（this.next=newNode;）
主程序：
         Link link=new Link();//创建了根节点
         link.add("火车头");
         link.add("车厢A");
         link.add("车厢B");
         link.add("车厢C");

总结：
Link类：控制Node类对象的产生和根节点
Node类：主要负责数据的保存和引用关系的分配

最后代码：

class Node{//作为隐藏类，用户无需清楚/*链表的属性*/private String data;private Node next;/*链表的构造*/public Node(String data) {this.data=data;}public void setNode(Node next) {this.next=next;}/*功能函数：取出数据或下一节点*/public String getData() {return this.data;}public Node getNode() {return this.next;}/*节点的添加：目的找到已有数据的最后一个节点*/public void addNode(Node newNode) {//第一次调用：Link.rootif(this.next==null) {//根节点后为空，直接连this.next=newNode;}else {//根节点后有数据，递归this.next.addNode(newNode);}}public void printNode() {System.out.println(this.data);if(this.next!=null) {this.next.printNode();}}
}
class Link{//负责数据的设置和输出private Node root;//起始标志，不保存数据，指向下一个节点/*增加数据*/public void add(String data) {Node newNode=new Node(data);if(this.root==null)  this.root=newNode;//没有根节点时执行，且执行一次else   this.root.addNode(newNode);//根节点已经存在了，采取尾插法}/*取出数据*/public void print() {if(this.root!=null) {this.root.printNode();}}
}
public class transfer {public static void main(String[] args) {Link link=new Link();link.add("火车头");link.add("车厢A");link.add("车厢B");link.add("车厢C");link.print();}
}