主要分析示例：
一、單鏈表循環鏈表
二、雙鏈表循環鏈表
其中單鏈表節點和雙鏈表節點類和接口ICommOperate<T>與上篇一致，這里不在贅述。參考：JAVA鏈表操作：單鏈表和雙鏈表http://m.ythuaji.com.cn/article/78976.html
一、單鏈表循環鏈表
|
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 ){ // 找到末端節點 current = current.getNextNode() ; } current.setNextNode(node) ; node.setNextNode(this.head) ; // 循壞鏈表，尾節點指向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) ;// 循壞鏈表，尾節點指向head this.size++ ; }else if( this.size<pos ){ // pos位置大于鏈表長度，插入末端 insertNode(node) ; }else if( pos>0 && pos<=this.size ){ // 鏈表內節點 // 1、找到要插入pos位置節點和前節點，node將插入兩個節點之間 int find = 0; SNode preNode = this.head; // 前節點 SNode currentNode = current; // 當前節點 while( find<pos-1 && currentNode!=this.head ){ preNode = current ; // 前節點后移 currentNode = currentNode.getNextNode() ; // 當前節點后移 find++ ; if( find<pos-1 && currentNode!=this.head ){ // 未結束尋找節點前，后移前節點 current = current.getNextNode() ; } }// System.out.println(preNode);// System.out.println(currentNode); // 2、插入節點 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); } } /* * 指定鏈表的節點pos，刪除對應節點。方式：找到要刪除節點的前后節點,進行刪除,下標從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、找到要刪除節點的前后節點 int find = 0; SNode preNode = this.head; // 前節點 SNode nextNode = current.getNextNode(); // 后節點 while( find<pos-1 && nextNode!=this.head ){ preNode = current ; // 前節點后移 nextNode = nextNode.getNextNode() ; // 后節點后移 find++ ; if( find<pos-1 && nextNode!=this.head ){ // 未結束找節點前，后移"前節點" current = current.getNextNode() ; } }// System.out.println(preNode);// System.out.println(nextNode); // 2、刪除節點 preNode.setNextNode(nextNode); System.gc(); // 回收刪除節點 this.size-- ; flag = true ; } return flag; } /* * 指定鏈表的節點pos，修改對應節點,下標從1開始 * */ @Override public boolean updateNode(int pos, Map<String, Object> map) { boolean flag = false ; SNode node = getNode(pos, map); // 獲得相應位置pos的節點 if( node!=null ){ String data = (String) map.get("data") ; node.setData(data); flag = true ; } return flag; } /* * 找到指定鏈表的節點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("總共有節點數: " + length +" 個"); int find = 0 ; while( current!=this.head ){ System.out.println("第 " + (++find) + " 個節點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { SingleCycleLinkList scll = new SingleCycleLinkList() ; SNode node1 = new SNode("節點1"); SNode node2 = new SNode("節點2"); SNode node3 = new SNode("節點3"); SNode node4 = new SNode("節點4"); SNode node5 = new SNode("節點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("*******************獲得指定鏈表節點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+" 個位置數據 ："+scll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節點*******************"); int pos1 = 3 ; System.out.println("將數據插入第"+pos1+"個節點："); scll.insertPosNode(pos1, node6) ; scll.printLink(); System.out.println("*******************刪除鏈表指定位置節點*******************"); int pos2 = 3 ; System.out.println("刪除第"+pos2+"個節點："); scll.deleteNode(pos2) ; scll.printLink(); System.out.println("*******************修改鏈表指定位置節點*******************"); int pos3 = 3 ; System.out.println("修改第"+pos3+"個節點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; scll.updateNode(pos3, map) ; scll.printLink(); }} |
二、雙鏈表循環鏈表
|
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 ; // 記錄鏈表節點數量 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{ // 鏈表內節點 while( current.getNextNode()!=this.head ){ // 找到末端節點 current = current.getNextNode() ; } current.setNextNode(node) ; node.setPriorNode(current); node.setNextNode(this.head) ; // 循壞鏈表，尾節點指向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 ){ // 鏈表內節點 // 1、找到要插入位置pos節點,插入pos節點當前位置 int find = 0; while( find<pos-1 && current.getNextNode()!=this.head ){ current = current.getNextNode() ; find++ ; } // 2、插入節點 if( current.getNextNode()==this.head ){ // 尾節點 node.setPriorNode(current); node.setNextNode(this.head); current.setNextNode(node); } else if( current.getNextNode()!=this.head ) { //中間節點 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); } } /* * 指定鏈表的節點pos，刪除對應節點。方式：找到要刪除節點的前后節點刪除,下標從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節點 int find = 0; while( find<pos-1 && current.getNextNode()!=this.head ){ current = current.getNextNode() ; find++ ; } // 2、刪除節點 if( current.getNextNode()==this.head ){ // 尾節點 current.getPriorNode().setNextNode(this.head) ; } else if( current.getNextNode()!=this.head ) { //中間節點 current.getPriorNode().setNextNode(current.getNextNode()) ; current.getNextNode().setPriorNode(current.getPriorNode()) ; } System.gc(); // 回收刪除節點 this.size-- ; flag = true ; } return flag; } /* * 指定鏈表的節點pos，修改對應節點,下標從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; } /* * 找到指定鏈表的節點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("總共有節點數: " + length +" 個"); while( current!=this.head ){ System.out.println("第 " + (++find) + " 個節點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { DoubleCycleLinkList dcll = new DoubleCycleLinkList() ; DNode node1 = new DNode("節點1"); DNode node2 = new DNode("節點2"); DNode node3 = new DNode("節點3"); DNode node4 = new DNode("節點4"); DNode node5 = new DNode("節點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("*******************獲得指定鏈表節點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+"個位置數據 ："+dcll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節點*******************"); int pos1 = dcll.getSize()+1 ; System.out.println("將數據插入第"+pos1+"個節點："); dcll.insertPosNode(pos1, node6) ; dcll.printLink(); System.out.println("*******************刪除鏈表指定位置節點*******************"); int pos2 = 7 ; System.out.println("刪除第"+pos2+"個節點："); dcll.deleteNode(pos2) ; dcll.printLink(); System.out.println("*******************修改鏈表指定位置節點*******************"); int pos3 = 3 ; System.out.println("修改第"+pos3+"個節點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; dcll.updateNode(pos3, map) ; dcll.printLink(); }} |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
