数据结构实现之单向循环链表

发表于 | 分类于 ， | | 阅读次数:

数据结构实现之单向循环链表

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
/**
 * Copyright (C), 2015-2018, XXX有限公司
 * FileName: CircleLinkedList
 * Author:   猫熊小才天
 * Date:     2018/11/26 17:06
 * Description: 单向循环链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package main.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈单向循环链表〉
 * 在循环的时候不能使用如下方法：
 * Node tmp = head;
 * while(tmp.next != null){
 *
 * }
 * 会出现死循环，换成
 * for(int i = 1; i <= getSize(); ++i)
 * @author 猫熊小才天
 * @create 2018/11/26
 * @since 1.0.0
 */
public class CircleLinkedList {

private class Node {
	int data; // 结点中的数据
	Node next = null; // 下一个结点的地址信息

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

	public Node() {
		super();
	}
}

private Node head = null; // 保存头结点
private Node tail = null; // 保存尾节点
private int size; // 保存已有的的结点数

public CircleLinkedList() {
	super();
}

/**
 * 头插法
 * 
 * @param data
 */
public void headAdd(int data) {
	// 如果链表为空
	if (isEmpty()) {
		head = new Node(data);
		head.next = head;
		tail = head;
	} else {
		Node newNode = new Node(data);
           // 让新结点指向head
		newNode.next = head;
           // 然后让新结点作为head
		head = newNode;
           // 将尾结点指向头结点
		tail.next = head;
	}
	++size;
}

/**
 * 尾插法
 * 
 * @param data
 */
public void tailAdd(int data) {
	// 如果链表为空
	if (isEmpty()) {
		head = new Node(data);
		head.next = head;
		tail = head;
	}else {
	    Node newNode = new Node(data);
	    // 让尾结点指向新结点
	    tail.next = newNode;
	    // 让新结点指向头结点
	    newNode.next = head;
	    // 将新结点作为尾结点
	    tail = newNode;
       }
       ++size;
}

   /**
    * 删除第index个结点
    * @param index
    * @return
    */
   public boolean deleteNodeByIndex(int index) {
       boolean res = false;
       if (isEmpty()) {
           System.out.println("单向循环链表为空");
           res = false;
       }
       /**
        * 如果输入的下标超过单向循环链表的范围
        */
       if (index < 1 || index > getSize()) {
           System.out.println("输入下标不在单向循环链表的范围中");
           res = false;
       }else if(index == 1){
           // 删除头结点
           Node tmp = new Node(head.next.data);
           // 让tmp等于head的下一个结点
           tmp.next = head.next.next;
           // 将tmp赋值给head，即相当于删除了原先的head
           head = tmp;
           // 尾结点指向新的头结点
           tail.next = head;
           System.out.println("删除头结点成功");
           res = true;
       }else if(index == getSize()){
           // 删除尾结点
           // 获取倒数第二个结点
           Node tmp = getDataByIndex(getSize() - 1);
           // 让倒数第二个结点指向head
           tmp.next = head;
           // tmp赋值到新的尾结点
           tail = tmp;
           System.out.println("删除尾结点成功");
           res = true;
       }else if(index > 1 && index < getSize()){
           // 删除的是中间任一结点
           // 获取第 index - 1 个结点
           Node prev = getDataByIndex(index - 1);
           // 需要删除的结点即第index-1个结点的next
           Node cur = prev.next;
           prev.next = cur.next;
           System.out.println("删除第" + index + "个结点成功");
           res = true;
       }
       --size;
       return res;
   }

   /**
    * 删除单向循环链表中数据为data的所有结点
    * @param data
    * @return
    */
   public boolean deleteNodeByData(int data) {
       if (isEmpty()) {
           System.out.println("单向循环链表为空");
           return false;
       }
       boolean res = false;
       int count = 0;
       // 先循环将头结点删除，直到头结点中的data≠data
       Node tmp = head;
       for(int i = 1; i <= getSize(); ++i){
           if(tmp.data == data){
               tmp = tmp.next;
               head = tmp;
               tail = head;
               ++count;
               --size; // 需要将size减少！！！
               res = true;
           }else {
               break;
           }
       }
       // 再循环将尾结点删除，直到尾结点中的data≠data
       Node tmp2 = tail;
       for(int i = 1; i <= getSize(); ++i){
           if(tmp.data == data){
               tmp = getDataByIndex(getSize() - 1);
               tmp.next = head;
               tail = tmp;
               ++count;
               --size;
               res = true;
           }else {
               break;
           }
       }

       Node preNode = head;
       Node curNode = head.next;
       for(int i = 1; i <= getSize(); ++i){
           if(curNode.data == data){
               preNode.next = curNode.next;
               ++count;
               --size;
               res = true;
           }
           preNode = curNode;
           curNode = curNode.next;
       }

       if(res == true){
           System.out.println("共删除了" + count + "个结点");
       }else {
           System.out.println("删除失败");
       }
       return res;
   }

   /**
    * 获取index位置下的Node数据
    * @param index
    */
   public Node getDataByIndex(int index){
       if (isEmpty()) {
           System.out.println("单向循环链表为空");
           return null;
       }else if(index < 1 || index > getSize()){
           System.out.println("输入下标不在单向循环链表的范围中");
           return null;
       }else {
           Node res = head;
           for(int i = 1; i <= getSize() && res.next != null; ++i){
               if(i == index){
                   System.out.println("第" + index + "个结点的数据是：" + res.data);
                   return res;
               }
               res = res.next;
           }
           return res;
       }
   }

/**
 * 判断链表是否为空
 * 
 * @return
 */
public boolean isEmpty() {
	return size == 0;
}

/**
 * 返回链表长度
 * 
 * @return
 */
public int getSize() {
	return size;
}

/**
 * 清空线性表
 */
public void clear() {
	// 将头结点和尾结点设为空
	head = null;
	tail = null;
	size = 0;
}

/**
 * 打印单向链表 如果传过来的参数head是list.reHead即为逆向输出
 * 
 * @param head
 */
public void printCircleLinkedList(Node head) {
	Node tmp = head;
	for(int i = 1; i <= getSize(); ++i){
           System.out.print(tmp.data);
           tmp = tmp.next;
           if (i != getSize()) {
               System.out.print(" -> ");
           }
       }
	System.out.println();
}

   public static void main(String[] args) {
       CircleLinkedList list = new CircleLinkedList();
       list.tailAdd(5);
       list.tailAdd(2);
       list.tailAdd(4);
       list.tailAdd(1);
       list.tailAdd(5);
       list.tailAdd(3);
       list.tailAdd(5);
       list.printCircleLinkedList(list.head);

       /*list.deleteNodeByIndex(3);
       list.printCircleLinkedList(list.head);*/

       //list.getDataByIndex(6);

       /*list.deleteNodeByData(5);
       list.printCircleLinkedList(list.head);*/
   }
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
5 -> 2 -> 4 -> 1 -> 5 -> 3 -> 5
第2个结点的数据是：2
删除第3个结点成功
5 -> 2 -> 1 -> 5 -> 3 -> 5

5 -> 2 -> 4 -> 1 -> 5 -> 3 -> 5
删除头结点成功
2 -> 4 -> 1 -> 5 -> 3 -> 5

5 -> 2 -> 4 -> 1 -> 5 -> 3 -> 5
第5个结点的数据是：5
删除第6个结点成功
5 -> 2 -> 4 -> 1 -> 5 -> 5

5 -> 2 -> 4 -> 1 -> 5 -> 3 -> 5
第4个结点的数据是：1

5 -> 2 -> 4 -> 1 -> 5 -> 3 -> 5
共删除了3个结点
2 -> 4 -> 1 -> 3