# 第 13 节 链表的定义与使用

***

1、本次的操作属于引用部分的加强应用，所以在此部分里面有两点需要依赖：

* 依赖于引用传递问题
* this表示当前对象

2、链表的实现的基本模式；

3、开发并且使用可用链表。

## 链表的基本形式

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

![](/files/-M51Q9r4FvXvEAJP2pn3)

**范例：** 定义一个Node类

* 假设本次保存的数据是String型数据，同时拥有下一个引用；

```java
// 每一个链表实际上就是由多个节点所组成的
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的关系匹配。

**范例：** 使用第一种形式设置和取出数据

```java
public class MainClass {
    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();
        }
    }
}
```

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

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

```java
public class MainClass {
    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类是否存在；
* 所有的节点的引用关系不应该由用户处理，应该有一个专门的工具类来进行处理

下面需要定义一个类，来帮助客户端去隐藏所有的链表中给出的细节操作。

![](/files/-M51Q9r7IMB0kfsO_y2p)

**范例：** 链表的基本形式

```java
// 每一个链表实际上就是由多个节点所组成的
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) { // 当前节点的下一个为空
            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(); // 交给Node类输出
        }
    }
}
public class MainClass {
    public static void main(String[] args) {
        Link link = new Link(); // 由这个类负责所有的数据操作
        link.add("Hello"); // 存放数据
        link.add("World");
        link.add("haha");
        link.add("nihao");
        link.print(); // 展示数据
    }
}
```

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

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

## 开发可用链表

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

## 程序基本结构

在开发具体的可用链表之前，首先必须明确一个道理：Node类负责所有的节点数据的保存以及节点关系的匹配。所以Node类不可能单独的去使用，而以上的实现里面Node是可以单独使用的，外部可以绕过Link类直接操作Node类，这种操作明显是没有任何意义的。所以下面必须修改设计结构，让Node类只能够被Link类使用。

这个时候使用内部类是一个最好的选择。内部类可以使用private定义，这样一个内部类只能够被一个外部类使用，并且，内部类可以方便的与外部类之间进行私有属性的直接访问。

**范例：** 链表的开发结构

```java
class Link { // 链表类，外部能够看见的只有这一个类
    // 让其为Link类服务
    private class Node { // 定义的节点类
        private String data;
        private Node next;
        public Node(String data) {
            this.data = data;
        }
    }
    // ========================= 以上为内部类 =========================
    private Node root; // 需要根节点
}
```

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

## 数据增加：public void add(数据类型 变量)

如果要进行新数据的增加，则应该由Link类负责节点对象的产生，并且由Link类维护根节点，所有的节点关系匹配交给Node类处理。

```java
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) { // 假设不允许有null
        if (data == null) {
            return ;
        }
        Node newNode = new Node(data); // 要保存的数据
        if (this.root == null) { // 当前没有根节点
            this.root = newNode; // 保存根节点
        } else { // 根节点存在，其他节点交给Node类处理
            this.root.addNode(newNode);
        }
    }
}
public class MainClass {
    public static void main(String[] args) {
        Link all = new Link();
        all.add("Hello");
        all.add("World");
        all.add(null);
    }
}
```

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

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

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

**范例：** 修改Link类

* 增加count属性

```java
private int count = 0; // 保存元素的个数
```

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

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

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

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

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

## 判断空链表：public boolean isEmpty()

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

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

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

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

## 数据查询：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类增加方法

```java
// 第一次调用（Link）：this = Link.root
// 第二次调用（Node）：this = Link.root.next
// 第三次调用（Node）：this = Link.root.next.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;
        }
    }
}
```

**范例：** 定义测试程序

```java
public class MainClass {
    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("heihei"));
    }
}
```

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

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

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

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

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

```java
private int foot = 0;
```

**范例：** 在每一次查询的时候（一个链表可能查询多次），那么foot应该在每一次查询时都从头开始；但是一定要注意查询的前提：root存在，并且要查询的索引小于链表个数。

```java
public String get(int index) {
	if (index >= this.count) { // 操过了查询范围（索引从0开始）
		return null; // 没有数据
	}
	this.foot = 0; // 表示从前向后查询
	return this.root.getNode(index); // 将查询过程交给Node类处理
}
```

**范例：** 在Node类里面实现getNode()方法，内部类和外部类之间可以互相进行私有属性的访问。

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

## 修改指定索引内容：public void set(int index, 数据类型 变量)

修改数据和查询数据区别不大，查询的时候当满足索引值得时候只是进行了一个数据的返回，那么此处只需要将数据返回变为数据的重新赋值即可。

**范例：** 在Link类里面增加set()方法

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

**范例：** 在Node类里面增加setNode()方法

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

## 数据删除：public void remove(数据类型 变量)

对于删除数据而言，可以分为两种情况：

* 情况一：要删除的数据是根节点，则root应该变为“根节点.next”，由于root是由Link类进行维护，所以此操作应该在Link类中定义;
* 情况二：要删除的是普通节点，应该在Node类中处理。删除数据的最终形式：当前节点上一节点.next = 当前节点.next，即：空出了当前节点。

**范例：** 在Node类里面增加一个removeNode()方法，此方法专门处理非根节点的删除

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

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

```java
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 -- ; // 统计个数减少
	}
}
```

## 将链表变为对象数组：public 数据类型\[] toArray()

任何情况下，不管是什么样的类都不可能在类中使用输出语句，想要输出数据，一定要将数据返回到调用处进行输出，而链表属于动态对象数组，所以此处最好的做法是将链表以对象数组的形式返回。

Link类的toArray()方法一定要返回一个对象数组，并且这个对象数组一定要被Node类操作，那么这个对象数组最好定义在Link类的属性里面。

**范例：** 修改Link类的定义

* 增加一个返回的数组属性内容，之所以将其定义为属性，是因为内部类和外部类都可以访问；

```java
private String[] retArray; // 返回的数组
```

* 增加toArray()方法

```java
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类里面处理数组数据的保存

```java
// 第一次调用（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()等功能，所以在类中要提供有对象比较方法的支持。

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

```java
class Book {
	private String title;
	private double price;
	public Book(String title, double price) {
		this.title = title;
		this.price = price;
	}
	public boolean compare(Book book) {
		if (this == book)
			return true;
		if (book == null)
			return false;
		if (this.price == book.price && this.title.equals(book.title))
			return true;
		return false;
	}
	public String getInfo() {
		return "title=" + title + ", price=" + price;
	}
}
```

**范例：** 修改链表实现

```java
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
		// 第三次调用（Node）：this = Link.root.next.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);
			}
		}
		// 要传递上一个节点以及要删除的数据
		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 = 0; // 保存元素的个数
	private int foot = 0;
	private Book[] retArray; // 返回的数组
	public void add(Book data) { // 假设不允许有null
		if (data == null) {
			return ;
		}
		Node newNode = new Node(data); // 要保存的数据
		if (this.root == null) { // 当前没有根节点
			this.root = newNode; // 保存根节点
		} else { // 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
		this.count ++; // 每一次保存完成后数据量加一
	}
	public int size() { // 取得保存的数据量
		return this.count;
	}
	public boolean isEmpty() {
		return this.count == 0;
	}
	public boolean contains(Book data) {
		// 没有要查询的数据，也不存在根节点
		if (data == null || this.root == null) {
			return false; // 没有查询结果
		}
		return this.root.containsNode(data);
	}
	public Book get(int index) {
		if (index >= this.count) { // 操过了查询范围（索引从0开始）
			return null; // 没有数据
		}
		this.foot = 0; // 表示从前向后查询
		return this.root.getNode(index); // 将查询过程交给Node类处理
	}
	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)) { // 判断数据是否存在
			// 判断要删除的数据是否是根节点的数据
			if (data.compare(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;
	}
}
```

**范例：** 实现测试

```java
public class MainClass {
	public static void main(String[] args) {
		Link all = new Link();
		all.add(new Book("Java", 12.8));
		all.add(new Book("Oracle", 13.8));
		all.add(new Book("Linux", 14.8));
		System.out.println("保存书的个数：" + all.size());
		System.out.println(all.contains(new Book("Java", 12.8)));
		all.remove(new Book("Oracle", 13.8));
		Book[] books = all.toArray();
		for (int i = 0; i < books.length; i ++) {
			System.out.println(books[i].getInfo());
		}
	}
} 
```

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

## 在关系中使用链表

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

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

```java
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 false;
    	if (this.pid == province.pid && this.name.equals(province.name))
    		return true;
    	return false;
    }
    public Link getCities() {
        return this.cities;
    }
    public String getInfo() {
        return "pid=" + pid + ", name=" + 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 boolean compare(City city) {
    	if (this == city)
    		return true;
    	if (city == null)
    		return false;
    	if (this.cid == city.cid && this.name.equals(city.name) 
    			&& this.province.compare(city.province)) 
    		return true;
    	return false;
    }
    public void setProvince(Province province) {
        this.province = province;
    }
    public Province getProvince() {
        return this.province;
    }
    public String getInfo() {
        return "cid=" + cid + ", name=" + name;
    }
}
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
		// 第三次调用（Node）：this = Link.root.next.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);
			}
		}
		// 要传递上一个节点以及要删除的数据
		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 = 0; // 保存元素的个数
	private int foot = 0;
	private City[] retArray; // 返回的数组
	public void add(City data) { // 假设不允许有null
		if (data == null) {
			return ;
		}
		Node newNode = new Node(data); // 要保存的数据
		if (this.root == null) { // 当前没有根节点
			this.root = newNode; // 保存根节点
		} else { // 根节点存在，其他节点交给Node类处理
			this.root.addNode(newNode);
		}
		this.count ++; // 每一次保存完成后数据量加一
	}
	public int size() { // 取得保存的数据量
		return this.count;
	}
	public boolean isEmpty() {
		return this.count == 0;
	}
	public boolean contains(City data) {
		// 没有要查询的数据，也不存在根节点
		if (data == null || this.root == null) {
			return false; // 没有查询结果
		}
		return this.root.containsNode(data);
	}
	public City get(int index) {
		if (index >= this.count) { // 操过了查询范围（索引从0开始）
			return null; // 没有数据
		}
		this.foot = 0; // 表示从前向后查询
		return this.root.getNode(index); // 将查询过程交给Node类处理
	}
	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)) { // 判断数据是否存在
			// 判断要删除的数据是否是根节点的数据
			if (data.compare(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 MainClass {
	public static void main(String[] args) {
		Link all = new Link();
		// 第一步：设置关系数据
		// 1、先准备好各自独立的对象
        Province pro = new Province(1, "Shaan xi");
        City c1 = new City(1001, "Xi'an");
        City c2 = new City(1002, "Baoji");
        City c3 = new City(1003, "Xianyang");
        // 2、设置关系
        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(c3);
        City[] c = pro.getCities().toArray();
        for (int i = 0; i < c.length; i ++) {
        	System.out.println(c[i].getInfo());
        }
	}
}
```

本程序不再受到长度的限制，但是会出现一个新的问题：对于每一个新的类都要定义一个新的属于该类的Link类。

方法解决的是代码的重复问题，但是以上问题并不属于代码的重复，而是属于数据类型的不统一，所以之前学习到的内容就不足以解决这个问题。

### 总结

1、链表本次讲解的知识一个最基础的单项链表；

2、熟记以下方法的名称以及作用；

| No. |                 方法名称                |  类型 |           描述          |
| :-: | :---------------------------------: | :-: | :-------------------: |
|  1  |       public void add(数据类型 变量)      |  普通 |      向链表之中增加新的数据      |
|  2  |          public int size()          |  普通 |     取得链表中保存的元素的个数     |
|  3  |       public boolean isEmpty()      |  普通 | 判断是否是空链表（size() == 0） |
|  4  |   public boolean contains(数据类型 变量)  |  普通 |      判断某一个数据是否存在      |
|  5  |      public 数据类型 get(int index)     |  普通 |        根据索引取得数据       |
|  6  | public void set(int index, 数据类型 变量) |  普通 |       更新指定索引的数据       |
|  7  |     public void remove(数据类型 变量)     |  普通 |  删除指定数据，如果是对象则要进行对象比较 |
|  8  |       public 数据类型\[] toArray()      |  普通 |     将链表以对象数组的形式返回     |

3、本次讲解的链表是日后进行Java类集学习的前期原理分析。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://shepherd-xie.gitbook.io/be-a-javaer/di-2-zhang-java-mian-xiang-dui-xiang-bian-cheng/section-13.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.