1. 链表的基本形式
链表主要知识点
- 此次的内容属于引用部分的实际应用，所以需要依赖两点：
- 依赖于引用传递
- this表示当前对象。
- 链表的实现基本模式；
- 开发并且使用可用链。
链表基本形式
链表是一种最为简单的数据结构，它的主要目的是依靠引用关系来实现多个数据的保存。
链表模型图
范例：定义一个Node类
- 假设本次保存的数据是String型，同时拥有下一个引用；
//每一个链表实际上就是有多个节点所组成的
class Node {
//定义一个节点
private String data; //要保存的数据
private Node next; //要保存下一个节点
//每一个Node类对象都必须保存有相应的数据
public Node(String data) { //必须有数据才有Node
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
}
以上只是一个专门负责保存节点的类，具体怎么保存并不是Node类负责，需要由其它的类来负责Node的关系匹配
范例：使用第一种形式设置和取出数据
public class LinkDemo {
public static void main(String[] args) {
//第一步：准备出所有数据
Node root = new Node("火车头");
Node n1 = new Node("No1");
Node n2 = new Node("No2");
root.setNext(n1);
n1.setNext(n2);
//第二步：取出所有数据
Node currentNode = root; //从根节点开始读取
while (currentNode != null) {
System.out.println(currentNode.getData());
//将下一个节点设置为当前节点
currentNode = currentNode.getNext();
}
}
}
实际以上的操作使用的循环并不方便，最好的做法还是应该使用递归操作完成。
范例：使用第二种方式设置和取得数据
public class LinkDemo2 {
public static void main(String[] args) {
//第一步：准备出所有数据
Node root = new Node("火车头");
Node n1 = new Node("No1");
Node n2 = new Node("No2");
root.setNext(n1);
n1.setNext(n2);
print(root);
}
public static void print(Node current) {
if (current == null) {
return ;
}
System.out.println(current.getData());
print(current.getNext());
}
}
由于所有的节点并不知道具体的操作次数，所以只能用while使用，但是在节点的操作中，递归比while更加的直观。
疑问?整个代码实际上就是完成设置数据和取去数据的过程，为什么需要Node呢?
因为，数据本身不具备先后的关系，所以使用Node类的封装数据，同时利用Node类来指向下一个节点。
2. 链表的基本雏形
通过分析发现：
- 用户在操作的过程之中完全没有必要去Node类是否存在；
- 所有的节点的引用关系不应该由用户去处理，应该有一个专门的工具类来进行处理。
定义一个类，使客户端隐藏所有的链表中给出的细节操作。
范例：链表的基本形式
//每一个链表实际上就是有多个节点所组成的
class Node {
//定义一个节点
private String data; //要保存的数据
private Node next; //要保存下一个节点
//每一个Node类对象都必须保存有相应的数据
public Node(String data) { //必须有数据才有Node
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
public void addNode(Node newNode) {
if (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类对象的关系处理
class Link {
//根节点
private Node root;
public void add(String data) {
//为了可以设置数据的先后关系，所以将data包装在一个Node类对象
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 LinkDemo3 {
public static void main(String[] args) {
//由这个类负责所有的数据操作
Link link = new Link();
link.add("hello"); //存放数据
link.add("world"); //存放数据
link.add("WWWW"); //存放数据
link.print(); //展示数据
}
}
链表的基本特点：
- 客户端代码不实现Node以及引用关系的细节，只使用Link类中提供的方法；
- Link类的主要功能时控制Node类对象的产生和根节点；
- Node类主要负责数据的保存以及引用关系的分配。
3. 开发可用链表
可以使用链表实现数据的增加、修改、删除、查询操作
1. 程序基本结构
Node类负责所有的节点数据的保存以及节点关系的匹配，所以Node类，不可能单独去使用，而以上的代码里面Node时可以单独使用的，外部可以荣国Link类直接操作Node类，这样是没有意义的；所以修改代码，是Node为内部类，只能被Link类使用。
内部类可以使用private定义，这样内部类只能被外部类使用，而且，内部类可以方便的与外部类之间进行私有属性的直接访问。
范例：链表的开发结构
class Link { //链表类，外部能够看见的只有这一个类
//之所以定义在内部，主要是之让Link类能调用
private class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
}else {
this.next.addNode(newNode);
}
}
}
}
//=================以上为内部类=====================
2. 数据增加 public void add(数据类型 变量)
如果要进行新数据的增加，则应该由Link类负责节点对象的产生，并且由Link类维护根节点，所有的节点的关系匹配交给Node类处理。
class Link { //链表类，外部能够看见的只有这一个类
//之所以定义在内部，主要是之让Link类能调用
private class Node {
private String data;
private Node next;
public Node(String data) {
this.data = data;
}
public void addNode(Node newNode) {
if (this.next == null) {
this.next = newNode;
}else {
this.next.addNode(newNode);
}
}
}
//=================以上为内部类=====================
private Node root;
public void add(String data) {
//判断链表不能为空，但不是所有的链表都不许为空
if (data == null) {
return;
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
}else {
this.root.addNode(newNode);
}
}
}
public class LinkDemo4 {
public static void main(String[] args) {
Link all = new Link();
all.add("hello");
all.add("world");
all.add("null");
}
}
3. 取链表元素个数 public int size()
每个链表都有长度，可以直接在Link类里面设置一个count属性，随后每一次数据添加之后，可以进行个数自增。
范例：修改Link.java类
class Link { //链表类，外部能够看见的只有这一个类
private Node root;
//增加一个count属性
private int count = 0; //保存元素的个数
public void add(String data) {
//判断链表不能为空，但不是所有的链表都不许为空
if (data == null) {
return;
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
}else {
this.root.addNode(newNode);
}
this.count ++ ; //每一次保存完成后元素个数+1
}
public int size() {
return this.count;
}
}
再在Link类里面添加一个新的方法：size（）
public int size() {
return this.count;
}
此程序中null不会保存
4. 判断链表是否为空 public boolean isEmpty()
空链表的两种判断方式：
- 判断root是否有对象(是否为null)；
- 判断保存的数据量的值(count)。
范例：判断是否为空链表
public boolean isEmpty() {
return this.count == 0;
}
5. 数据查询 public boolean contains(数据类型 变量)
在链表中一定会保存多个数据，判断数据存在的方式，以：String类型为例，循环查询链表中的内容，并且要与查询的数据进行匹配(equals())，如果查找到了返回true，否则返回false。
范例：修改Link.java 类
public boolean contains(String data) {
//现在没有要查询的数据，根节点也不保存数据
if (data == null || this.root == null) {
return false;
}
return this.root.containsNode(data);
}
范例：在Node类中增加方法
public boolean containsNode(String data) {
//当前节点数据为要查询的数据
if (data.equals(this.data)) {
return true;
} else {
//当前节点不是要查询的数据
//判断时候后下一个节点
if (this.next != null) {
return this.next.containsNode(data);
} else {
return false;
}
}
}
6. 根据索引取得数据 public 数据类型 get(int index)
示例图
范例：在Link类里面添加一个foot属性，表示Node元素编号
private int foot = 0;
范例：foot每一次查询都应该从头开始
public String get(int index) {
if (index > this.count) {
return null;
} else {
this.foot = 0;
return this.root.getNode(index);
}
}
范例：在Node类实现getNode()方法，
public String getNode(int index) {
//使用当前的foot内容与要查询的内容比较
//foot自增，目的是为了下次查询
if (Link.this.foot ++ ==index) { //要查询的索引
return this.data; //返回当前节点数据
} else { //向后查询
return this.next.getNode(index);
}
}
内部类和外部类之间可以方便的进行私有属性的互相访问。
7. 修改指定索引内容public void set(int index , 数据类型 变量)
修改数据和查询的区别不大，查询的时候当满足索引值的时候，只是进行了一个数据的返回，那么此处只需要将数据返回改成数据的重新赋值即可。
范例：在Link类里面增加set()方法
public void set(int index , String data) {
if (index > this.count) {
return ;
} else {
this.foot = 0;
this.root.setNode(index , data);
}
}
范例：在Node类里面增加setNode方法
public void setNode(int index , String data) {
if (Link.this.foot ++ ==index) {
this.data = data;
} else {
this.next.setNode(index , data);
}
}
8. 数据删除public void remove(数据类型 变量)
数据删除分两种情况：
- 删除根节点，则root应该指向"root.next" ， Like类中处理这种情况
- 要删除的不是 根节点，而是其它的普通节点，应该在Node类里面处理，所以此处从第二个节点开始判断的。
范例：在Node类里增加一个removeNode()方法，此方法处理非根节点的删除
public void removeNode(Node previous , String data) {
if (data.equals(this.data)) {
previous.next = this.next;
} else {
this.next.removeNode(this , data);
}
}
范例：在Link类里面增加remove()方法和根节点的判断
public void remove(String data) {
if (this.contains(data)) { //判断数据是否存在
if (data.equals(this.root.data)) {
this.root = this.root.next;
} else {
this.root.next.removeNode(this.root , data);
}
this.count -- ;
}
}
9. 将链表转换为数组public 数组类型[] toArray
在任何情况下，不管是什么样的类，都不可能总理类中使用输出语句，只要是想输出数据一定将数据返回到调用处进行输出，而由于链表属于动态对象数组，所以此处最好的做法是将链表以对象数组的形式返回。
范例：修改Link类的定义
- 增加一个返回数组类型的属性，内部类和外部类都可以访问
private String[] retArray
- 增加toArray()方法
public String[] toArray() {
if (this.root == null) {
return null;
}
this.foot = 0;
//根据保存内容开辟数据
this.retArray = new String[this.count];
this.root.toArrayNode();
return this.retArray;
}
}
范例：在Node类里面处理数组数据的保存
public void toArrayNode() {
Link.this.retArray[Link.this.foot++] = this.data;
if (this.next != null) {
this.next.toArrayNode();
}
}
实现的前提：内部类与外部类之间可以直接进行私有属性的访问。
