主要分析示例：
一、单链表循环链表
二、双链表循环链表
其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致，这里不在赘述。参考：JAVA链表操作：单链表和双链表http://www.zzvips.com/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(); }} |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
