手写 JDK 的 LinkedList 实现

前言

这里将参考 JDK 的 LinkedList 底层源码,模拟手写一个简易版的 LinkedList。

代码

  • 定义接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public interface MyList<E> {

/**
* 添加节点
*/
void add(E element);

/**
* 设置节点
*/
E set(int index, E element);

/**
* 获取节点
*/
E get(int index);

/**
* 删除节点
*/
E remove(int index);

/**
* 清空链表节点
*/
void clear();

/**
* 获取节点数量
*/
int size();

}
  • 基于双向链表实现 LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
public class MyLinkedList<E> implements MyList<E> {

private int size = 0; // 链表节点的数量

private Node<E> first; // 头节点

private Node<E> last; // 尾节点

public MyLinkedList() {

}

/**
* 添加节点到链表的尾部
*/
private void linkLast(E element) {
Node<E> l = last;
Node<E> newNode = new Node<>(l, element, null);
last = newNode;
// 判断是否首次添加节点
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}

/**
* 移除节点
*/
private E unlink(Node<E> node) {
E data = node.data;
Node<E> prev = node.prev;
Node<E> next = node.next;

// 判断是否移除头节点
if (prev == null) {
first = next;
} else {
prev.next = next;
node.prev = null;
}

// 判断是否移除尾节点
if (next == null) {
last = prev;
} else {
next.prev = prev;
node.next = null;
}

node.data = null;
size--;
return data;
}

/**
* 检查索引范围
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException();
}
}

/**
* 检查索引范围
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}

/**
* 获取指定位置的节点
*/
private Node<E> node(int index) {
checkElementIndex(index);
Node<E> cur = first;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}

@Override
public void add(E element) {
linkLast(element);
}

@Override
public E set(int index, E element) {
Node<E> node = node(index);
E oldData = node.data;
node.data = element;
return oldData;
}

@Override
public E get(int index) {
Node<E> node = node(index);
return node.data;
}

@Override
public E remove(int index) {
Node<E> node = node(index);
return unlink(node);
}

@Override
public void clear() {
Node<E> cur = first;
while (cur != null) {
Node<E> next = cur.next;
// GC
cur.prev = null;
cur.next = null;
cur.data = null;
cur = next;
}
first = null;
last = null;
size = 0;
}

@Override
public int size() {
return size;
}

@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
Node<E> cur = first;
while (cur != null) {
stringBuilder.append(cur.data);
if (cur != last) {
stringBuilder.append(", ");
}
cur = cur.next;
}
stringBuilder.append("]");
return stringBuilder.toString();
}

/**
* 节点
*/
static class Node<E> {

/**
* 数据
*/
E data;

/**
* 上一个节点
*/
Node<E> prev;

/**
* 下一个节点
*/
Node<E> next;

Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.next = next;
this.data = element;
}

}

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class MyLinkedListTest {

public static void main(String[] args) {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.add(13);
list.add(12);
list.add(11);
list.add(14);
list.add(17);
list.add(15);
list.add(18);
System.out.println(list);

Integer value = list.get(5);
System.out.println("value = " + value);

Integer oldValue = list.set(1, 23);
System.out.println("oldValue = " + oldValue);
System.out.println(list);

list.remove(1);
list.remove(1);
list.remove(1);
System.out.println(list);
System.out.println("size = " + list.size());

list.clear();
System.out.println(list);
System.out.println("size = " + list.size());
}

}

输出结果:

1
2
3
4
5
6
7
8
[13, 12, 11, 14, 17, 15, 18]
value = 15
oldValue = 12
[13, 23, 11, 14, 17, 15, 18]
[13, 17, 15, 18]
size = 4
[]
size = 0