链表的定义与使用

一、链表基本形式

链表是一种最为简单的数据结构，它的主要目的是依靠引用关系来实现多个数据的保存，那么下面假设现在要保存的数据是字符串。

范例：定义一个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("车厢A");
		Node n2 = new Node("车厢B");
		root.setNext(n1);
		n1.setNext(n2);
		// 第二步：取出所有数据
		Node currentNode = root;// 当前从根节点开始读取
		while (currentNode != null) {// 当前节点存在有数据
			System.out.println(currentNode.getData());
			// 将下一个节点设置为当前节点
			currentNode = currentNode.getNext();
		}
	}
}

实际上以上的操作使用的循环并不方便，最好的做法还是应该使用递归操作完成。

范例：使用第二种方式设置和取出数据

public class LinkDemo {
	public static void main(String args[]) {
		// 第一步：准备出所有的数据
		Node root = new Node("火车头");
		Node n1 = new Node("车厢A");
		Node n2 = new Node("车厢B");
		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类来指向下一个节点。

---

二、链表基本雏形

通过分析发现：

· 用户在操作的过程之中完全没有必要去关心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;
	}

	// 实现节点的添加
	// 第一次调用(Link)：this = Link.root
	// 第二次调用(Node)：this = link.root.next
	// 第三次调用(Node)：this = link.root.next.next
	public void addNode(Node newNode) {
		if (this.next == null) {// 当前节点下一个为null
			this.next = newNode;// 保存新节点
		} else {// 当前节点之后还存在有节点
				// 当前节点的下一个节点继续保存
			this.next.addNode(newNode);
		}
	}

	// 第一次调用(Link)：this = Link.root
	// 第二次调用(Node)：this = link.root.next
	// 第三次调用(Node)：this = link.root.next.next
	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 {// 根节点已经存在了
			// 随后后面增加的元素应该交由节点来决定
			// 从root节点之后找到合适的位置
			this.root.addNode(newNode);
		}
	}

	public void print() {// 输出数据
		if (this.root != null) {// 现在存在根节点
			this.root.printNode();
		}
	}

}

public class LinkDemo {
	public static void main(String args[]) {
		Link link = new Link();// 由这个类负责所有的数据操作
		link.add("Hello");// 存放数据
		link.add("World");// 存放数据
		link.add("Hello");// 存放数据
		link.print();// 展示数据
	}
}

通过以上代码实际上就可以发现链表的基本操作特点：

• 客户端代码不用去关注具体的Node以及引用关系的细节，只关注于提供的Link类中支持的方法；
• Link类的主要功能是控制Node类对象的产生和根节点；
• Node类主要负责数据的保存以及引用关系的分配。

---

三、开发可用链表

指的是可以使用链表实现数据的增加、修改、删除、查询操作。

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;
		}
	}

	// ==========以上为内部类===========
	private Node root;// 需要根节点
}

而随后主要就是进行代码的填充以及功能的完善。

---

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) {
		Node newNode = new Node(data);
		if (data == null) {// 假设不允许有空
			return;
		}
		if (this.root == null) {// 当前没有根节点
			this.root = newNode;// 保存根节点
		} else {// 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
	}
}

public class LinkDemo {
	public static void main(String args[]) {
		Link all = new Link();
		all.add("Hello");
		all.add("World");
		all.add(null);
	}
}

此时使用了一个不许为null的判断，但并不是所有的链表都不许为null。

---

3、取得保存元素个数：public int size()

既然每一个链表对象都只有一个root根元素，那么每一个链表就有自己的长度，可以直接在Link类里面设置一个count属性，随后每一次数据添加完成之后，可以进行个数的自增。

范例：修改Link.java类

· 增加一个count属性；

private int count;//保存元素的个数

· 在add()方法里面增加数据的统计操作；

	private Node root;// 需要根节点
	private int count;// 保存元素的个数

	public void add(String data) {
		Node newNode = new Node(data);
		if (data == null) {// 假设不允许有空
			return;
		}
		if (this.root == null) {// 当前没有根节点
			this.root = newNode;// 保存根节点
		} else {// 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
		this.count++;// 每一次保存完成之后数据量加1
	}

· 随后为Link类增加一个新的方法：size()

	public int size() {// 取得保存的数据量
		return this.count;
	}

本程序之中null不会被保存。

---

4、判断是否是空链表（size()==0）:public boolean isEmpty()

空链表的判断实际上可以通过两种方式完成：

• 第一种：判断root有对象（是否为null）；
• 第二种：判断保存的数据量（count）。

范例：判断是否为空链表

	public boolean isEmpty() {
		return this.count == 0;
	}

本次是一个链表组成内部的剖析，所以一些简单的代码一定要清楚实现原理。

---

5、数据查询：public boolean contains(数据类型 变量)

在链表之中一定会保存有多个数据，那么基本的判断数据是否存在的方式。以：String为例。循环链表中的内容，并且与要查询的数据进行匹配（equals()），如果查找到了，则返回true，否则返回false。

范例：修改Link类

	public boolean contains(String data) {
		// 现在没有要查询的数据，根节点也不保存数据
		if (data == null || this.root == null) {
			return false;// 没有查询结果
		}
		return this.root.containsNode(data);
	}

从根元素查询数据是否存在。

范例：在Node类中增加方法

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		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;
				}
			}
		}

范例：定义测试程序

public class LinkDemo {
	public static void main(String args[]) {
		Link all = new Link();
		all.add("Hello");
		all.add("World");
		all.add(null);
		System.out.println(all.contains("Hello"));
		System.out.println(all.contains("d"));
	}
}

本次使用的是String型数据，所以判断数据的时候使用的是equals方法，可是如果现在要传递的是一个自定义对象呢？需要定义一个对象比较的方法（暂时将方法名称定义为compare()）。

---

6、根据索引取得数据：public 数据类型 get(int index)

通过以上的代码测试可以发现，链表里面保存了多个String类对象，在程序里面只有数组可以保存多个对象，现在使用的链表与数组相比较的话，优势就是没有长度限制，所以链表严格意义上来讲就是一个动态对象，那么既然链表属于动态对象数组，那么也应该具备像数组那样可以根据索引取得元素的功能。

由于是动态对象数组，所以数组中的每一个元素的索引的内容都一定是动态生成的。

范例：在Link类里面增加一个foot的属性，表示每一个Node元素的编号

private int foot;

范例：在每一次查询的时候（一个链表可能查询多次），那么foot应该在每一次查询的时候都从头开始。

但是千万要记住，如果有内容，或者是要查询的索引小于个数。

	public String get(int index) {
		if (index > this.count) {// 超过了查询范围
			return null;// 没有数据
		}
		this.foot = 0;// 表示从前向后查询
		return this.root.getNode(index);// 将查询过程交给Node类
	}

范例：在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;// 结束方法调用
		}
		this.foot = 0;// 重新设置foot属性的内容，作为索引出现
		this.root.setNode(index, data);// 交给Node类设置数据内容
	}

 

范例：在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应该变为“根节点.next”，Link类才关心根节点，此种情况要在Link类中进行处理;
•  情况二：要删除的是普通节点，应该在Node类里处理，此处是从第二个节点开始判断的。删除数据的最终的形式“当前节点上一个节点.next = 当前节点.next”，即：空出了当前节点。

范例：在Node类里面增加一个removeNode()方法，此方法专门处理普通节点。

		// 第一次调用(Link)：previous = Link.root、this = Link.root.next
		// 第二次调用(Node)：previous = Link.root.next、
this = Link.root.next.next
		// 要传递上一个节点以及要删除的数据
		public void removeNode(Node previous, String data) {
			if (data.equals(this.data)) {// 当前节点为要删除节点
				previous.next = this.next;// 空出当前节点
			} else {// 应该向后继续查询
				this.next.removeNode(this, data);
			}
		}

范例：在Link类里面增加根节点的判断

	public void remove(String data) {
		if (this.contains(data)) {// 主要功能是判断数据是否存在
			// 要删除数据是否是根节点数据
			// root是Node类的对象，此处直接访问了内部类的私有操作
			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类的toArray()方法一定要返回一个对象数组，并且这个对象数组也一定要被Node类操作，那么这个对象数组最好定义在Link类的属性里面。

范例：修改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();// 交给Node类处理
		return this.retArray;
	}

范例：在Node类里面处理数组数据的保存

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		public void toArrayNode() {
			Link.this.retArray[Link.this.foot++] = this.data;
			if (this.next != null) {// 有后续元素
				this.next.toArrayNode();
			}
		}

实现的前提：内部类与外部类之间可以直接进行私有属性的访问。

链表数据变为对象数组取出是最为重要的功能。

---

四、使用链表

以上所给出的链表严格来讲不能够使用，而且意义也不大，因为它所能够操作的数据类型只有String，毕竟String所保留的数据比较少，所以可以采用自定义类来进行链表的操作。

由于链表中要保存的对象需要实现contains()、remove()等功能，所以在类中要提供有对象比较方法的支持。

范例：定义一个保存图书信息的类

class Book {
	private String title;
	private double price;

	public Book(String title, double price) {
		this.title = title;
		this.price = price;
	}

	public String getInfo() {
		return "名称：" + this.title + "，价格：" + this.price;
	}

	public boolean compare(Book book) {
		if (this == book) {
			return true;
		}
		if (book == null) {
			return false;
		}
		if (this.title.equals(book.title) && this.price == book.price) {
			return true;
		} else {
			return false;
		}
	}
}

范例：修改链表实现

class Link {// 链表类，外部只能看见这一个
	// 之所以定义在内部，主要是让其为Link类服务
	private class Node {// 定义的节点类
		private Book data;// 保存数据
		private Node next;// 引用关系

		public Node(Book data) {
			this.data = data;
		}

		public void addNode(Node newNode) {
			if (this.next == null) {// 当前的下一个节点为空
				this.next = newNode;
			} else {// 向后继续保存
				this.next.addNode(newNode);
			}
		}

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		public boolean containsNode(Book data) {
			if (data.compare(this.data)) {// 当前节点数据为要查询的数据
				return true;// 后面不再查询了
			} else {// 当前节点数据不满足查询条件
				if (this.next != null) {// 有后续节点
					return this.next.containsNode(data);
				} else {// 没有后续节点
					return false;
				}
			}
		}

		public Book getNode(int index) {
			// 使用当前的foot内容与要查询的索引进行比较
			// 随后将foot的内容自增，目的是为了下次查询方便
			if (Link.this.foot++ == index) {// 要查询的索引
				return this.data;// 返回当前节点数据
			} else {// 现在应该继续向后查询
				return this.next.getNode(index);
			}
		}

		public void setNode(int index, Book data) {
			if (Link.this.foot++ == index) {
				this.data = data;// 进行内容的修改
			} else {
				this.next.setNode(index, data);
			}
		}

		// 第一次调用(Link)：previous = Link.root、this = Link.root.next
		// 第二次调用(Node)：previous = Link.root.next、this = Link.root.next.next
		// 要传递上一个节点以及要删除的数据
		public void removeNode(Node previous, Book data) {
			if (data.compare(this.data)) {// 当前节点为要删除节点
				previous.next = this.next;// 空出当前节点
			} else {// 应该向后继续查询
				this.next.removeNode(this, data);
			}
		}

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		public void toArrayNode() {
			Link.this.retArray[Link.this.foot++] = this.data;
			if (this.next != null) {// 有后续元素
				this.next.toArrayNode();
			}
		}
	}

	// ==========以上为内部类===========
	private Node root;// 需要根节点
	private int count;// 保存元素的个数
	private int foot;
	private Book[] retArray;// 返回的数组

	public void add(Book data) {
		Node newNode = new Node(data);
		if (data == null) {// 假设不允许有空
			return;
		}
		if (this.root == null) {// 当前没有根节点
			this.root = newNode;// 保存根节点
		} else {// 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
		this.count++;// 每一次保存完成之后数据量加1
	}

	public int size() {// 取得保存的数据量
		return this.count;
	}

	public boolean isEmpty() {
		return this.count == 0;
	}

	public Book get(int index) {
		if (index > this.count) {// 超过了查询范围
			return null;// 没有数据
		}
		this.foot = 0;// 表示从前向后查询
		return this.root.getNode(index);// 将查询过程交给Node类
	}

	public boolean contains(Book data) {
		// 现在没有要查询的数据，根节点也不保存数据
		if (data == null || this.root == null) {
			return false;// 没有查询结果
		}
		return this.root.containsNode(data);
	}

	public void set(int index, Book data) {
		if (index > this.count) {
			return;// 结束方法调用
		}
		this.foot = 0;// 重新设置foot属性的内容，作为索引出现
		this.root.setNode(index, data);// 交给Node类设置数据内容
	}

	public void remove(Book data) {
		if (this.contains(data)) {// 主要功能是判断数据是否存在
			// 要删除数据是否是根节点数据
			// root是Node类的对象，此处直接访问了内部类的私有操作
			if (data.equals(this.root.data)) {// 为要删除节点
				this.root = this.root.next;// 空出当前节点
			} else {// 不是根元素
					// 此时根元素已经判断过了，从第二个元素开始判断
				this.root.next.removeNode(this.root, data);

			}
			this.count--;// 个数减少
		}
	}

	public Book[] toArray() {
		if (this.root == null) {
			return null;
		}
		this.foot = 0;// 需要脚标控制
		this.retArray = new Book[this.count];// 根据保存内容开辟数组
		this.root.toArrayNode();// 交给Node类处理
		return this.retArray;
	}
}

范例：实现测试

public class LinkDemo {
	public static void main(String args[]) {
		Link all = new Link();
		all.add(new Book("Java", 56.3));
		all.add(new Book("Android", 65.3));
		all.add(new Book("Oracle", 67.3));
		System.out.println("保存书的个数：" + all.size());
		System.out.println(all.contains(new Book("Java", 56.3)));
		all.remove(new Book("Oracle", 67.3));
		Book[] books = all.toArray();
		for (int x = 0; x < books.length; x++) {
			System.out.println(books[x].getInfo());
		}
	}
}

虽然以上的代码麻烦（如果不让你写链表，只使用方法），那么就可以发现，此时的程序没有了长度的限制，因为是在内存里面保存的，如果存放的太多了，那么你的程序就会变慢。

链表最好的使用就是横向替代掉对象数组。

---

五、在关系中使用链表

链表就是动态对象数组，那么在之前进行数据表映射的时候（本次只以一对多为主），都会出现对象数组的概念，现在就可以利用链表来实现对象数组的保存。

对于任何一个要使用链表的类而言，一定要提供有对象比较的方法。

class Province {
	private int pid;
	private String name;
	private Link cities = new Link();

	public Province(int pid, String name) {
		this.pid = pid;
		this.name = name;
	}

	public boolean Compare(Province province) {
		if (this == province) {
			return true;
		}
		if (province == null) {
			return true;
		}
		if (this.pid == province.pid && this.name.equals(province.name)) {
			return true;
		} else {
			return false;
		}
	}

	public Link getCities() {
		return this.cities;
	}

	public String getInfo() {
		return "省份编号：" + this.pid + "，省份名称：" + this.name;
	}
}

class City {
	private int cid;
	private String name;
	private Province province;

	public City(int cid, String name) {
		this.cid = cid;
		this.name = name;
	}

	public void setProvince(Province province) {
		this.province = province;
	}

	public Province getProvince() {
		return this.province;
	}

	public String getInfo() {
		return "城市编号：" + this.cid + "，城市名称：" + this.name;
	}

	public boolean Compare(City city) {
		if (this == city) {
			return true;
		}
		if (city == null) {
			return true;
		}
		if (this.cid == city.cid && this.name.equals(city.name) && this.province.Compare(city.province)) {
			return true;
		} else {
			return false;
		}
	}
}

class Link {// 链表类，外部只能看见这一个
	// 之所以定义在内部，主要是让其为Link类服务
	private class Node {// 定义的节点类
		private City data;// 保存数据
		private Node next;// 引用关系

		public Node(City data) {
			this.data = data;
		}

		public void addNode(Node newNode) {
			if (this.next == null) {// 当前的下一个节点为空
				this.next = newNode;
			} else {// 向后继续保存
				this.next.addNode(newNode);
			}
		}

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		public boolean containsNode(City data) {
			if (data.Compare(this.data)) {// 当前节点数据为要查询的数据
				return true;// 后面不再查询了
			} else {// 当前节点数据不满足查询条件
				if (this.next != null) {// 有后续节点
					return this.next.containsNode(data);
				} else {// 没有后续节点
					return false;
				}
			}
		}

		public City getNode(int index) {
			// 使用当前的foot内容与要查询的索引进行比较
			// 随后将foot的内容自增，目的是为了下次查询方便
			if (Link.this.foot++ == index) {// 要查询的索引
				return this.data;// 返回当前节点数据
			} else {// 现在应该继续向后查询
				return this.next.getNode(index);
			}
		}

		public void setNode(int index, City data) {
			if (Link.this.foot++ == index) {
				this.data = data;// 进行内容的修改
			} else {
				this.next.setNode(index, data);
			}
		}

		// 第一次调用(Link)：previous = Link.root、this = Link.root.next
		// 第二次调用(Node)：previous = Link.root.next、this = Link.root.next.next
		// 要传递上一个节点以及要删除的数据
		public void removeNode(Node previous, City data) {
			if (data.Compare(this.data)) {// 当前节点为要删除节点
				previous.next = this.next;// 空出当前节点
			} else {// 应该向后继续查询
				this.next.removeNode(this, data);
			}
		}

		// 第一次调用(Link)：this = Link.root
		// 第二次调用(Node)：this = Link.root.next
		public void toArrayNode() {
			Link.this.retArray[Link.this.foot++] = this.data;
			if (this.next != null) {// 有后续元素
				this.next.toArrayNode();
			}
		}
	}

	// ==========以上为内部类===========
	private Node root;// 需要根节点
	private int count;// 保存元素的个数
	private int foot;
	private City[] retArray;// 返回的数组

	public void add(City data) {
		Node newNode = new Node(data);
		if (data == null) {// 假设不允许有空
			return;
		}
		if (this.root == null) {// 当前没有根节点
			this.root = newNode;// 保存根节点
		} else {// 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
		this.count++;// 每一次保存完成之后数据量加1
	}

	public int size() {// 取得保存的数据量
		return this.count;
	}

	public boolean isEmpty() {
		return this.count == 0;
	}

	public City get(int index) {
		if (index > this.count) {// 超过了查询范围
			return null;// 没有数据
		}
		this.foot = 0;// 表示从前向后查询
		return this.root.getNode(index);// 将查询过程交给Node类
	}

	public boolean contains(City data) {
		// 现在没有要查询的数据，根节点也不保存数据
		if (data == null || this.root == null) {
			return false;// 没有查询结果
		}
		return this.root.containsNode(data);
	}

	public void set(int index, City data) {
		if (index > this.count) {
			return;// 结束方法调用
		}
		this.foot = 0;// 重新设置foot属性的内容，作为索引出现
		this.root.setNode(index, data);// 交给Node类设置数据内容
	}

	public void remove(City data) {
		if (this.contains(data)) {// 主要功能是判断数据是否存在
			// 要删除数据是否是根节点数据
			// root是Node类的对象，此处直接访问了内部类的私有操作
			if (data.equals(this.root.data)) {// 为要删除节点
				this.root = this.root.next;// 空出当前节点
			} else {// 不是根元素
					// 此时根元素已经判断过了，从第二个元素开始判断
				this.root.next.removeNode(this.root, data);

			}
			this.count--;// 个数减少
		}
	}

	public City[] toArray() {
		if (this.root == null) {
			return null;
		}
		this.foot = 0;// 需要脚标控制
		this.retArray = new City[this.count];// 根据保存内容开辟数组
		this.root.toArrayNode();// 交给Node类处理
		return this.retArray;
	}
}

public class LinkDemo {
	public static void main(String args[]) {
		Province pro = new Province(1, "河北省");
		City c1 = new City(1001, "唐山");
		City c2 = new City(1002, "秦皇岛");
		City c3 = new City(1003, "石家庄");
		c1.setProvince(pro);
		c2.setProvince(pro);
		c3.setProvince(pro);
		pro.getCities().add(c1);
		pro.getCities().add(c2);
		pro.getCities().add(c3);
		System.out.println(pro.getInfo());
		System.out.println("拥有的城市数量：" + pro.getCities().size());
		pro.getCities().remove(c1);
		City c[] = pro.getCities().toArray();
		for (int x = 0; x < c.length; x++) {
			System.out.println(c[x].getInfo());
		}
	}
}

本程序不再受到数组长度的限制，但是新的问题：如果真按照这样的方式去编写代码，会造成只要有一个简单Java类，那么就需要定义一个链表。

方法解决的是代码的重复问题，但是以上并不属于代码的重复，属于数据类型的不统一，所以这个时候我们在之前所学习到的知识就不足以来解决此类问题。