本文實例講述了Java數據結構之雙端鏈表原理與實現方法。分享給大家供大家參考，具體如下：
一、概述：
1、什么時雙端鏈表：
鏈表中保持這對最后一個連點引用的鏈表
2、從頭部插入
要對鏈表進行判斷，如果為空則設置尾節點為新添加的節點
3、從尾部進行插入
如果鏈表為空，則直接設置頭節點為新添加的節點，否則設置尾節點的后一個節點為新添加的節點
4、從頭部刪除
判斷節點是否有下個節點，如果沒有則設置節點為null
二、具體實現
|
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
|
/** * @描述 頭尾相接的鏈表 * @項目名稱 Java_DataStruct * @包名 com.struct.linklist * @類名 LinkList * @author chenlin * @date 2010年6月26日 上午8:00:28 * @version 1.0 */public class FirstLastLinkList { //頭 private Node first; //尾 private Node last; public FirstLastLinkList(){ first = null; last = null; } /** * 插入數據 * @param value */ public void insertFirst(long value){ Node newNode = new Node(value); if (first == null) { last = newNode; }else { //把first節點往下移動 newNode.next = first; } //把插入的節點作為新的節點 first = newNode; } /** * 插入數據 * @param value */ public void insertLast(long value){ Node newNode = new Node(value); if (first == null) { first = newNode; }else { last.next = newNode; } //把最后個節點設置為最新的節點 last = newNode; } public boolean isEmpty(){ return first == null; } /** * 刪除頭節點 * @param value * @return */ public Node deleteFirst(){ if (first == null) { throw new RuntimeException("鏈表數據不存在"); } if (first.next == null) { last = null; } Node temp = first; first = temp.next; return temp; } public Node deleteByKey(long key){ Node current = first; Node last = first; while(current.data != key){ if (current.next == null) { System.out.println("沒找到節點"); return null; } last = current; current = current.next; } if (current == first) { //return deleteFirst(); //指向下個就表示刪除第一個 first = first.next; }else { last.next = current.next; } return current; } /** * 顯示所有的數據 */ public void display(){ if (first == null) { //throw new RuntimeException("鏈表數據不存在"); return; } Node current = first; while(current != null){ current.display(); current = current.next; } System.out.println("---------------"); } /** * 查找節點1 * @param value * @return */ public Node findByValue(long value){ Node current = first; while(current != null){ if (current.data != value) { current = current.next; }else { break; } } if (current == null) { System.out.println("沒找到"); return null; } return current; } /** * 查找節點2 * * @param key * @return */ public Node findByKey(long key) { Node current = first; while (current.data != key) { if (current.next == null) { System.out.println("沒找到"); return null; } current = current.next; } return current; } /** * 根據索引查找對應的值 * @param position * @return */ public Node findByPosition(int position){ Node current = first; //為什么是position - 1，因為要使用遍歷，讓current指向下一個， 所以position - 1的下個node就是要找的值 for (int i = 0; i < position - 1 ; i++) { current = current.next; } return current; } public static void main(String[] args) { FirstLastLinkList linkList = new FirstLastLinkList(); linkList.insertFirst(21); linkList.insertFirst(22); linkList.insertFirst(23); linkList.insertLast(24); linkList.insertLast(25); linkList.insertLast(26); linkList.insertLast(27); linkList.display(); System.out.println("---查找-------------------------------------"); linkList.findByKey(25).display(); System.out.println("--刪除first-------------------------------------"); //linkList.deleteFirst().display(); ///linkList.deleteFirst().display(); //linkList.deleteFirst().display(); //linkList.deleteFirst().display(); System.out.println("-刪除指定值---------------------------------------"); linkList.deleteByKey(27).display(); linkList.deleteByKey(21).display(); System.out.println("----------------------------------------"); linkList.display(); }} |
希望本文所述對大家java程序設計有所幫助。
原文鏈接：http://blog.csdn.net/lovoo/article/details/51762164
