JAVA 鏈表操作：循環(huán)鏈表
主要分析示例：
一、單鏈表循環(huán)鏈表
二、雙鏈表循環(huán)鏈表
其中單鏈表節(jié)點和雙鏈表節(jié)點類和接口ICommOperate<T>與上篇一致，這里不在贅述。參考：JAVA鏈表操作：單鏈表和雙鏈表http://www.jfrwli.cn/article/78976.html
一、單鏈表循環(huán)鏈表
|
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
|
package LinkListTest;import java.util.HashMap;import java.util.Map;public class SingleCycleLinkList implements ICommOperate<SNode> { private SNode head = new SNode("HEAD") ; // 公共頭指針，聲明之后不變 private int size = 0 ; public int getSize() { return this.size; } /* * 鏈表插入，每次往末端插入,判定末端的標準為next是否指向head * */ @Override public boolean insertNode(SNode node) { boolean flag = false ; initLinkList() ; // 初始化鏈表 if( this.size==0 ){ // 空鏈表 this.head.setNextNode(node) ; node.setNextNode(this.head) ; }else{ SNode current = this.head ; while( current.getNextNode()!=this.head ){ // 找到末端節(jié)點 current = current.getNextNode() ; } current.setNextNode(node) ; node.setNextNode(this.head) ; // 循壞鏈表，尾節(jié)點指向head } this.size++ ; flag = true ; return flag; } /* * 插入鏈表指定位置pos,從1開始,而pos大于size則插入鏈表末端 * */ @Override public boolean insertPosNode(int pos, SNode node) { boolean flag = true ; SNode current = this.head.getNextNode() ; initLinkList() ;// 初始化鏈表 if( this.size==0 ){ // 鏈表為空 this.head.setNextNode(node) ; node.setNextNode(this.head) ;// 循壞鏈表，尾節(jié)點指向head this.size++ ; }else if( this.size<pos ){ // pos位置大于鏈表長度，插入末端 insertNode(node) ; }else if( pos>0 && pos<=this.size ){ // 鏈表內節(jié)點 // 1、找到要插入pos位置節(jié)點和前節(jié)點，node將插入兩個節(jié)點之間 int find = 0; SNode preNode = this.head; // 前節(jié)點 SNode currentNode = current; // 當前節(jié)點 while( find<pos-1 && currentNode!=this.head ){ preNode = current ; // 前節(jié)點后移 currentNode = currentNode.getNextNode() ; // 當前節(jié)點后移 find++ ; if( find<pos-1 && currentNode!=this.head ){ // 未結束尋找節(jié)點前，后移前節(jié)點 current = current.getNextNode() ; } }// System.out.println(preNode);// System.out.println(currentNode); // 2、插入節(jié)點 preNode.setNextNode(node); node.setNextNode(currentNode); this.size++ ; }else { System.out.println("位置信息錯誤"); flag = false ; } return flag; } private void initLinkList(){ if( size==0 ){ this.head.setNextNode(this.head); } } /* * 指定鏈表的節(jié)點pos，刪除對應節(jié)點。方式：找到要刪除節(jié)點的前后節(jié)點,進行刪除,下標從1開始 * */ @Override public boolean deleteNode(int pos) { boolean flag = false; SNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==this.head ){ System.out.println("位置信息錯誤或鏈表無信息"); }else{ // 1、找到要刪除節(jié)點的前后節(jié)點 int find = 0; SNode preNode = this.head; // 前節(jié)點 SNode nextNode = current.getNextNode(); // 后節(jié)點 while( find<pos-1 && nextNode!=this.head ){ preNode = current ; // 前節(jié)點后移 nextNode = nextNode.getNextNode() ; // 后節(jié)點后移 find++ ; if( find<pos-1 && nextNode!=this.head ){ // 未結束找節(jié)點前，后移"前節(jié)點" current = current.getNextNode() ; } }// System.out.println(preNode);// System.out.println(nextNode); // 2、刪除節(jié)點 preNode.setNextNode(nextNode); System.gc(); // 回收刪除節(jié)點 this.size-- ; flag = true ; } return flag; } /* * 指定鏈表的節(jié)點pos，修改對應節(jié)點,下標從1開始 * */ @Override public boolean updateNode(int pos, Map<String, Object> map) { boolean flag = false ; SNode node = getNode(pos, map); // 獲得相應位置pos的節(jié)點 if( node!=null ){ String data = (String) map.get("data") ; node.setData(data); flag = true ; } return flag; } /* * 找到指定鏈表的節(jié)點pos,下標從1開始 * */ @Override public SNode getNode(int pos, Map<String, Object> map) { SNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==this.head ){ System.out.println("位置信息錯誤或鏈表不存在"); return null; } int find = 0 ; while( find<pos-1 && current!=this.head ){ current = current.getNextNode() ; find++ ; } return current; } /* * 打印鏈表 * */ @Override public void printLink() { int length = this.size ; if( length==0 ){ System.out.println("鏈表為空！"); return ; } SNode current = this.head.getNextNode() ; System.out.println("總共有節(jié)點數(shù): " + length +" 個"); int find = 0 ; while( current!=this.head ){ System.out.println("第 " + (++find) + " 個節(jié)點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { SingleCycleLinkList scll = new SingleCycleLinkList() ; SNode node1 = new SNode("節(jié)點1"); SNode node2 = new SNode("節(jié)點2"); SNode node3 = new SNode("節(jié)點3"); SNode node4 = new SNode("節(jié)點4"); SNode node5 = new SNode("節(jié)點5"); SNode node6 = new SNode("插入指定位置");// scll.insertPosNode(scll.getSize()+1, node1) ;// scll.insertPosNode(scll.getSize()+1, node2) ;// scll.insertPosNode(scll.getSize()+1, node3) ;// scll.insertPosNode(scll.getSize()+1, node4) ;// scll.insertPosNode(scll.getSize()+1, node5) ; scll.insertNode(node1); scll.insertNode(node2); scll.insertNode(node3); scll.insertNode(node4); scll.insertNode(node5); System.out.println("*******************輸出鏈表*******************"); scll.printLink(); System.out.println("*******************獲得指定鏈表節(jié)點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+" 個位置數(shù)據(jù) ："+scll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節(jié)點*******************"); int pos1 = 3 ; System.out.println("將數(shù)據(jù)插入第"+pos1+"個節(jié)點："); scll.insertPosNode(pos1, node6) ; scll.printLink(); System.out.println("*******************刪除鏈表指定位置節(jié)點*******************"); int pos2 = 3 ; System.out.println("刪除第"+pos2+"個節(jié)點："); scll.deleteNode(pos2) ; scll.printLink(); System.out.println("*******************修改鏈表指定位置節(jié)點*******************"); int pos3 = 3 ; System.out.println("修改第"+pos3+"個節(jié)點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; scll.updateNode(pos3, map) ; scll.printLink(); }} |
二、雙鏈表循環(huán)鏈表
|
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
|
package LinkListTest;import java.util.HashMap;import java.util.Map;public class DoubleCycleLinkList implements ICommOperate<DNode>{ private DNode head = new DNode("HEAD"); // 公共頭指針，聲明之后不變 private int size = 0 ; // 記錄鏈表節(jié)點數(shù)量 public int getSize() { return this.size; } /* * 鏈表插入，每次往末端插入,判定末端的標準為next是否指向head * */ @Override public boolean insertNode(DNode node) { boolean flag = false ; initLinkList() ; // 初始化鏈表 DNode current = this.head ; if( this.size==0 ){ // 空鏈表 this.head.setNextNode(node) ; node.setPriorNode(this.head); node.setNextNode(this.head) ; }else{ // 鏈表內節(jié)點 while( current.getNextNode()!=this.head ){ // 找到末端節(jié)點 current = current.getNextNode() ; } current.setNextNode(node) ; node.setPriorNode(current); node.setNextNode(this.head) ; // 循壞鏈表，尾節(jié)點指向head } this.size++ ; flag = true ; return flag; } /* * 插入鏈表指定位置pos,從1開始,而pos大于size則插入鏈表末端 * */ @Override public boolean insertPosNode(int pos, DNode node) { boolean flag = true; initLinkList() ; // 初始化鏈表 DNode current = this.head.getNextNode() ; if( this.size==0 ){ // 鏈表為空 this.head.setNextNode(node) ; node.setPriorNode(this.head); node.setNextNode(this.head) ; this.size++ ; }else if( pos>this.size ){ // pos位置大于鏈表長度，插入末端 insertNode(node) ; }else if( pos>0 && pos<=this.size ){ // 鏈表內節(jié)點 // 1、找到要插入位置pos節(jié)點,插入pos節(jié)點當前位置 int find = 0; while( find<pos-1 && current.getNextNode()!=this.head ){ current = current.getNextNode() ; find++ ; } // 2、插入節(jié)點 if( current.getNextNode()==this.head ){ // 尾節(jié)點 node.setPriorNode(current); node.setNextNode(this.head); current.setNextNode(node); } else if( current.getNextNode()!=this.head ) { //中間節(jié)點 node.setPriorNode(current.getPriorNode()); node.setNextNode(current); current.getPriorNode().setNextNode(node); current.setPriorNode(node); } this.size++ ; }else{ System.out.println("位置信息錯誤"); flag = false ; } return flag; } private void initLinkList(){ if( size==0 ){ this.head.setNextNode(this.head); this.head.setPriorNode(this.head); } } /* * 指定鏈表的節(jié)點pos，刪除對應節(jié)點。方式：找到要刪除節(jié)點的前后節(jié)點刪除,下標從1開始 * */ @Override public boolean deleteNode(int pos) { boolean flag = false; DNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==this.head ){ System.out.println("位置信息錯誤或鏈表不存在"); }else{ // 1、找到要刪除位置pos節(jié)點 int find = 0; while( find<pos-1 && current.getNextNode()!=this.head ){ current = current.getNextNode() ; find++ ; } // 2、刪除節(jié)點 if( current.getNextNode()==this.head ){ // 尾節(jié)點 current.getPriorNode().setNextNode(this.head) ; } else if( current.getNextNode()!=this.head ) { //中間節(jié)點 current.getPriorNode().setNextNode(current.getNextNode()) ; current.getNextNode().setPriorNode(current.getPriorNode()) ; } System.gc(); // 回收刪除節(jié)點 this.size-- ; flag = true ; } return flag; } /* * 指定鏈表的節(jié)點pos，修改對應節(jié)點,下標從1開始 * */ @Override public boolean updateNode(int pos, Map<String, Object> map) { boolean flag = false ; DNode node = getNode(pos, map); if( node!=null ){ String data = (String) map.get("data") ; node.setData(data); flag = true ; } return flag; } /* * 找到指定鏈表的節(jié)點pos,下標從1開始 * */ @Override public DNode getNode(int pos, Map<String, Object> map) { DNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==this.head ){ System.out.println("位置信息錯誤或鏈表不存在"); return null; } int find = 0 ; while( find<pos-1 && current!=this.head ){ current = current.getNextNode() ; find++ ; } return current; } /* * 打印鏈表 * */ @Override public void printLink() { int length = this.size ; if( length==0 ){ System.out.println("鏈表為空！"); return ; } DNode current = this.head.getNextNode() ; int find = 0 ; System.out.println("總共有節(jié)點數(shù): " + length +" 個"); while( current!=this.head ){ System.out.println("第 " + (++find) + " 個節(jié)點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { DoubleCycleLinkList dcll = new DoubleCycleLinkList() ; DNode node1 = new DNode("節(jié)點1"); DNode node2 = new DNode("節(jié)點2"); DNode node3 = new DNode("節(jié)點3"); DNode node4 = new DNode("節(jié)點4"); DNode node5 = new DNode("節(jié)點5"); DNode node6 = new DNode("插入指定位置"); dcll.insertPosNode(10, node1) ; dcll.insertPosNode(10, node2) ; dcll.insertPosNode(8, node3) ; dcll.insertPosNode(88, node4) ; dcll.insertPosNode(8, node5) ;// dcll.insertNode(node1);// dcll.insertNode(node2);// dcll.insertNode(node3);// dcll.insertNode(node4);// dcll.insertNode(node5); System.out.println("*******************輸出鏈表*******************"); dcll.printLink(); System.out.println("*******************獲得指定鏈表節(jié)點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+"個位置數(shù)據(jù) ："+dcll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節(jié)點*******************"); int pos1 = dcll.getSize()+1 ; System.out.println("將數(shù)據(jù)插入第"+pos1+"個節(jié)點："); dcll.insertPosNode(pos1, node6) ; dcll.printLink(); System.out.println("*******************刪除鏈表指定位置節(jié)點*******************"); int pos2 = 7 ; System.out.println("刪除第"+pos2+"個節(jié)點："); dcll.deleteNode(pos2) ; dcll.printLink(); System.out.println("*******************修改鏈表指定位置節(jié)點*******************"); int pos3 = 3 ; System.out.println("修改第"+pos3+"個節(jié)點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; dcll.updateNode(pos3, map) ; dcll.printLink(); }} |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
