java数据结构之循环双链表

我就是我 2022-08-22 15:15 256阅读 0赞

感谢[tu451953337][]的分享 原文链接地址：[点击打开链接][Link 1]

这个循环双链表写的相当不错，注释解析也很清晰。是个不错的博文！

1.  **public** **class** DbLinkedList<T>  
2.  \{  
3.        
4.      //定义内部类，用作链表的节点  
5.      **private** **class** Node<T>  
6.      \{  
7.          Node<T> pre; //指向前一个节点  
8.          Node<T> next; //指向后一个节点  
9.          T value;  //当前节点的值  
10.           
11.         **public** Node(T value, Node<T> next, Node<T> pre)  
12.         \{  
13.             **this**.value = value;  
14.             **this**.next = next;  
15.             **this**.pre = pre;  
16.         \}  
17.           
18.         **public** String toString()  
19.         \{  
20.             **return** **this**.value + "";  
21.         \}  
22.     \}  
23.       
24.     **private** Node<T> header;  //定义头节点  
25.     **private** **int** size;  //定义链表的长度  
26.       
27.     **public** DbLinkedList()  
28.     \{  
29.         header = **new** Node<T>(**null**, **null**, **null**);//空的头节点，用来区分双向循环链表的首尾  
30.         header.pre = header.next = header; //双向循环链表，首尾相连  
31.         size = 0;  
32.     \}  
33.       
34.     **public** DbLinkedList(Collection<? **extends** T> collection)  
35.     \{  
36.         **this**();  
37.         addAll(**this**.size, collection);  
38.     \}  
39.       
40.     **public** **boolean** add(T value)//在链表的尾巴上面加一个节点, 相当于在header节点前面加一个节点  
41.     \{  
42.         **return** add(header, value);  
43.     \}  
44.       
45.     **public** **boolean** add(**int** index, T value)//指定index处加入节点  
46.     \{  
47.         **return** add(entry(index), value);  
48.     \}  
49.       
50.     **public** **boolean** remove(Object obj)//删除指定value的节点  
51.     \{  
52.         Node<T> node;  
53.         //1. 从header.next往后遍历，再到header时结束  
54.         **for**(node = header.next; node!=header; node=node.next)  
55.         \{  
56.             **if**(node.value == obj || (obj!=**null** && obj.equals(node.value)))  
57.             \{  
58.                 remove(node);  
59.                 **return** **true**;  
60.             \}  
61.         \}  
62.         //2.java.util.LinkedList实现，先区分null再遍历，个人感觉效率差不多呀，希望有人赐教  
63.         /\* 
64.         if(obj==null) 
65.         \{  
66.             for(node = header.next; node!=header; node=node.next) 
67.             \{  
68.                 if(node.value == null) 
69.                 \{  
70.                     remove(node); 
71.                     return true; 
72.                 \} 
73.             \} 
74.         \} 
75.         else 
76.         \{  
77.             for(node = header.next; node!=header; node=node.next) 
78.             \{  
79.                 if(node.value == obj || obj.equals(node.value)) 
80.                 \{  
81.                     remove(node); 
82.                     return true; 
83.                 \} 
84.             \} 
85.         \} 
86.         \*/  
87.         **return** **false**;  
88.     \}  
89.       
90.     **public** T remove(**int** index)//删除指定index节点  
91.     \{  
92.         **return** remove(entry(index));  
93.     \}  
94.       
95.     **public** **boolean** addAll(Collection<? **extends** T> collection)  
96.     \{  
97.         **return** addAll(**this**.size, collection);  
98.     \}  
99.       
100.     //在指定index位置添加collection里的所有元素  
101.     **public** **boolean** addAll(**int** index, Collection<? **extends** T> collection)  
102.     \{  
103.         **if**(collection==**null** || collection.size()==0)  
104.         \{  
105.             **return** **false**;  
106.         \}  
107.         //获取指定位置节点，如果index==size，则在末尾添加节点，即header节点之前  
108.         //当index==size时，调用entry方法会抛异常，所以三则表达式很有必要  
109.         Node<T> node = index == **this**.size ? **this**.header : entry(index);  
110.         Object\[\] objArray = collection.toArray();  
111.         **int** len = objArray.length;  
112.         Node<T> preNode = node.pre;  
113.         **for**(**int** i=0; i<len; i++)  
114.         \{  
115.             //新建一个节点，新节点的next指向node，新节点的pre指向node的pre  
116.             //完成指向过程node.pre←newNode→node  
117.             //当第二次迭代时，preNode=newNode1(i=1创建的newNode), newNode1←newNode2(i=2创建的newNode)→node  
118.             Node<T> newNode = **new** Node<T>((T) objArray\[i\], node, preNode);  
119.             //维持双向链表的指向，将node的pre节点的next指向新节点,完成指向过程node.pre→newNode  
120.             //当第二次迭代时，newNode1→newNode2  
121.             preNode.next = newNode;  
122.             //将preNode指向newNode，当第二次迭代时，preNode往后移动一位  
123.             preNode = newNode;  
124.         \}  
125.         //迭代完成后，node的前一个节点指向preNode（即最后一次创建的newNode），preNode←node  
126.         //如果len=2,完成的链就变成这样preNode→←newNode1→←newNode2→←node  
127.         node.pre = preNode;  
128.         //长度加len  
129.         **this**.size += len;  
130.         **return** **true**;  
131.     \}  
132.       
133.     **private** T remove(Node<T> node)  
134.     \{  
135.         //node的前一个节点next指向node的下一个节点  
136.         //node的下一个节点pre指向node的前一个节点  
137.         //A→node←B改成A→←B  
138.         node.pre.next = node.next;  
139.         node.next.pre = node.pre;  
140.         //node的前后指向null  
141.         //A←node→B改成null←node→null  
142.         node.pre = node.next = **null**;  
143.         T value = node.value;  
144.         node.value = **null**;  
145.         **this**.size--;  
146.         **return** value;  
147.     \}  
148.       
149.     **public** T get(**int** index)  
150.     \{  
151.         **return** entry(index).value;  
152.     \}  
153.       
154.     **private** Node<T> entry(**int** index) //迭代至index处的节点  
155.     \{  
156.         rangeIndex(index); //判断index是否越界  
157.           
158.         Node<T> node = **this**.header;  
159.         //判断index是否小于size的一半，如果小于就从header往后开始迭代，否则就从header往前开始迭代，提高效率  
160.         //例如有一个链表header→A→B→C→D→header  
161.         **if**(index < (**this**.size>>1))  
162.         \{  
163.             //因为header是空的头节点，所以i要小于等于index  
164.             //例如index=1， 小于size的一半2  
165.             //i=0时，node=A  
166.             //i=1时，node=B，然后跳出循环  
167.             **for**(**int** i=0; i<=index; i++)  
168.             \{  
169.                 node = node.next;  
170.             \}  
171.         \}  
172.         **else**  
173.         \{  
174.             //例如index=2，不小size的一半  
175.             //i=3, node等于header的前一个， node=D  
176.             //i=2, node=C，然后跳出循环  
177.             **for**(**int** i=**this**.size-1; i>=index; i--)  
178.             \{  
179.                 node = node.pre;  
180.             \}  
181.         \}  
182.         **return** node;  
183.     \}  
184.       
185.     **private** **void** rangeIndex(**int** index)  
186.     \{  
187.         **if**(index < 0 || index >= **this**.size)  
188.         \{  
189.             **throw** **new** IndexOutOfBoundsException("index错误");  
190.         \}  
191.     \}  
192.       
193.     **private** **boolean** add(Node<T> node, T value)  
194.     \{  
195.         //新建一个节点，新节点的next指向node，新节点的pre指向node的pre  
196.         //完成指向过程node.pre←newNode→node  
197.         Node<T> newNode = **new** Node<T>(value, node, node.pre);  
198.         //维持双向链表的指向，将node的pre节点的next指向新节点,完成指向过程node.pre→newNode  
199.         node.pre.next = newNode;  
200.         //node节点的前一个节点指向新节点，完成指向过程newNode←node  
201.         node.pre = newNode;  
202.         //上面两行代码不能颠倒，否则node的前一个节点会被覆盖成新节点，会丢失node原来的前一个节点的next指向  
203.         //上述代码完成了在node节点和node前一个节点之间加入一个新节点，并维护了双向关系  
204.         **this**.size++;  
205.         **return** **true**;  
206.     \}  
207.       
208.     **public** **void** clear()  
209.     \{  
210.         Node<T> node = header.next;  
211.         //将每一个节点的双向指向都清空，这样每个节点都没有被引用，可以方便垃圾回收器回收内存  
212.         **while**(node != header)  
213.         \{  
214.             //将node的下一个节点临时保存起来  
215.             Node<T> tempNode = node.next;  
216.             //将node的下一个节点和上一个节点置空  
217.             node.next = node.pre = **null**;  
218.             //将node的值也置空  
219.             node.value = **null**;  
220.             //将node移动到下一个节点  
221.             node = tempNode;  
222.         \}  
223.         //清空header的双向指向null  
224.         **this**.header.next = **this**.header.pre = **this**.header;  
225.         **this**.size = 0;  
226.     \}  
227.       
228.     **public** **boolean** isEmpty()  
229.     \{  
230.         **return** **this**.size == 0;  
231.     \}  
232.       
233.     **public** **int** size()  
234.     \{  
235.         **return** **this**.size;  
236.     \}  
237. \}

**如果有什么不清楚或者有啥疑问意见可以加我QQ/[微信][Link 2]  208017534  / qiang220316，欢迎一起交流一起进步。**

**![Center][]**

[tu451953337]: http://my.csdn.net/tu451953337
[Link 1]: http://blog.csdn.net/tu451953337/article/details/36673671
[Link 2]: http://lib.csdn.net/base/5
[Center]: /images/20220722/32eda723ce2242ca8afc2bbdc3d81503.png