【Java数据结构】实现双链表

1. public class MyLinkedList {
2. 
3. static  class ListNode{
4. 
5. private int data;
6. private ListNode next;
7. private ListNode pre;
8. public ListNode(){
9. 
10.         }
11. 
12. public ListNode(int data) {
13. this.data = data;
14. 
15.        }
16.    }
17. 
18.     ListNode head;
19.     ListNode tail;
20. 
21. // 2、无头双向链表实现
22. 
23. //头插法
24. public  void addFirst(int data){
25. 
26.         ListNode node=new ListNode(data);
27. 
28. if(this.head==null){
29. this.head=node;
30. this.tail=node;
31.         }else{
32.            node.next=this.head;
33.             head.pre=node;
34. this.head=node;
35.         }
36. 
37.         }
38. //尾插法
39. public void addLast(int data){
40.             ListNode node=new ListNode(data);
41.             ListNode cur=this.tail;
42. if(this.head==null){
43. this.head=node;
44. this.tail=node;
45.             }else{
46. 
47.                 cur.next=node;
48.                 node.pre=cur;
49. this.tail=node;
50.             }
51. 
52. 
53. 
54.         }
55. //任意位置插入,第一个数据节点为0号下标
56. public boolean addIndex(int index,int data){
57. ListNode node =new ListNode(data);
58. 
59. if(index<0||index>size()){
60. return false;
61.             }
62. if(index==0){
63.                 addFirst(data);
64. return true;
65.             }
66. if(index==size()){
67.                 addLast(data);
68. return true;
69.             }
70.             ListNode cur=this.head;
71. if(index!=0){
72.                 cur=cur.next;
73.                 index--;
74.             }
75.             node.next=cur;
76.             cur.pre.next=node;
77.             node.pre=cur.pre;
78.             cur.pre=node;
79. 
80. return true;
81. 
82.         }
83. //查找是否包含关键字key是否在单链表当中
84. public boolean contains(int key){
85.             ListNode cur=this.head;
86. while (cur!=null){
87. if(cur.data==key){
88. return true;
89.                 }else {
90.                     cur=cur.next;
91.                 }
92.             }
93. return false;
94.         }
95. //删除第一次出现关键字为key的节点
96. public void remove(int key){
97. if(this.head==null){
98. return;
99.             }
100.             ListNode cur=this.head;
101. while (cur!=null){
102. if(cur.data==key){
103. if(this.head.data==key){
104. this.head=this.head.next;
105. if(head!=null){
106.                             head.pre=null;
107.                         }else{
108. this.tail=null;
109.                         }
110.                     }  else{
111.                         cur.pre.next=cur.next;
112. if(cur.next!=null){
113.                             cur.next.pre=cur.pre;
114.                         }else{
115. this.tail=cur.pre;
116.                         }
117. 
118.                     }
119. 
120. break;
121.                 }else{
122.                     cur=cur.next;
123. 
124.                 }
125.             }
126. 
127.         }
128. //删除所有值为key的节点
129. public void removeAllKey(int key){
130. if(this.head==null){
131. return;
132.             }
133.             ListNode cur=this.head;
134. while (cur!=null){
135. if(cur.data==key){
136. if(this.head.data==key){
137. this.head=this.head.next;
138. if(head!=null){
139.                             head.pre=null;
140.                         }else{
141. this.tail=null;
142.                         }
143.                     }  else{
144.                         cur.pre.next=cur.next;
145. if(cur.next!=null){
146.                             cur.next.pre=cur.pre;
147.                         }else{
148. this.tail=cur.pre;
149.                         }
150.                     }
151.                 }
152.                     cur=cur.next;
153. 
154. 
155.             }
156. 
157. 
158. 
159.         }
160. //得到单链表的长度
161. public int size(){
162.             ListNode cur=this.head;
163. int count=0;
164. while(cur!=null){
165.                 count++;
166.                 cur=cur.next;
167.             }
168. return count;
169. 
170.         }
171. public void display(){
172. 
173.             ListNode cur=this.head;
174. while(cur!=null){
175.                 System.out.print(cur.data+" ");
176.                 cur=cur.next;
177.             }
178.             System.out.println();
179. 
180.         }
181. public void clear(){
182. 
183.             ListNode cur=this.head;
184. while(cur!=null){
185.                 ListNode curNext=cur.next;
186.                 cur.pre=null;
187.                 cur.next=null;
188.                 cur=curNext;
189.             }
190. 
191. this.head=null;
192. this.tail=null;
193. 
194.         }
195. 
196. }

1. public class Test {
2. public static void main(String[] args) {
3.         MyLinkedList myLinkedList=new MyLinkedList();
4. 
5.         myLinkedList.addFirst(1);
6.         myLinkedList.addFirst(2);
7.         myLinkedList.addFirst(3);
8.         myLinkedList.display();
9.         System.out.println("==========================");
10.         myLinkedList.addLast(4);
11.         myLinkedList.addLast(5);
12.         myLinkedList.addLast(6);
13.         myLinkedList.display();
14.         System.out.println("====================");
15.         System.out.println(myLinkedList.size());
16.         System.out.println("==========================");
17. //        myLinkedList.clear();
18. //        myLinkedList.display();
19.           myLinkedList.remove(5);
20.           myLinkedList.display();
21.         System.out.println("=============================");
22.         System.out.println(myLinkedList.contains(6));
23.         System.out.println("=============================");
24.         myLinkedList.addLast(9);
25.         myLinkedList.addLast(9);
26.         myLinkedList.addLast(9);
27.         myLinkedList.display();
28.         System.out.println("=====================");
29.         myLinkedList.removeAllKey(9);
30.         myLinkedList.display();
31.         System.out.println("=======================");
32.         System.out.println(myLinkedList.addIndex(2, 8888));
33.         System.out.println(myLinkedList.addIndex(0, 6666));
34.         System.out.println(myLinkedList.addIndex(7, 168168));
35.         myLinkedList.display();
36. 
37. 
38.     }
39. }