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

1. public class MySingleLinkedList {
2. 
3. static class ListNode {
4. public int value;
5. public ListNode next;
6. 
7. public ListNode(int value) {
8. this.value = value;
9.         }
10.     }
11. 
12. 
13. public ListNode head;
14. 
15. //头插法
16. public void addFirst(int data) {
17. ListNode node = new ListNode(data);
18.         node.next = head;
19.         head = node;
20.     }
21. 
22. //尾插法
23. public void addLast(int data) {
24. ListNode node = new ListNode(data);
25. //1.链表为空
26. if(this.head == null) {
27. this.head = node;
28.         } else {
29. //2.链表不为空
30. ListNode cur = this.head;
31. while(cur.next != null) {
32.                 cur = cur.next;
33.             }
34.             cur.next = node;
35.         }
36.     }
37. 
38. public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
39. //1.先检查插入位置是否合法
40.         checkAddIndex(index);
41. //2.分两种情况：1.头插 2.中间位置和尾插
42. ListNode node = new ListNode(data);
43. if(this.head == null) {
44. this.head = node;
45. return;
46.         }
47. if(index == 0) {
48.             addFirst(data);
49. return;
50.         }
51. ListNode cur = findAddIndexSubOne(index);
52.         node.next = cur.next;
53.         cur.next = node;
54.     }
55. private void checkAddIndex(int index) {
56. if(index < 0 || index > this.size()) {
57. throw new MySingleListIndexOutOfException("任意位置插入时，index不合法！");
58.         }
59.     }
60. //找到待插入位置的前一个结点
61. private ListNode findAddIndexSubOne(int index) {
62. ListNode cur = this.head;
63. while(index - 1 != 0) {
64.             cur = cur.next;
65.             index--;
66.         }
67. return cur;
68.     }
69. 
70. public boolean contains(int key) {
71. if(this.head == null) {
72.             System.out.println("链表为空！");
73. return false;
74.         }
75. ListNode cur = this.head;
76. while(cur != null) {
77. if(cur.value == key) {
78. return true;
79.             }
80.             cur = cur.next;
81.         }
82. return false;
83.     }
84. 
85. //删除第一次出现关键字为key的节点
86. public void remove(int key) {
87. //1.判断有无结点
88. if(this.head == null) {
89.             System.out.println("链表为空，不能删除！");
90. return;
91.         }
92. 
93. //2.删第一个
94. if(this.head.value == key) {
95. this.head = this.head.next;
96. return;
97.         }
98. //3.删后面的
99. ListNode cur = this.head;
100.         cur = removeSubOne(key,cur);
101. if(cur == null) {
102.             System.out.println("链表中没有这个元素！");
103. return;
104.         }
105.         cur.next = cur.next.next;
106.     }
107. private ListNode removeSubOne(int key, ListNode cur) {
108. while(cur.next != null) {
109. if(cur.next.value == key) {
110. return cur;
111.             }
112.             cur = cur.next;
113.         }
114. return null;
115.     }
116. 
117. public void removeAllKey(int key) {
118. //1.判断有无结点
119. if (this.head == null) {
120.             System.out.println("链表为空，不能删除！");
121. return;
122.         }
123. 
124. //处理中间和尾巴
125. ListNode cur = this.head;
126. while (cur != null) {
127. //removeSubOne函数在上一个删除方法里头
128.             cur = removeSubOne(key, cur);
129. if (cur != null) {
130.                 cur.next = cur.next.next;
131.             }
132.         }
133. 
134. //处理头
135. if (this.head.value == key) {
136. this.head = this.head.next;
137.         }
138.     }
139. 
140. //得到单链表的长度
141. public int size() {
142. ListNode cur = this.head;
143. int count = 0;
144. while(cur != null) {
145.             count++;
146.             cur = cur.next;
147.         }
148. return count;
149.     }
150. public void display() {
151. ListNode cur = this.head;
152. while(cur != null) {
153.             System.out.print(cur.value+" ");
154.             cur = cur.next;
155.         }
156.         System.out.println();
157.     }
158. public void clear() {
159. this.head = null;
160.     }
161. 
162. }

1. public class MySingleListIndexOutOfException extends RuntimeException{
2. public MySingleListIndexOutOfException() {
3.     }
4. 
5. public MySingleListIndexOutOfException(String message) {
6. super(message);
7.     }
8. }

1. public class Test {
2. public static void main(String[] args) {
3.         MySingleLinkedList mySingleLinkedList=new MySingleLinkedList();
4.         mySingleLinkedList.addFirst(1);
5.         mySingleLinkedList.addFirst(2);
6.         mySingleLinkedList.addFirst(3);
7.         mySingleLinkedList.display();
8.         System.out.println("=============================");
9.         mySingleLinkedList.addLast(9);
10.         mySingleLinkedList.addLast(10);
11.         mySingleLinkedList.addLast(10);
12.         mySingleLinkedList.display();
13.         System.out.println("================================");
14.         System.out.println(mySingleLinkedList.size());
15.         System.out.println("==================================");
16.         mySingleLinkedList.addIndex(0,999);
17.         mySingleLinkedList.addIndex(2,888);
18.         mySingleLinkedList.addIndex(7,10001);
19.         mySingleLinkedList.display();
20.         System.out.println("=================================");
21.         mySingleLinkedList.remove(2);
22.         mySingleLinkedList.display();;
23.         mySingleLinkedList.removeAllKey(10);
24.         mySingleLinkedList.display();
25.         System.out.println("===================================");
26.         System.out.println(mySingleLinkedList.contains(888));
27. 
28.     }
29. }