java与数据结构(4)---java实现双向循环链表
分类:
IT文章
•
2022-07-28 21:49:06
线性表之链式存储结构双向循环链表
双向循环链表：每个结点包含了数据、直接前驱地址指针和直接后驱地址指针，头结点的直接前驱指向尾结点，尾结点的直接后驱指向头结点，头尾相连构成一个可正可反的圆环。可以形象的理解成一群孩子手拉手牵成一个圆圈，从头一个孩子开始可以从左往右报数，也可以从右往左开始报数。
优点：双向循环链表可以迅速的获取当前数据的前驱数据，解决了单向循环链表从头开始遍历的麻烦。
接口类
![]()
1 package list;
2
3 public interface Listable<T> {
4
5 public void clear();
6
7 public boolean isEmpty();
8
9 public int Length();
10
11 public T getElement(int index);
12
13 public boolean add(T element);
14
15 public boolean addHead(T element);
16
17 public boolean addByIndex(int index, T element);
18
19 public boolean add(Listable<T> list);
20
21 public T remove(int index);
22
23 public boolean removeAll();
24
25 public T remove(T element);
26
27 public T setElement(int index,T element);
28
29 }
View Code
结点类
![]()
1 //结点类
2 class Node<T> {
3 private Node<T> left,right;
4 private T data;
5
6 Node(T data) {
7 this(data,null,null);
8 }
9
10 Node() {
11 this(null,null,null);
12 }
13
14 Node(T data,Node<T> left,Node<T> right) {
15 this.data = data;
16 this.left = left;
17 this.right = right;
18 }
19
20 public T getData() {
21 return this.data;
22 }
23
24 public Node<T> getLeft() {
25 return this.left;
26 }
27
28 public Node<T> getRight() {
29 return this.right;
30 }
31
32 public void setData(T data) {
33 this.data = data;
34 }
35
36 public void setRight(Node<T> right) {
37 this.right = right;
38 }
39
40 public void setLeft(Node<T> left) {
41 this.left = left;
42 }
43
44 public String toString() {
45 return getData().toString();
46 }
47 }
View Code
接口实现类
![]()
1 //接口实现类
2 class DoubleLinkedList<T> implements Listable<T> {
3 public Node<T> head;
4
5 //建空表,带头结点
6 DoubleLinkedList() {
7 this(null);
8 }
9
10 //建表，带头结点，表中有一条数据元素
11 DoubleLinkedList(T element) {
12 if(element == null) {
13 head = new Node<T>(element,null,null);
14 head.setRight(head);
15 head.setLeft(head);
16 }else {
17 Node<T> headRight = new Node<T>(element,null,null);
18 head = new Node<T>(null,headRight,headRight);
19 headRight.setLeft(head);
20 headRight.setRight(head);
21 }
22 }
23
24 //清空当前链表
25 public void clear() {}
26
27 //判空表
28 public boolean isEmpty() {
29 return head.getRight() == head;
30 }
31
32 //表长
33 public int Length() {
34 int len = 0;
35 Node<T> temp = head;
36 while(temp.getRight() != head) {
37 len++;
38 temp = temp.getRight();
39 }
40 return len;
41 }
42
43 //取下标index处的数据
44 public T getElement(int index) {
45 if(index <= 0) {
46 return head.getRight().getData();
47 }
48 int len = Length();
49 if(index >= len) {
50 return head.getLeft().getData();
51 }
52 T element = null;
53 if(index > 0 && index < len) {
54 int k = 0;
55 Node<T> temp = head;
56 //此处只能用while不能用if，用错好几次
57 while(k <= index && temp.getRight() != head) {
58 k++;
59 temp = temp.getRight();
60 }
61 element = temp.getData();
62 }
63 return element;
64 }
65
66 //尾添
67 public boolean add(T element) {
68 if(element == null) return false;
69 Node<T> node = new Node<T>(element,head.getLeft(),head);
70 head.getLeft().setRight(node);
71 head.setLeft(node);
72 return true;
73 }
74
75 //首添
76 public boolean addHead(T element) {
77 if(element == null) return false;
78 Node<T> node = new Node<T>(element,head,head.getRight());
79 head.getRight().setLeft(node);
80 head.setRight(node);
81 return false;
82 }
83
84 //表index处，添加新数据element
85 public boolean addByIndex(int index, T element) {
86 if(index <= 0) {
87 return addHead(element);
88 }else if(index >= Length()) {
89 return add(element);
90 }else {
91 int k = 0;
92 Node<T> temp = head;
93 //此处只能用while不能用if，用错好几次
94 while(k <= index && temp.getRight() != head) {
95 k++;
96 temp = temp.getRight();
97 }
98 Node<T> node = new Node<T>(element,temp.getLeft(),temp);
99 temp.getLeft().setRight(node);
100 temp.setLeft(node);
101 }
102 return true;
103 }
104
105 //将参数中的链表添加到当前链表的尾部
106 public boolean add(Listable<T> slist) {
107 if(slist.isEmpty() || slist == null) return false;
108 if(slist instanceof DoubleLinkedList) {
109 DoubleLinkedList<T> list = (DoubleLinkedList<T>)slist;
110 //以下操作影响到了添加的slist表，所以需要将slist表重新备份一个
111 DoubleLinkedList<T> temp = new DoubleLinkedList<T>();
112 for(int i = 0; i < list.Length(); i++) {
113 temp.add(list.getElement(i));
114 }
115 Node<T> node = temp.head;
116 Node<T> nodeLeft = node.getLeft();
117 Node<T> nodeRight = node.getRight();
118 this.head.getLeft().setRight(node.getRight());
119 nodeRight.setLeft(this.head.getLeft());
120 nodeLeft.setRight(this.head);
121 this.head.setLeft(node.getLeft());
122 return true;
123 }else {
124 return false;
125 }
126 }
127
128 //删除下标Index处的数据
129 public T remove(int index) {
130 if(isEmpty()) return null;
131 if(index < 0) {
132 index = 0;
133 }
134 int len = Length();
135 if(index >= len) {
136 //当index大于或等于表长是，默认移走表的最后一个元素，即下标为len-1的数据
137 index = len-1;
138 }
139 T element = null;
140 if(index >= 0 && index < len) {
141 Node<T> temp = head;
142 int k = 0;
143 while(k <= index && temp.getRight() != head) {
144 k++;
145 temp = temp.getRight();
146 }
147 element = temp.getData();
148 temp.getRight().setLeft(temp.getLeft());
149 temp.getLeft().setRight(temp.getRight());
150 temp.setRight(null);
151 temp.setLeft(null);
152 temp = null;
153 }
154 return element;
155 }
156
157 //删除当前链表中所有的数据，只剩头结点
158 public boolean removeAll() {
159 if(isEmpty()) return false;
160 Node<T> temp = head.getRight();
161 while(temp != head) {
162 head.setRight(temp.getRight());
163 temp.getRight().setLeft(head);
164 temp.setLeft(null);
165 temp.setRight(null);
166 temp = head.getRight();
167 }
168 return true;
169 }
170
171 //删除链表中从head开始的第一个element数据
172 public T remove(T element) {
173 if(isEmpty() || element == null) return null;
174 //从表中第一个元素开始比较
175 Node<T> temp = head.getRight();
176 int k=0;
177 while(temp != head) {
178 if(element.equals(temp.getData())) {
179 remove(k);
180 return element;
181 }else {
182 temp = temp.getRight();
183 k++;
184 }
185 }
186 if(k == (Length()-1)) {
187 System.out.println("该链表中没有该数据");
188 }
189 return element;
190 }
191
192 //修改下标index处的数据，并将原始数据返回
193 public T setElement(int index,T element) {
194 if(index < 0 || index >= Length()) return null;
195 Node<T> temp = head;
196 int k = 0;
197 while(k < index && temp.getRight() != head) {
198 k++;
199 temp = temp.getRight();
200 }
201 T tempEle = temp.getData();
202 temp.setData(element);
203 return tempEle;
204 }
205
206 //重写父类toString方法，实际是给list做遍历后将数据打印出来
207 public String toString() {
208 StringBuffer sb = new StringBuffer();
209 /*通过for循环遍历双向循环链表
210 int length = Length();
211 sb.append("[ ");
212 for(int i = 0; i < length; i++) {
213 sb.append(getElement(i)+" ");
214 }
215 sb.append("]");
216 */
217 //从表头开始遍历双向循环链表
218 sb.append("[ ");
219 Node<T> node = head;
220 while(node.getRight() != head) {
221 sb.append(node.getRight().getData()+" ");
222 node = node.getRight();
223 }
224 sb.append("]");
225 return sb.toString();
226 }
227
228 }
View Code
测试类
![]()
1 package list;
2
3 //************************************************
4 //*双向循环链表-java实现(画图分析会容易理解得多)
5 //************************************************
6
7 public class TestDoubleLinkedList {
8 public static void main(String[] args) {
9 Listable<String> list = new DoubleLinkedList<String>("a");
10 list.add("b");
11 list.add("c");
12 list.addByIndex(3,"e");
13 list.addByIndex(3,"d");
14 list.addByIndex(5,"f");
15 System.out.println(list);
16 list.addHead("A");
17 System.out.println(list.Length());
18 System.out.println(list);
19 Listable<String> list1 = new DoubleLinkedList<String>("123456");
20 list.add(list1);
21 System.out.println(list);
22 list.remove(100);
23 list.add("123456");
24 System.out.println("list="+list);
25 System.out.println(list1);
26 list1.removeAll();
27 System.out.println(list1+" list1 is Empty??"+list1.isEmpty());
28 list.remove("123456");
29 System.out.println("list="+list);
30 System.out.println("remove item="+list.remove("A"));
31 System.out.println("list="+list);
32 }
33 }
View Code
![]()
1 package list;
2
3 //************************************************
4 //*双向循环链表-java实现(画图分析会容易理解得多)
5 //************************************************
6
7 public class TestDoubleLinkedList {
8 public static void main(String[] args) {
9 Listable<String> list = new DoubleLinkedList<String>("a");
10 list.add("b");
11 list.add("c");
12 list.addByIndex(3,"e");
13 list.addByIndex(3,"d");
14 list.addByIndex(5,"f");
15 System.out.println(list);
16 list.addHead("A");
17 System.out.println(list.Length());
18 System.out.println(list);
19 Listable<String> list1 = new DoubleLinkedList<String>("123456");
20 list.add(list1);
21 System.out.println(list);
22 list.remove(100);
23 list.add("123456");
24 System.out.println("list="+list);
25 System.out.println(list1);
26 list1.removeAll();
27 System.out.println(list1+" list1 is Empty??"+list1.isEmpty());
28 list.remove("123456");
29 System.out.println("list="+list);
30 System.out.println("remove item="+list.remove("A"));
31 System.out.println("list="+list);
32 }
33 }
34
35 //结点类
36 class Node<T> {
37 private Node<T> left,right;
38 private T data;
39
40 Node(T data) {
41 this(data,null,null);
42 }
43
44 Node() {
45 this(null,null,null);
46 }
47
48 Node(T data,Node<T> left,Node<T> right) {
49 this.data = data;
50 this.left = left;
51 this.right = right;
52 }
53
54 public T getData() {
55 return this.data;
56 }
57
58 public Node<T> getLeft() {
59 return this.left;
60 }
61
62 public Node<T> getRight() {
63 return this.right;
64 }
65
66 public void setData(T data) {
67 this.data = data;
68 }
69
70 public void setRight(Node<T> right) {
71 this.right = right;
72 }
73
74 public void setLeft(Node<T> left) {
75 this.left = left;
76 }
77
78 public String toString() {
79 return getData().toString();
80 }
81 }
82
83 //接口实现类
84 class DoubleLinkedList<T> implements Listable<T> {
85 public Node<T> head;
86
87 //建空表,带头结点
88 DoubleLinkedList() {
89 this(null);
90 }
91
92 //建表，带头结点，表中有一条数据元素
93 DoubleLinkedList(T element) {
94 if(element == null) {
95 head = new Node<T>(element,null,null);
96 head.setRight(head);
97 head.setLeft(head);
98 }else {
99 Node<T> headRight = new Node<T>(element,null,null);
100 head = new Node<T>(null,headRight,headRight);
101 headRight.setLeft(head);
102 headRight.setRight(head);
103 }
104 }
105
106 //清空当前链表
107 public void clear() {}
108
109 //判空表
110 public boolean isEmpty() {
111 return head.getRight() == head;
112 }
113
114 //表长
115 public int Length() {
116 int len = 0;
117 Node<T> temp = head;
118 while(temp.getRight() != head) {
119 len++;
120 temp = temp.getRight();
121 }
122 return len;
123 }
124
125 //取下标index处的数据
126 public T getElement(int index) {
127 if(index <= 0) {
128 return head.getRight().getData();
129 }
130 int len = Length();
131 if(index >= len) {
132 return head.getLeft().getData();
133 }
134 T element = null;
135 if(index > 0 && index < len) {
136 int k = 0;
137 Node<T> temp = head;
138 //此处只能用while不能用if，用错好几次
139 while(k <= index && temp.getRight() != head) {
140 k++;
141 temp = temp.getRight();
142 }
143 element = temp.getData();
144 }
145 return element;
146 }
147
148 //尾添
149 public boolean add(T element) {
150 if(element == null) return false;
151 Node<T> node = new Node<T>(element,head.getLeft(),head);
152 head.getLeft().setRight(node);
153 head.setLeft(node);
154 return true;
155 }
156
157 //首添
158 public boolean addHead(T element) {
159 if(element == null) return false;
160 Node<T> node = new Node<T>(element,head,head.getRight());
161 head.getRight().setLeft(node);
162 head.setRight(node);
163 return false;
164 }
165
166 //表index处，添加新数据element
167 public boolean addByIndex(int index, T element) {
168 if(index <= 0) {
169 return addHead(element);
170 }else if(index >= Length()) {
171 return add(element);
172 }else {
173 int k = 0;
174 Node<T> temp = head;
175 //此处只能用while不能用if，用错好几次
176 while(k <= index && temp.getRight() != head) {
177 k++;
178 temp = temp.getRight();
179 }
180 Node<T> node = new Node<T>(element,temp.getLeft(),temp);
181 temp.getLeft().setRight(node);
182 temp.setLeft(node);
183 }
184 return true;
185 }
186
187 //将参数中的链表添加到当前链表的尾部
188 public boolean add(Listable<T> slist) {
189 if(slist.isEmpty() || slist == null) return false;
190 if(slist instanceof DoubleLinkedList) {
191 DoubleLinkedList<T> list = (DoubleLinkedList<T>)slist;
192 //以下操作影响到了添加的slist表，所以需要将slist表重新备份一个
193 DoubleLinkedList<T> temp = new DoubleLinkedList<T>();
194 for(int i = 0; i < list.Length(); i++) {
195 temp.add(list.getElement(i));
196 }
197 Node<T> node = temp.head;
198 Node<T> nodeLeft = node.getLeft();
199 Node<T> nodeRight = node.getRight();
200 this.head.getLeft().setRight(node.getRight());
201 nodeRight.setLeft(this.head.getLeft());
202 nodeLeft.setRight(this.head);
203 this.head.setLeft(node.getLeft());
204 return true;
205 }else {
206 return false;
207 }
208 }
209
210 //删除下标Index处的数据
211 public T remove(int index) {
212 if(isEmpty()) return null;
213 if(index < 0) {
214 index = 0;
215 }
216 int len = Length();
217 if(index >= len) {
218 //当index大于或等于表长是，默认移走表的最后一个元素，即下标为len-1的数据
219 index = len-1;
220 }
221 T element = null;
222 if(index >= 0 && index < len) {
223 Node<T> temp = head;
224 int k = 0;
225 while(k <= index && temp.getRight() != head) {
226 k++;
227 temp = temp.getRight();
228 }
229 element = temp.getData();
230 temp.getRight().setLeft(temp.getLeft());
231 temp.getLeft().setRight(temp.getRight());
232 temp.setRight(null);
233 temp.setLeft(null);
234 temp = null;
235 }
236 return element;
237 }
238
239 //删除当前链表中所有的数据，只剩头结点
240 public boolean removeAll() {
241 if(isEmpty()) return false;
242 Node<T> temp = head.getRight();
243 while(temp != head) {
244 head.setRight(temp.getRight());
245 temp.getRight().setLeft(head);
246 temp.setLeft(null);
247 temp.setRight(null);
248 temp = head.getRight();
249 }
250 return true;
251 }
252
253 //删除链表中从head开始的第一个element数据
254 public T remove(T element) {
255 if(isEmpty() || element == null) return null;
256 //从表中第一个元素开始比较
257 Node<T> temp = head.getRight();
258 int k=0;
259 while(temp != head) {
260 if(element.equals(temp.getData())) {
261 remove(k);
262 return element;
263 }else {
264 temp = temp.getRight();
265 k++;
266 }
267 }
268 if(k == (Length()-1)) {
269 System.out.println("该链表中没有该数据");
270 }
271 return element;
272 }
273
274 //修改下标index处的数据，并将原始数据返回
275 public T setElement(int index,T element) {
276 if(index < 0 || index >= Length()) return null;
277 Node<T> temp = head;
278 int k = 0;
279 while(k < index && temp.getRight() != head) {
280 k++;
281 temp = temp.getRight();
282 }
283 T tempEle = temp.getData();
284 temp.setData(element);
285 return tempEle;
286 }
287
288 //重写父类toString方法，实际是给list做遍历后将数据打印出来
289 public String toString() {
290 StringBuffer sb = new StringBuffer();
291 /*通过for循环遍历双向循环链表
292 int length = Length();
293 sb.append("[ ");
294 for(int i = 0; i < length; i++) {
295 sb.append(getElement(i)+" ");
296 }
297 sb.append("]");
298 */
299 //从表头开始遍历双向循环链表
300 sb.append("[ ");
301 Node<T> node = head;
302 while(node.getRight() != head) {
303 sb.append(node.getRight().getData()+" ");
304 node = node.getRight();
305 }
306 sb.append("]");
307 return sb.toString();
308 }
309
310 }
