双向链表的模仿实现 —— LinkedList

MyLinkedList类

2. public class MyLinkedList {
3.     // 定义节点类
4.     static class Node {
5.         int val;
6.         Node prev;
7.         Node next;
9.         public Node() {
11.         }
13.         public Node(int val) {
14.             this.val = val;
15.         }
16.     }
18.     // 定义头节点
19.     private Node head;
20.     // 定义尾结点
21.     private Node tail;
23.     // 头插
24.     public void headInsert(int val) {
25.         // 申请节点
26.         Node node = new Node(val);
27.         // 判空
28.         if (head == null) {
29.             // head 和 tail 都指向 node
30.             head = node;
31.             tail = node;
32.             return;
33.         }
34.         // head 不为空，则进行头插
35.         node.next = head;
36.         head.prev = node;
37.         // 重置头节点
38.         head = node;
39.     }
41.     // 尾插
42.     public void tailInsert(int val) {
43.         // 申请节点
44.         Node node = new Node(val);
46.         // 判空
47.         if (head == null) {
48.             head = node;
49.             tail = node;
50.             return;
51.         }
53.         // 非空情况下进行尾插
54.         tail.next = node;
55.         node.prev = tail;
56.         // 重置尾结点
57.         tail = node;
58.     }
60.     // 在 index 处插入元素
61.     public void randomInsert(int index, int val) {
62.         // 判空
63.         if (head == null) return;
64.         // 下标判断
65.         if (index < 0 || index > size()) {
66.             throw new IndexOfLinkedListException("下标 index :" + index + " 出现异常！");
67.         }
69.         // 头插
70.         if (index == 1) {
71.             headInsert(val);
72.             return;
73.         }
74.         // 尾插
75.         if (index == size()) {
76.             tailInsert(val);
77.             return;
78.         }
80.         // 找到要插入的位置
81.         Node cur = head;
82.         Node node = new Node(val);
83.         for (int i = 0; i < index; i++) {
84.             cur = cur.next;
85.         }
87.         // 进行插入
88.         cur.prev.next = node;
89.         node.next = cur;
90.         node.prev = cur.prev;
91.         cur.prev = node;
92.     }
94.     // 删除与 val 相等的元素节点
95.     public void remove(int val) {
96.         // 判空
97.         if (head == null) return;
99.         Node cur = head;
100.         while (cur != null) {
101.             // 值相等，进行删除
102.             if (cur.val == val) {
103.                 // 头节点的情况
104.                 if (cur == head) {
105.                     head = head.next;
106.                     head.prev = null;
107.                     break;
108.                 }
109.                 // 尾结点的情况
110.                 if (cur == tail) {
111.                     tail = tail.prev;
112.                     tail.next = null;
113.                     break;
114.                 }
116.                 // 中间节点删除
117.                 cur.prev.next = cur.next;
118.                 cur.next.prev = cur.prev;
119.             }
120.             cur = cur.next;
121.         }
122.     }
124.     // 删除 index 处的元素
125.     public void removeOfIndex(int index) {
126.         // 判空
127.         if (head == null) return;
129.         // 下标判断
130.         if (index < 0 || index > size()) {
131.             throw new IndexOfLinkedListException("下标 index :" + index + " 出现异常！");
132.         }
134.         // 头删
135.         if (index == 1) {
136.             head = head.next;
137.             head.prev = null;
138.             return;
139.         }
141.         // 尾删
142.         if (index == size()) {
143.             tail = tail.prev;
144.             tail.next = null;
145.             return;
146.         }
148.         // 找到要删除的位置
149.         Node cur = head;
150.         for (int i = 1; i < index; i++) {
151.             cur = cur.next;
152.         }
154.         // 进行删除操作
155.         cur.prev.next = cur.next;
156.         cur.next.prev = cur.prev;
157.     }
159.     // 删除所有与 val 相等的节点
160.     public void removeAllVal(int val) {
161.         // 判空
162.         if (head == null) return;
164.         // 判断 val 值是否在链表中出现
165.         if (!contains(val)) return;
167.         // 从头节点开发判断
168.         Node cur = head;
169.         while (cur != null) {
170.             // 相等则进行删除
171.             if (cur.val == val) {
172.                 // 是头节点的情况
173.                 if (head == cur) {
174.                     // head 走到下一个节点处
175.                     head = head.next;
176.                     head.prev = null;
177.                 } else if (tail == cur) {
178.                     // tail 走到上一个节点处
179.                     tail = tail.prev;
180.                     tail.next = null;
181.                 } else {
182.                     // 中间节点，让删除节点的前一个节点和后一个节点进行连接
183.                     cur.next.prev = cur.prev;
184.                     cur.prev.next = cur.next;
185.                 }
186.             }
187.             // 注意，cur 无论是否删除了当前节点，都应该要走到下一步
188.             cur = cur.next;
189.         }
190.     }
192.     // 查找 val 第一次出现的下标
193.     public int indexOf(int val) {
194.         // 判空
195.         if (head == null) return -1;
197.         Node cur = head;
198.         for (int i = 1; i < size() + 1; i++) {
199.             // 找到了
200.             if (cur.val == val) {
201.                 return i;
202.             }
203.             cur = cur.next;
204.         }
205.         // 没找到
206.         return -1;
207.     }
209.     // 查找 val 最后一次出现的下标
210.     public int lastOfIndex(int val) {
211.         // 判空
212.         if (head == null) return -1;
214.         int index = -1;
215.         Node cur = tail;
216.         for (int i = size(); i > 0; i--) {
217.             // 找到了
218.             if (cur.val == val) {
219.                 index = i;
220.             }
221.             cur = cur.prev;
222.         }
223.         // 没找到
224.         return index;
225.     }
227.     // 判断 val 是否在链表中
228.     public boolean contains(int val) {
229.         // 判空
230.         if (head == null) return false;
232.         Node cur = head;
233.         while (cur != null) {
234.             // 找到了
235.             if (cur.val == val) {
236.                 return true;
237.             }
238.             cur = cur.next;
239.         }
240.         // 没找到
241.         return false;
242.     }
244.     // 获取元素个数
245.     public int size() {
246.         Node cur = head;
247.         // 获取链表中的元素个数
248.         int count = 0;
250.         while (cur != null) {
251.             count++;
252.             cur = cur.next;
253.         }
254.         return count;
255.     }
257.     // 打印链表
258.     public void display() {
259.         Node cur = head;
260.         // 进行打印操作
261.         while (cur != null) {
262.             System.out.print(cur.val + " ");
263.             cur = cur.next;
264.         }
265.         // 换行
266.         System.out.println();
267.     }
269.     // 清空链表
270.     public void clear() {
271.         Node cur = head;
273.         // 把每个节点都置为 null
274.         while (cur != null) {
275.             Node tmp = cur.next;
276.             cur.next = null;
277.             cur.prev = null;
278.             cur = tmp;
279.         }
281.         // 头节点和尾结点置空
282.         head = null;
283.         tail = null;
284.     }
285. }

复制代码

 
IndexOfLinkedListException类

2. public class IndexOfLinkedListException extends RuntimeException {
3.     public IndexOfLinkedListException() {
4.     }
6.     public IndexOfLinkedListException(String message) {
7.         super(message);
8.     }
9. }

复制代码

 
 Test类

2. public class Test {
3.     public static void main(String[] args) {
4.         MyLinkedList linkedList = new MyLinkedList();
5.         // 头插
6.         linkedList.headInsert(1);
7.         linkedList.headInsert(2);
8.         linkedList.headInsert(3);
9.         // 打印链表
10.         linkedList.display();
11.         // 获取长度
12.         System.out.println(linkedList.size());
14.         // 尾插
15.         linkedList.tailInsert(4);
16.         linkedList.tailInsert(5);
17.         linkedList.tailInsert(6);
18.         linkedList.display();
19.         System.out.println(linkedList.size());
21.         // 任意位置插入
22.         linkedList.randomInsert(1, 7);
23.         linkedList.randomInsert(1, 7);
24.         linkedList.randomInsert(1, 7);
25.         linkedList.randomInsert(8, 8);
26.         linkedList.display();
27.         linkedList.randomInsert(8, 7);
28.         linkedList.display();
29.         linkedList.randomInsert(8, 8);
30.         linkedList.display();
31.         System.out.println(linkedList.size());
32.         linkedList.randomInsert(2, 111);
33.         linkedList.randomInsert(3, 111);
34.         linkedList.display();
35.         System.out.println(linkedList.size());
37.         // 删除所有和 val 相等的节点
38.         linkedList.removeAllVal(7);
39.         linkedList.display();
40.         System.out.println(linkedList.size());
42.         // 删除链表中第一个 val 相等的节点
43.         linkedList.remove(111);
44.         linkedList.remove(6);
45.         linkedList.remove(3);
46.         linkedList.display();
47.         System.out.println(linkedList.size());
49.         // 删除 index 处的节点
50.         linkedList.removeOfIndex(1);
51.         linkedList.removeOfIndex(6);
52.         linkedList.removeOfIndex(2);
53.         linkedList.display();
54.         System.out.println(linkedList.size());
56.         // 找到 val 第一次出现的位置
57.         System.out.println(linkedList.indexOf(2));
58.         System.out.println(linkedList.indexOf(8));
60.         // 找到val 最后一次出现的位置
61.         System.out.println(linkedList.lastOfIndex(2));
62.         System.out.println(linkedList.lastOfIndex(8));
64.         // 清空链表
65.         linkedList.clear();
66.         System.out.println(linkedList.size());
67.     }
68. }

复制代码