Java基础学习10之链表 链表 链表基本的结构 链表实现结

发表于

链表

「这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战」。

关于作者

  • 作者介绍

🍓 博客主页：作者主页

🍓 简介：JAVA领域优质创作者🥇、一名在校大三学生🎓、在校期间参加各种省赛、国赛，斩获一系列荣誉🏆。

🍓 关注我：关注我学习资料、文档下载统统都有，每日定时更新文章，励志做一名JAVA资深程序猿👨‍💻。

链表是一种基本的数据结构，但好似对于数据结构的部分，强调一下几点：

  1. 在整个Java开发领域之中，没有一本书去真正讲解数据结构的书，只能去看C语言的数据结构：
  2. 在所有开发之中，都会存在数据结构的身影，可以这样去解释：数据结构的精通与否，完全决定于以后。
  3. 数据结构的核心：引用数据类型操作。

链表实际上可以理解为遗传数据，或者按照专业性的说法，可以理解为动态的对象数组，对象数组的最大优点：是表示“多”的概念，例如：多个雇员。但是传统的对象数组有一个最大的问题在于，里面保存的数据长度是固定的。思考：如果现在想要扩大一个对象数组的范围？

建立一个新的对象数组，而后将原本的内容拷贝到新的数组之中，再改变原数组的引用方式。

1
2
3
4
5
java复制代码public class TestLinkDemo{
	public static void main(String args[]){
		Object ob[] = new Object [3];
	}
}

但是再实际的开发之中，要面临的一个问题是：数组是一个定长的线性结构，也就是说虽然以上代码可以满足于存放多个内容，但是一旦我们呢的内容不足或者是内容过多，可能会导致资源的浪费。要想解决此类问题最好的做法就是不定义一个固定长度的数组 ，有多少数据就保存多少数据。

链表基本的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
java复制代码class Node{//因为只有Node类才可以在保存数据的同时设置数据
	private Object data;//真正要保存的数据
	private Node next;//定义下一个节点
	public Node(Object data){
		this.data = data;
	}
	public void setData(Object data){
		this.data = data;
	}
	public Object getData(){
		return this.data;
	}
	public void setNext(Node next){
		this.next = next;
	}
	public Node getNext(){
		return this.next;
	}
}
public class TestLinkDemo{
	public static void main(String args[]){
		//1.封装几个节点
		Node root = new Node("火车头");
		Node n1 = new Node("车厢1");
		Node n2 = new Node("车厢2");
		Node n3 = new Node("车厢3");
		//2.设置节点关系
		root.setNext(n1);
		n1.setNext(n2);
		n2.setNext(n3);
		//3.输出链表
		print(root);
	}
	public static void print(Node node){
		if(node != null){//表示当前是有节点的
			System.out.println(node.getData());
			print(node.getNext());//继续向下取出
		}
		
	}
}

在整个链表的实现过程中，Node类的作用：保存数据和保存下一个节点，但是我们发现客户端需要自己来进行节点的创建操作以及关系的配置。所谓的链表就是需要有一个单独的类，假设叫Link，通过Link类来实现Node的数据保存和关系处理。

链表实现结构说明

通过之前的分析，可以发现链表的最大作用类就是Node，但是以上程序都是由用户自己去匹配节点关系的，但是这些节点的匹配工作不应该由用户完成，应该由一个程序专门去负责。

那么专门负责几点操作的类，就成为链表类——Link,负责处理几点关系，而用户不用关心节点的问题，只需关心Link的处理操作即可。

image-20210809111013328

真实开发——标准过程

image-20210809111231614

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码class Link{//负责对链表的操作
	//将Node定义内部类，表示Node类只能为Link类提供服务
	private class Node{//负责数据与节点的关系匹配
		private Object data;//真正要保存的数据
		private Node next;//定义下一个节点
		public Node(Object data){
			this.data = data;
		}
		public void setData(Object data){
			this.data = data;
		}
		public Object getData(){
			return this.data;
		}	
	}
	//以下为Link类
}
public class TestLinkDemo{
	public static void main(String args[]){
		
	}
}

增加链表数据—public void add(数据)

通过上面程序的分析，可以发下，对于链表的实现，Node类是整个操作的关键，但是首先来研究一下之前程序的问题：Node是一个单独的类是可以被用户直接使用的，但是这个类由用户直接去使用，没有任何意义，即：这个类有用，但不能让用户去使用，让Link类去使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
java复制代码class Link{//负责对链表的操作
	//将Node定义内部类，表示Node类只能为Link类提供服务
	private class Node{//负责数据与节点的关系匹配
		private Object data;//真正要保存的数据
		private Node next;//定义下一个节点
		public Node(Object data){
			this.data = data;
		}
		public void setData(Object data){
		this.data = data;
		}
		public Object getData(){
			return this.data;
		}
		public void setNext(Node next){
			this.next = next;
		}
		public Node getNext(){
			return this.next;
		}
		//第一次调用：this = Link.root
		//第二次调用：this = Link.root.next
		//第三次调用：this = Link.root.next.next
		public void addNode(Node newNode){//处理节点关系
			if(this.next == null){ //当前节点下一个为空
				this.next = newNode;
			}else{//当前节点的下一个不为空
				this.next.addNode(newNode);
			}
		}
		public void nodePrint(){
				System.out.println(this.getData());
				if (this.getNext()==null)
				{
					return;
				}else{
					this.getNext().nodePrint();
				}
			}	
	}
	//以下为Link类------------------------------------------------
	private Node root; //属于根节点，没有根节点就无法数据的保存
	//增加数据
	public void add(Object data){
		if(data == null){//人为追加规定，不允许存放null值
			return ;//结束方法调用
		}
		//如果要想进行数据的保存，那么必须将数据封装在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){
			return;
		}
		System.out.println(this.root.getData());
		if (this.root.getNext()==null){
			return;
		}
		else{
			this.root.getNext().nodePrint();
		}
	}
}
public class TestLinkDemo1{
	public static void main(String args[]){
		Link link = new Link();
		link.add("Hello");
		link.add("World");
		link.print();
	}
}

增加多个数据—public void addAll(数据数组)

1
2
3
4
5
java复制代码public void addAll(String date[]){
	for(int x = 0;x<date.length;x++){
		this.add(date[x]);
	}
}
2.5 统计数据个数—public int size()

在Link类中定义

1
java复制代码private int count;//统计个数

在增加数据的最后一行添加count++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码public void add(Object data){
    if(data == null){//人为追加规定，不允许存放null值
        return ;//结束方法调用
    }
    //如果要想进行数据的保存，那么必须将数据封装在Node类里面
    //如果没有封装，则无法确认好节点的先后顺序
    Node newNode = new Node(data);
    if(this.root == null){
        this.root = newNode;//第一个节点设置为根节点
    }else{//根节点存在了
        this.root.addNode(newNode);
    }
    count++;
}

链表数据转换为对象数组—public Object[] toArray()

对于链表的这种数据结构，最为关键的是两个操作：删除和取得全部数据。

在Link类中定义一个操作数组的脚标：

1
java复制代码private int foot = 0;

要把数据保存的数组，Link类和Node类都需要使用，那么可以在Link类中定义返回数组，必须以属性的形式出现，只有这样，Node类才可以访问这个数组并进行操作。

1
java复制代码private Object [] retData ; //返回类型

在Link类中增加toArray()方法：

1
2
3
4
5
6
7
8
9
10
java复制代码//链表数据转换为对象数组
public Object[] toArray(){
    if(this.count == 0){
        return null;
    }
    this.retData = new Object[this.count];
    this.root.toArrayNode();
    this.foot = 0;//下表清零操作
    return this.retData;
}

在Node中增加toArrayNode()方法：

1
2
3
4
5
6
java复制代码public void toArrayNode(){
    Link.this.retData[Link.this.foot++] = this.data;
    if(this.next != null){
        this.next.toArrayNode();
    }
}

不过按照以上的方式进行开发，每一次调用toArray()方法，都要重复的进行数据的的遍历，如果在数据没有修改的情况下，这种做法是一种低效的做法，最好的方法是增加一个修改标记，如果发现数据增加了或删除的话，表示要重新遍历数据。

image-20210813171359533

链表查询数据—public boolean contains(查找对象)

现在如果想查询某个数据是否存在，那么基本的操作原理：逐个盘查，盘查的具体对象应该交给Node去完成，前提是：有数据存在。

在Link类之中，增加查询操作：

1
2
3
4
5
6
java复制代码//查找链表的指定数据是否存在
public boolean contains(Object search){
    if(search == null && this.root == null)
        return false;
    return this.root.containsNode(search);
}

在Node类中，完成具体查询，查询流程为：

​ 判断当前节点的内容是否满足于查询内容，如果满足返回ture；

​ 如果当前节点内容不满足，则向后继续查询，如果没有后续节点了，则返回false。

1
2
3
4
5
6
7
8
9
10
java复制代码public boolean containsNode(Object search){
    if(search.equals(this.data))
        return true;
    else{
        if(this.next != null){//判断下一个节点是否为空
            return this.next.containsNode(search);
        }
        return false;
    }
}

根据索引取得数据—public Object get(int index)

在一个链表之中会有多个节点保存数据，现在要求可以取得指定节点的数据。但是在进行这一操作的过程之中，有一个小问题：如果要取得数据的索引超过了数据的保存个数，那么是无法取得的。

​ 在Link类之中增加一个get(int index)方法：

1
2
3
4
5
6
7
8
java复制代码//根据索引取得数据
public Object get(int index){
    if(index >= this.count){
        return null;
    }
    this.foot = 0;
    return this.root.getNode(index);
}

在Node类之中增加一个getNdoe(int index)方法：

1
2
3
4
5
6
7
8
9
java复制代码//第一次this == Link.root
//第二次this == Link.root.next
public Object getNode(int index){
    if(Link.this.foot++ == index){
        return this.data;
    }else{
        return this.next.getNode(index);
    }
}

修改指定索引数据—public void set(int index,Object newData)

如果修改数据只需要进行数据的替换。

在Link类之中增加一个set(int index,Object newData)方法：

1
2
3
4
5
6
7
8
java复制代码//修改指定索引数据
public void set(int index,Object newData){
    if(index >= this.count){
        return ;
    }
    this.foot = 0;
    this.root.setNode(index,newData);
}

在Node类之中增加一个getNode(int index)方法：

1
2
3
4
5
6
7
8
9
java复制代码public void setNode(int index, Object newData){
    if(Link.this.foot ++ == index){//索引相同
        this.data = newData;
    }else{
        if(this.next != null){
            this.next.setNode(index,newData);
        }
    }
}

删除数据—public void remove(数据)

对于链表之中的内容，之前完成的是增加操作和查询操作，但是从链表之中也会存在删除数据的操作，可是删除数据的操作要分为两种情况讨论：

​ 情况一：删除的数据不是根节点，待删节点的上一个next指向待删节点的next。

​ 所有的处理操作应该交给Node进行处理。

​ 情况二：删除的数据是根节点，下一个节点保存为跟节点。

​ 如果删除的是根节点，意味着Link中的根节点的保存需要发生变化，该操作主要在Link中处理。

image-20210813174659850

在Link中增加一个删除remove(Object data)方法

1
2
3
4
5
6
7
8
9
10
11
java复制代码//删除数据
public void remove(Object data){
    if(this.contains(data)){//如果数据存在则进行数据处理
        if(this.root.data.equals(data)){//首先需要判断要删除的数据是否为根节点数据
            this.root = this.root.next;//根节点变为下一个节点
        }else{//不是根节点
            this.root.next.removeNode(this.root,data);
        }
        this.count --;
    }
}

在Node类之中增加一个removeNode(Node previous, Object data)方法：

1
2
3
4
5
6
7
8
9
java复制代码//第一次：this = Link.root.next、previous= Link.root;
//第二次：this = Link.root.next.next、previous= Link.root.next;
public void removeNode(Node previous, Object data){
    if(this.data.equals(data)){//当前节点为要删除的节点
        previous.next = this.next;
    }else{
        this.next.removeNode(this,data);
    }
}

Link链表类模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
java复制代码class Link{//负责链表的操作
//将Node定义内部类，表示Node类只能为Link类提供服务
	private class Node{//负责数据与节点的关系匹配
		private Object data;//真正要保存的数据
		private Node next;//定义下一个节点
		public Node(Object data){
			this.data = data;
		}
		public void setData(Object data){
		this.data = data;
		}
		public Object getData(){
			return this.data;
		}
		public void setNext(Node next){
			this.next = next;
		}
		public Node getNext(){
			return this.next;
		}
		//第一次调用：this = Link.root
		//第二次调用：this = Link.root.next
		//第三次调用：this = Link.root.next.next
		public void addNode(Node newNode){//处理节点关系
			if(this.next == null){ //当前节点下一个为空
				this.next = newNode;
			}else{//当前节点的下一个不为空
				this.next.addNode(newNode);
			}
		}
		public void nodePrint(){
				System.out.println(this.getData());
				if (this.getNext()==null)
				{
					return;
				}else{
					this.getNext().nodePrint();
				}
		}	
		public void toArrayNode(){
			Link.this.retData[Link.this.foot++] = this.data;
			if(this.next != null){
				this.next.toArrayNode();
			}
		}
		public boolean containsNode(Object search){
			if(search.equals(this.data))
				return true;
			else{
				if(this.next != null){//判断下一个节点是否为空
					return this.next.containsNode(search);
				}
				return false;
			}
		}
		//第一次this == Link.root
		//第二次this == Link.root.next
		public Object getNode(int index){
			if(Link.this.foot++ == index){
				return this.data;
			}else{
				return this.next.getNode(index);
			}
		}
		
		public void setNode(int index, Object newData){
			if(Link.this.foot ++ == index){//索引相同
				this.data = newData;
			}else{
				if(this.next != null){
					this.next.setNode(index,newData);
				}
			}
		}
		//第一次：this = Link.root.next、previous= Link.root;
		//第二次：this = Link.root.next.next、previous= Link.root.next;
		public void removeNode(Node previous, Object data){
			if(this.data.equals(data)){//当前节点为要删除的节点
				previous.next = this.next;
			}else{
				this.next.removeNode(this,data);
			}
		}
	}
	//以下为Link类------------------------------------------------
	private Object [] retData ; //返回类型
	private int foot = 0;//操作下标
	private int count;//统计个数
	private Node root; //属于根节点，没有根节点就无法数据的保存
	//增加数据
	public void add(Object data){
		if(data == null){//人为追加规定，不允许存放null值
			return ;//结束方法调用
		}
		//如果要想进行数据的保存，那么必须将数据封装在Node类里面
		//如果没有封装，则无法确认好节点的先后顺序
		Node newNode = new Node(data);
		if(this.root == null){
			this.root = newNode;//第一个节点设置为根节点
		}else{//根节点存在了
			this.root.addNode(newNode);
		}
			count++;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		this.count=0;
		return false;
	}

	//增加多个数据
	public void addAll(String date[]){
		for(int x = 0;x<date.length;x++){
			this.add(date[x]);
		}
	}
	public int size(){
		return this.count;
	}

	//输出数据
	public void print(){
		if (this.root == null){
			return;
		}
		System.out.println(this.root.getData());
		if (this.root.getNext()==null){
			return;
		}
		else{
			this.root.getNext().nodePrint();
		}
	}
	//链表数据转换为对象数组
	public Object[] toArray(){
			if(this.count == 0){
				return null;
			}
			this.retData = new Object[this.count];
			this.root.toArrayNode();
			this.foot = 0;//下表清零操作
			return this.retData;
	}
	//查找链表的指定数据是否存在
	public boolean contains(Object search){
		if(search == null && this.root == null)
			return false;
		return this.root.containsNode(search);
	}
	//根据索引取得数据
	public Object get(int index){
		if(index >= this.count){
			return null;
		}
		this.foot = 0;
		return this.root.getNode(index);
	}
	
	//修改指定索引数据
	public void set(int index,Object newData){
		if(index >= this.count){
			return ;
		}
		this.foot = 0;
		this.root.setNode(index,newData);
	}
	//删除数据
	public void remove(Object data){
		if(this.contains(data)){//如果数据存在则进行数据处理
			if(this.root.data.equals(data)){//首先需要判断要删除的数据是否为根节点数据
				this.root = this.root.next;//根节点变为下一个节点
			}else{//不是根节点
				this.root.next.removeNode(this.root,data);
			}
			this.count --;
		}
	}
}

综合案例

建立宠物商店，包括销售宠物上架、下架、关键字查询，要求程序的关系即可，对于宠物的信息只要有三项：名字、年龄、颜色。

对应的关系：一个宠物商店有多种宠物，如果按照表设计应该属于一对多关系映射，但是现在问题，一方是宠物商店，多方是宠物，但是宠物又分为猫、狗、猪、驴、鱼等。

image-20210813223132675

1、建立宠物标准

1
2
3
4
5
java复制代码interface Pet{//定义宠物
	public String getName();
	public String getColor();
	public int getAge();
}

2、对于宠物商店，只关注于宠物的标准，而不关心具体是那种宠物

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码class PetShop{
	private Link pets = new Link();//开辟一个链表，保存宠物信息
	public void add(Pet pet){//上架宠物
		this.pets.add(pet);
	}
	public void delete(Pet pet){//下架宠物
		this.pets.delete(pet);
	}
	public Link getPets(){	//得到全部宠物
		return this.pets;
	}
	public Link search(String keyword){//关键字查找
		Link result = new Link();
		Object [] data = this.pets.toArray();
		for(int i = 0; i < data.length ; i++){
			Pet pet = (Pet) data[i];
			if(pet.getName().contains(keyword) || pet.getColor().contains(keyword)){
				result.add(pet);	//满足查询结果
			}
		}
		return result;
	}
}

3、定义宠物狗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
java复制代码class Dog implements Pet{
	private String name;
	private String color;
	private int age;
	public String getName(){
		return this.name;
	}
	public String getColor(){
		return this.color;
	}
	public boolean equals(Object obj){
		if(obj == null){
		return false;
		}
		if(this == obj){
			return false;
		}
		if(!(obj instanceof Dog)){
			return false;
		}
		Dog pet = (Dog) obj;
		return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age.equals(pet.age);
	}	
	public int getAge(){
		return this.age;
	}
	public Dog(String name, String color, int age){
		this.name = name ;
		this.color = color;
		this.age = age;
	}
	public String toString(){
		return "【狗】名字 = " + this.name +
				"颜色 = " + this.color + 
				"年龄 = " +this.age;
	}
}

定义宠物猫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
java复制代码class Cat implements Pet{
	private String name;
	private String color;
	private int age;
	public String getName(){
		return this.name;
	}
	public String getColor(){
		return this.color;
	}
	public boolean equals(Object obj){
		if(obj == null){
		return false;
		}
		if(this == obj){
			return false;
		}
		if(!(obj instanceof Cat)){
			return false;
		}
		Cat pet = (Cat) obj;
		return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age.equals(pet.age);
	}	
	public int getAge(){
		return this.age;
	}
	public Cat(String name, String color, int age){
		this.name = name ;
		this.color = color;
		this.age = age;
	}
	public String toString(){
		return "【猫】名字 = " + this.name +
				"颜色 = " + this.color + 
				"年龄 = " +this.age;
	}
}

5、测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java复制代码public class Pets{
	public static void main(String args[]){
		PetShop ps = new PetShop();
		ps.add(new Dog("小黑","黑色",1));
		ps.add(new Dog("金毛","金色",2));
		ps.add(new Dog("拉布拉多","白色",3));
		ps.add(new Dog("萨摩耶","白色",2));
		ps.add(new Cat("加菲猫","黄色",3));
		ps.add(new Dog("波斯猫","金色",4));
		ps.delete(new Dog("萨摩耶","白色",2));
		Link all = ps.search("白");
		Object [] data = all.toArray();
		for(int i = 0 ; i < data.length ; i++){
			System.out.println(data[i]);
		}
		
	}
}

6、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
java复制代码class Link{//负责链表的操作
//将Node定义内部类，表示Node类只能为Link类提供服务
	private class Node{//负责数据与节点的关系匹配
		private Object data;//真正要保存的数据
		private Node next;//定义下一个节点
		public Node(Object data){
			this.data = data;
		}
		public void setData(Object data){
		this.data = data;
		}
		public Object getData(){
			return this.data;
		}
		public void setNext(Node next){
			this.next = next;
		}
		public Node getNext(){
			return this.next;
		}
		//第一次调用：this = Link.root
		//第二次调用：this = Link.root.next
		//第三次调用：this = Link.root.next.next
		public void addNode(Node newNode){//处理节点关系
			if(this.next == null){ //当前节点下一个为空
				this.next = newNode;
			}else{//当前节点的下一个不为空
				this.next.addNode(newNode);
			}
		}
		public void nodePrint(){
				System.out.println(this.getData());
				if (this.getNext()==null)
				{
					return;
				}else{
					this.getNext().nodePrint();
				}
		}	
		public void toArrayNode(){
			Link.this.retData[Link.this.foot++] = this.data;
			if(this.next != null){
				this.next.toArrayNode();
			}
		}
		public boolean containsNode(Object search){
			if(search.equals(this.data))
				return true;
			else{
				if(this.next != null){//判断下一个节点是否为空
					return this.next.containsNode(search);
				}
				return false;
			}
		}
		//第一次this == Link.root
		//第二次this == Link.root.next
		public Object getNode(int index){
			if(Link.this.foot++ == index){
				return this.data;
			}else{
				return this.next.getNode(index);
			}
		}
		
		public void setNode(int index, Object newData){
			if(Link.this.foot ++ == index){//索引相同
				this.data = newData;
			}else{
				if(this.next != null){
					this.next.setNode(index,newData);
				}
			}
		}
		//第一次：this = Link.root.next、previous= Link.root;
		//第二次：this = Link.root.next.next、previous= Link.root.next;
		public void removeNode(Node previous, Object data){
			if(this.data.equals(data)){//当前节点为要删除的节点
				previous.next = this.next;
			}else{
				this.next.removeNode(this,data);
			}
		}
	}
	//以下为Link类------------------------------------------------
	private Object [] retData ; //返回类型
	private int foot = 0;//操作下标
	private int count;//统计个数
	private Node root; //属于根节点，没有根节点就无法数据的保存
	//增加数据
	public void add(Object data){
		if(data == null){//人为追加规定，不允许存放null值
			return ;//结束方法调用
		}
		//如果要想进行数据的保存，那么必须将数据封装在Node类里面
		//如果没有封装，则无法确认好节点的先后顺序
		Node newNode = new Node(data);
		if(this.root == null){
			this.root = newNode;//第一个节点设置为根节点
		}else{//根节点存在了
			this.root.addNode(newNode);
		}
			count++;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		this.count=0;
		return false;
	}

	//增加多个数据
	public void addAll(String date[]){
		for(int x = 0;x<date.length;x++){
			this.add(date[x]);
		}
	}
	public int size(){
		return this.count;
	}

	//输出数据
	public void print(){
		if (this.root == null){
			return;
		}
		System.out.println(this.root.getData());
		if (this.root.getNext()==null){
			return;
		}
		else{
			this.root.getNext().nodePrint();
		}
	}
	//链表数据转换为对象数组
	public Object[] toArray(){
			if(this.count == 0){
				return null;
			}
			this.retData = new Object[this.count];
			this.root.toArrayNode();
			this.foot = 0;//下表清零操作
			return this.retData;
	}
	//查找链表的指定数据是否存在
	public boolean contains(Object search){
		if(search == null && this.root == null)
			return false;
		return this.root.containsNode(search);
	}
	//根据索引取得数据
	public Object get(int index){
		if(index >= this.count){
			return null;
		}
		this.foot = 0;
		return this.root.getNode(index);
	}
	
	//修改指定索引数据
	public void set(int index,Object newData){
		if(index >= this.count){
			return ;
		}
		this.foot = 0;
		this.root.setNode(index,newData);
	}
	//删除数据
	public void remove(Object data){
		if(this.contains(data)){//如果数据存在则进行数据处理
			if(this.root.data.equals(data)){//首先需要判断要删除的数据是否为根节点数据
				this.root = this.root.next;//根节点变为下一个节点
			}else{//不是根节点
				this.root.next.removeNode(this.root,data);
			}
			this.count --;
		}
	}
}
interface Pet{//定义宠物
	public String getName();
	public String getColor();
	public int getAge();
}
class PetShop{
	private Link pets = new Link();//开辟一个链表，保存宠物信息
	public void add(Pet pet){//上架宠物
		this.pets.add(pet);
	}
	public void delete(Pet pet){//下架宠物
		this.pets.remove(pet);
	}
	public Link getPets(){	//得到全部宠物
		return this.pets;
	}
	public Link search(String keyword){//关键字查找
		Link result = new Link();
		Object [] data = this.pets.toArray();
		for(int i = 0; i < data.length ; i++){
			Pet pet = (Pet) data[i];
			if(pet.getName().contains(keyword) || pet.getColor().contains(keyword)){
				result.add(pet);	//满足查询结果
			}
		}
		return result;
	}
}
class Dog implements Pet{
	private String name;
	private String color;
	private int age;
	public String getName(){
		return this.name;
	}
	public String getColor(){
		return this.color;
	}
	public boolean equals(Object obj){
		if(obj == null){
		return false;
		}
		if(this == obj){
			return false;
		}
		if(!(obj instanceof Dog)){
			return false;
		}
		Dog pet = (Dog) obj;
		return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age == pet.age;
	}	
	public int getAge(){
		return this.age;
	}
	public Dog(String name, String color, int age){
		this.name = name ;
		this.color = color;
		this.age = age;
	}
	public String toString(){
		return "【狗】名字 = " + this.name +
				"，颜色 = " + this.color + 
				"，年龄 = " +this.age;
	}
}

class Cat implements Pet{
	private String name;
	private String color;
	private int age;
	public String getName(){
		return this.name;
	}
	public String getColor(){
		return this.color;
	}
	public boolean equals(Object obj){
		if(obj == null){
		return false;
		}
		if(this == obj){
			return false;
		}
		if(!(obj instanceof Cat)){
			return false;
		}
		Cat pet = (Cat) obj;
		return this.name.equals(pet.name) && this.color.equals(pet.color) && this.age == pet.age;
	}	
	public int getAge(){
		return this.age;
	}
	public Cat(String name, String color, int age){
		this.name = name ;
		this.color = color;
		this.age = age;
	}
	public String toString(){
		return "【猫】名字 = " + this.name +
				"，颜色 = " + this.color + 
				"，年龄 = " +this.age;
	}
}
public class Pets{
	public static void main(String args[]){
		PetShop ps = new PetShop();
		ps.add(new Dog("小黑","黑色",1));
		ps.add(new Dog("金毛","金色",2));
		ps.add(new Dog("拉布拉多","白色",3));
		ps.add(new Dog("萨摩耶","白色",2));
		ps.add(new Cat("加菲猫","黄色",3));
		ps.add(new Dog("波斯猫","金色",4));
		ps.delete(new Dog("萨摩耶","白色",2));
		Link all = ps.search("白");
		Object [] data = all.toArray();
		for(int i = 0 ; i < data.length ; i++){
			System.out.println(data[i]);
		}
		
	}
}

image-20210813230334734

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%