鏈表是一種復雜的數據結構，其數據之間的相互關系使鏈表分成三種：單鏈表、循環鏈表、雙向鏈表，下面將逐一介紹。鏈表在數據結構中是基礎，也是重要的知識點，這里講下Java 中鏈表的實現，
JAVA 鏈表操作：單鏈表和雙鏈表
主要講述幾點：
一、鏈表的簡介
二、鏈表實現原理和必要性
三、單鏈表示例
四、雙鏈表示例
一、鏈表的簡介
鏈表是一種比較常用的數據結構，鏈表雖然保存比較復雜，但是在查詢時候比較便捷，在多種計算機語言都相應的應用，鏈表有多種類別，文章針對單鏈表和雙鏈表進行分析。鏈表中數據就像被一個鏈條串聯一起，輕易的可以實現數據的訪問。
二、鏈表實現原理和必要性
這里只分析單鏈表和雙鏈表。鏈表的實現過程是有些許復雜的，但是會帶來許多好處。比如現在網購時代到來，商家發快遞一般會將商品包裝在盒子里并寫上地址信息，快遞公司就可以通過盒子上的信息找到買家，商品完整到達。如果沒有盒子的保護，有可能在途中商品受損。而鏈表就好比那個寫了地址信息的盒子，既保護了商品信息，同時又寫好了物流信息。鏈表之中存在一個HEAD節點，類似“火車頭”，只要找到相應HEAD節點，就可以對鏈表進行操作。此次分析中，HEAD節點只是做數據頭，不保存有效數據。
單鏈表的實現原理如圖：
雙鏈表實現原理：
三、單鏈表示例
ICommOperate<T> 接口操作類：
|
1
2
3
4
5
6
7
8
9
10
11
|
package LinkListTest;import java.util.Map;public interface ICommOperate<T> { public boolean insertNode(T node) ; public boolean insertPosNode(int pos, T node) ; public boolean deleteNode(int pos) ; public boolean updateNode(int pos, Map<String, Object> map) ; public T getNode(int pos, Map<String, Object> map) ; public void 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
|
package LinkListTest;// 單連表節點public class SNode { private String data; private SNode nextNode; public SNode() { } public SNode(String data) { this.data = data; this.nextNode = new SNode(); } public String getData() { return data; } public void setData(String data) { this.data = data; } public SNode getNextNode() { return nextNode; } public void setNextNode(SNode nextNode) { this.nextNode = nextNode; } @Override public String toString() { return "SNode [data=" + data + "]"; }} |
單鏈接操作類：
|
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
|
package LinkListTest;import java.util.HashMap;import java.util.Map;public class SingleLinkList implements ICommOperate<SNode>{ private SNode head = new SNode("HEAD") ; // 公共頭指針，聲明之后不變 private int size = 0 ; public int getSize() { return this.size; } /* * 鏈表插入，每次往末端插入 * */ @Override public boolean insertNode(SNode node) { boolean flag = false ; SNode current = this.head ; if( this.size==0 ){ // 空鏈表 this.head.setNextNode(node) ; node.setNextNode(null) ; }else{ // 鏈表內節點 while( current.getNextNode()!=null ){ current = current.getNextNode() ; } current.setNextNode(node) ; node.setNextNode(null) ; } 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() ; if( this.size==0 ){ // 空鏈表 this.head.setNextNode(node) ; node.setNextNode(null) ; this.size++ ; }else if( this.size<pos ){ // pos位置大于鏈表長度，插入末端 insertNode(node) ; }else if( pos>0 && pos<=this.size) { // 鏈表內節點 // 1、找到要插入pos位置節點和前節點 int find = 0; SNode preNode = this.head; // 前節點 SNode currentNode = current; // 當前節點 while( find<pos-1 && currentNode.getNextNode()!=null ){ preNode = current ; // 前節點后移 currentNode = currentNode.getNextNode() ; // 當前節點后移 find++ ; }// System.out.println(preNode);// System.out.println(currentNode); // 2、插入節點 preNode.setNextNode(node); node.setNextNode(currentNode); this.size++ ; System.out.println("節點已經插入鏈表中"); }else{ System.out.println("位置信息錯誤"); flag = false ; } return flag; } /* * 指定鏈表的節點pos，刪除對應節點。方式：找到要刪除節點的前后節點，進行刪除。從1開始 * */ @Override public boolean deleteNode(int pos) { boolean flag = false; SNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("位置信息錯誤或鏈表無信息"); }else{ // 1、找到要刪除節點的前后節點 int find = 0; SNode preNode = this.head; // 前節點 SNode nextNode = current.getNextNode(); // 后節點 while( find<pos-1 && nextNode.getNextNode()!=null ){ preNode = current ; // 前節點后移 nextNode = nextNode.getNextNode() ; // 后節點后移 find++ ; }// 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==null ){ System.out.println("位置信息錯誤或鏈表不存在"); return null; } int find = 0 ; while( find<pos-1 && current!=null ){ 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() ; int find = 0 ; System.out.println("總共有節點數: " + length +" 個"); while( current!=null ){ System.out.println("第 " + (++find) + " 個節點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { SingleLinkList sll = new SingleLinkList() ; 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("插入指定位置"); sll.insertPosNode(sll.getSize()+1, node1) ; sll.insertPosNode(sll.getSize()+1, node2) ; sll.insertPosNode(sll.getSize()+1, node3) ; sll.insertPosNode(sll.getSize()+1, node4) ; sll.insertPosNode(sll.getSize()+1, node5) ; // sll.insertNode(node1);// sll.insertNode(node2);// sll.insertNode(node3);// sll.insertNode(node4);// sll.insertNode(node5); System.out.println("*******************輸出鏈表*******************"); sll.printLink(); System.out.println("*******************獲得指定鏈表節點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+" 個位置數據 ："+sll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節點*******************"); int pos1 = 2 ; System.out.println("將數據插入第 "+pos1+" 個節點："); sll.insertPosNode(pos1, node6) ; sll.printLink(); System.out.println("*******************刪除鏈表指定位置節點*******************"); int pos2 = 2 ; System.out.println("刪除第 "+pos2+" 個節點："); sll.deleteNode(pos2) ; sll.printLink(); System.out.println("*******************修改鏈表指定位置節點*******************"); int pos3 = 2 ; System.out.println("修改第 "+pos3+" 個節點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; sll.updateNode(pos3, map) ; sll.printLink(); }} |
四、雙鏈表示例
ICommOperate<T> 接口操作類：
|
1
2
3
4
5
6
7
8
9
10
|
package LinkListTest;import java.util.Map;public interface ICommOperate<T> { public boolean insertNode(T node) ; public boolean insertPosNode(int pos, T node) ; public boolean deleteNode(int pos) ; public boolean updateNode(int pos, Map<String, Object> map) ; public T getNode(int pos, Map<String, Object> map) ; public void 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
|
package LinkListTest;// 雙連表節點public class DNode { private DNode priorNode; private String data; private DNode nextNode; public DNode(){ } public DNode(String data) { this.priorNode = new DNode() ; this.data = data ; this.nextNode = new DNode() ; } public DNode getPriorNode() { return priorNode; } public void setPriorNode(DNode priorNode) { this.priorNode = priorNode; } public String getData() { return data; } public void setData(String data) { this.data = data; } public DNode getNextNode() { return nextNode; } public void setNextNode(DNode nextNode) { this.nextNode = nextNode; } @Override public String toString() { return "DNode [data=" + data + "]"; } } |
雙鏈表實現類：
|
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
|
package LinkListTest;import java.util.HashMap;import java.util.Map;public class DoubleLinkList implements ICommOperate<DNode>{ private DNode head = new DNode("HEAD"); private int size = 0 ; public int getSize() { return this.size; } /* * 鏈表插入，每次往末端插入 * */ @Override public boolean insertNode(DNode node) { boolean flag = false; DNode current = this.head ; if( this.size==0 ){ // 空鏈表 this.head.setNextNode(node) ; node.setPriorNode(this.head); node.setNextNode(null) ; }else{ // 鏈表內節點 while( current.getNextNode()!=null ){ current = current.getNextNode() ; } current.setNextNode(node); node.setNextNode(null); node.setPriorNode(current); } this.size++ ; flag = true ; return flag; } /* * 插入鏈表指定位置pos，從1開始,而pos大于size則插入鏈表末端 * */ @Override public boolean insertPosNode(int pos, DNode node) { boolean flag = true; DNode current = this.head.getNextNode() ; if( this.size==0){ // 鏈表為空 this.head.setNextNode(node) ; node.setNextNode(null) ; node.setPriorNode(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()!=null ){ current = current.getNextNode() ; find++ ; } // 2、插入節點 if( current.getNextNode()==null ){ // 尾節點 node.setPriorNode(current); node.setNextNode(null); current.setNextNode(node); } else if( current.getNextNode()!=null ) { //中間節點 node.setPriorNode(current.getPriorNode()); node.setNextNode(current); current.getPriorNode().setNextNode(node); current.setPriorNode(node); } this.size++ ; }else{ System.out.println("位置信息錯誤"); flag = false ; } return flag; } /* * 指定鏈表的節點pos，刪除對應節點，從1開始 * */ @Override public boolean deleteNode(int pos) { boolean flag = false; DNode current = this.head.getNextNode() ; if( pos<=0 || pos>this.size || current==null ){ System.out.println("位置信息錯誤或鏈表不存在"); }else{ // 1、找到要刪除位置pos節點 int find = 0; while( find<pos-1 && current.getNextNode()!=null ){ current = current.getNextNode() ; find++ ; } // 2、刪除節點 if( current.getNextNode()==null ){ // 尾節點 current.getPriorNode().setNextNode(null) ; } else if( current.getNextNode()!=null ) { //中間節點 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==null ){ System.out.println("位置信息錯誤或鏈表不存在"); return null; } int find = 0 ; while( find<pos-1 && current!=null ){ 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!=null ){ System.out.println("第 " + (++find) + " 個節點 ：" + current); current=current.getNextNode() ; } } public static void main(String[] args) { DoubleLinkList dll = new DoubleLinkList() ; 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("插入指定位置"); dll.insertPosNode(10, node1) ; dll.insertPosNode(10, node2) ; dll.insertPosNode(10, node3) ; dll.insertPosNode(10, node4) ; dll.insertPosNode(10, node5) ;// dll.insertNode(node1);// dll.insertNode(node2);// dll.insertNode(node3);// dll.insertNode(node4);// dll.insertNode(node5); System.out.println("*******************輸出鏈表*******************"); dll.printLink(); System.out.println("*******************獲得指定鏈表節點*******************"); int pos = 2 ; System.out.println("獲取鏈表第 "+pos+" 個位置數據 ："+dll.getNode(pos, null)); System.out.println("*******************向鏈表指定位置插入節點*******************"); int pos1 = 2 ; System.out.println("將數據插入第"+pos1+"個節點："); dll.insertPosNode(pos1, node6) ; dll.printLink(); System.out.println("*******************刪除鏈表指定位置節點*******************"); int pos2 = 7 ; System.out.println("刪除第"+pos2+"個節點："); dll.deleteNode(pos2) ; dll.printLink(); System.out.println("*******************修改鏈表指定位置節點*******************"); int pos3 = 2 ; System.out.println("修改第"+pos3+"個節點："); Map<String, Object> map = new HashMap<>() ; map.put("data", "this is a test") ; dll.updateNode(pos3, map) ; dll.printLink(); } } |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
