pexels-photo-1322185

链表

定义

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向 NULL (空)）。这种结构成为 “单向链表 “。

SingleLinkedList

在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为 “双向链表” 或者 “双链表”。

DoublyLinkedList

当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。

SinglyCircularLinkedList

当双向链表的头部和尾部相互指向时，就构成了双向循环链表。

DoublyCircularLinkedList

单向链表

单向链表在插入元素、删除元素时，需要获取前驱元素，需要从 head 开始遍历，时间复杂度为 O (n)。

根据 index 查询对应元素，也需要从 head 开始遍历，时间复杂度为 O (n)。

代码实现

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Single Linked List
 *
 * @author https://wangwei.one
 * @date 2018/12/25
 */
public class SingleLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head node
     */
    private Node<T> head;
    /**
     * tail node
     */
    private Node<T> tail;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(null, element);
        tail = newNode;
        // if linked list is empty
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param index
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        checkPositionIndex(index);
        // prev node
        Node<T> prev = null;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }
        // current node
        Node<T> current = x;
        // new node
        Node<T> newNode = new Node<>(current, element);
        // if current node is head
        if (prev == null) {
            head = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * remove element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        Node<T> prev = null;
        Node<T> x = head;
        if (element == null) {
            while (x != null && x.element != null) {
                prev = x;
                x = x.next;
            }
        } else {
            while (x != null && !x.element.equals(element)) {
                prev = x;
                x = x.next;
            }
        }

        // if this linked is null OR don't find element
        if (x == null) {
            return false;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        // if delete node is tail
        if (next == null) {
            tail = prev;
        }

        // for GC
        x.element = null;
        x = null;

        size--;
        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> prev = null;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }

        // if delete node is tail
        if (next == null) {
            tail = prev;
        }
        size--;
        return x.element;
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return old element
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> node = node(index);
        T oldElement = node.element;
        node.element = element;
        return oldElement;
    }
    
    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        Node<T> node = node(index);
        return node == null ? null : node.element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    /**
     * check index
     *
     * @param index
     */
    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element.equals(element)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Linked List Node
     *
     * @param <T>
     */
    private class Node<T> {
        private Node<T> next;
        private T element;

        public Node(Node<T> next, T element) {
            this.next = next;
            this.element = element;
        }
    }
}

源码

双向链表

相比于单向链表，双向链表多了一个前驱指针，在查找前驱节点时，时间复杂度降低为了 O (1)。

通过 index 查询，删除某个 node 节点，时间复杂度都降为了 O (1)。代码如下：

代码实现

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Doubly Linked List
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2018/04/28
 */
public class DoublyLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head element
     */
    private Node<T> head = null;
    /**
     * tail element
     */
    private Node<T> tail = null;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(element, node(index));
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        final Node<T> last = tail;
        Node<T> newNode = new Node<>(last, element, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param element
     * @param target
     * @return
     */
    private boolean addBefore(T element, Node<T> target) {
        Node<T> prev = target.prev;
        Node<T> newNode = new Node<>(prev, element, target);
        target.prev = newNode;
        if (prev == null) {
            head = newNode;
        } else {
            prev.next = newNode;
        }
        size++;
        return true;
    }

    /**
     * remove node by element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (element.equals(x.element)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * remove node by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        return unlink(node(index));
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        if (index < (size >> 1)) {
            Node<T> x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    /**
     * unlink node
     *
     * @param node
     */
    private T unlink(Node<T> node) {
        final T element = node.element;
        final Node<T> prev = node.prev;
        final Node<T> next = node.next;

        // if unlink is head
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            // clear prev
            node.prev = null;
        }

        // if unlink is tail
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

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

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        Node<T> node = node(index);
        return node == null ? null : node.element;
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (element == null) {
            for (Node<T> x = head; x != null; x = x.next) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = head; x != null; x = x.next) {
                if (element.equals(x.element)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * node
     *
     * @param <T>
     */
    private class Node<T> {

        private T element;
        private Node<T> prev;
        private Node<T> next;

        public Node(Node<T> prev, T element, Node<T> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }

}

源代码

单向循环链表

与单向链表一样，在寻找前驱节点时，需要遍历整个链表，时间复杂度为 O (n).

在第一次添加元素时，特别注意，head 与 tail 为同一节点，并且需要自指向。

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Singly Circular Linked List
 *
 * @param <T>
 * @author https://wangwei.one
 * @date 2018/05/03
 */
public class SinglyCircularLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size = 0;
    /**
     * head node
     */
    private Node<T> head = null;
    /**
     * tail node
     */
    private Node<T> tail = null;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add Last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        final Node<T> last = tail;
        Node<T> newElement = new Node<>(element, head);
        tail = newElement;
        if (last == null) {
            head = newElement;
            // we need linked itself when add an element at first time
            tail.next = head;
        } else {
            last.next = newElement;
        }
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param element
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        checkPositionIndex(index);
        // prev node, start with tail
        Node<T> prev = tail;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }
        // current node
        Node<T> current = x;
        // new node
        Node<T> newNode = new Node<>(element, current);
        if (index == 0) {
            head = newNode;
        }
        prev.next = newNode;
        size++;
        return true;
    }

    /**
     * remove node by element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        // start with tail
        Node<T> prev = tail;
        // start with head
        Node<T> x = head;
        // start with index -1
        int prevIndex = -1;

        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                break;
            }
            if (element != null && element.equals(x.element)) {
                break;
            }
            prev = x;
            x = x.next;
            prevIndex = i;
        }

        // if this linked list is empty
        if (x == null) {
            return false;
        }

        // if don't match element
        if (prevIndex == size - 1) {
            return false;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (prevIndex == -1) {
            head = next;
        }

        // if delete node is tail
        if (prevIndex == size - 2) {
            tail = prev;
        }

        prev.next = next;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        // for GC
        x = null;

        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> prev = tail;
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            prev = x;
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> next = x.next;

        // if delete node is head
        if (index == 0) {
            head = next;
        }

        // if delete node is tail
        if (index == size - 1) {
            tail = prev;
        }

        prev.next = next;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        return x.element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public T set(int index, T element) {
        checkPositionIndex(index);
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return node(index).element;
    }

    /**
     * clear list element
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     */
    @Override
    public boolean contains(T element) {
        if (head == null) {
            return false;
        }
        Node<T> x = head;
        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                return true;
            }
            if (element != null && element.equals(x.element)) {
                return true;
            }
            x = x.next;
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private class Node<T> {

        private T element;
        private Node<T> next;

        public Node(T element, Node<T> next) {
            this.element = element;
            this.next = next;
        }
    }
}

源代码

双向循环链表

双向循环链表相比单向循环链表，降低了查找前驱节点的复杂度，时间复杂度为 O (1).

同样第一次添加元素时，head 与 tail 为同一元素，需要自指向。

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
package one.wangwei.algorithms.datastructures.list.impl;

import one.wangwei.algorithms.datastructures.list.IList;

/**
 * Doubly circular linked list
 *
 * @author https://wangwei.one
 * @date 2018/12/21
 */
public class DoublyCircularLinkedList<T> implements IList<T> {

    /**
     * size
     */
    private int size;
    /**
     * head node
     */
    private Node<T> head;
    /**
     * tail node
     */
    private Node<T> tail;

    /**
     * add element
     *
     * @param element
     * @return
     */
    @Override
    public boolean add(T element) {
        return addLast(element);
    }

    /**
     * add element at index
     *
     * @param index
     * @param element
     * @return
     */
    @Override
    public boolean add(int index, T element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            return add(element);
        } else {
            return addBefore(index, element);
        }
    }

    /**
     * Add last element
     *
     * @param element
     * @return
     */
    private boolean addLast(T element) {
        Node<T> last = tail;
        Node<T> newNode = new Node<>(element, last, head);
        tail = newNode;
        // add element at first time
        if (last == null) {
            head = newNode;
            tail.next = head;
        } else {
            last.next = newNode;
        }
        head.prev = tail;
        size++;
        return true;
    }

    /**
     * add element before certain element
     *
     * @param index
     * @param element
     * @return
     */
    private boolean addBefore(int index, T element) {
        Node<T> target = node(index);
        Node<T> prev = target.prev;
        Node<T> newNode = new Node<>(element, prev, target);

        prev.next = newNode;
        target.prev = newNode;

        if (index == 0) {
            head = newNode;
        }

        size++;
        return true;
    }

    /**
     * remove element
     *
     * @param element
     * @return
     */
    @Override
    public boolean remove(T element) {
        // start with head
        Node<T> x = head;
        // start with index -1
        int prevIndex = -1;

        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                break;
            }
            if (element != null && element.equals(x.element)) {
                break;
            }
            x = x.next;
            prevIndex = i;
        }

        // if this linked list is empty
        if (x == null) {
            return false;
        }

        // if don't match element
        if (prevIndex == size - 1) {
            return false;
        }

        Node<T> prev = x.prev;
        Node<T> next = x.next;

        // if delete node is head
        if (prevIndex == -1) {
            head = next;
        }

        // if delete node is tail
        if (prevIndex == size - 2) {
            tail = prev;
        }

        prev.next = next;
        next.prev = prev;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        // for GC
        x = null;

        return true;
    }

    /**
     * remove element by index
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        checkPositionIndex(index);
        Node<T> x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        // if linked is empty
        if (x == null) {
            return null;
        }

        Node<T> prev = x.prev;
        Node<T> next = x.next;

        // if delete node is head
        if (index == 0) {
            head = next;
        }

        // if delete node is tail
        if (index == size - 1) {
            tail = prev;
        }

        prev.next = next;
        next.prev = prev;

        size--;

        if (size == 0) {
            head = tail = null;
        }

        return x.element;
    }

    private void checkPositionIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * set element by index
     *
     * @param index
     * @param element
     * @return old element
     */
    @Override
    public T set(int index, T element) {
        Node<T> oldNode = node(index);
        T oldElement = oldNode.element;
        oldNode.element = element;
        return oldElement;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        return node(index).element;
    }

    /**
     * get element by index
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        checkPositionIndex(index);
        if (index < (size >> 1)) {
            Node<T> x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = tail;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    /**
     * clear list
     */
    @Override
    public void clear() {
        for (Node<T> x = head; x != null; ) {
            Node<T> next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     * contain certain element
     *
     * @param element
     * @return
     */
    @Override
    public boolean contains(T element) {
        if (head == null) {
            return false;
        }
        Node<T> x = head;
        for (int i = 0; i < size; i++) {
            if (element == null && x.element == null) {
                return true;
            }
            if (element != null && element.equals(x.element)) {
                return true;
            }
            x = x.next;
        }
        return false;
    }

    /**
     * get list size
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param <T>
     */
    private class Node<T> {
        private T element;
        private Node<T> prev;
        private Node<T> next;

        public Node(T element, Node<T> prev, Node<T> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }

}

源代码

总结

写链表代码特别需要注意边界条件的处理：

  • 如果链表为空，代码能否正常工作？
  • 如果链表只有一个节点时，代码能否正常工作？
  • 如果链表只有两个节点时，代码能否正常工作？
  • 代码在删除或插入 Head 和 Tail 节点时，这四种的链表结构是否

ArrayList vs LinkedList

ArrayList LinkedList
插入 &
删除		 O(n) O(1)
随机访问 O(1) O(n)
优点 连续的内存空间，可以借助 CPU 的预取机制 内存不连续，天然支持动态扩容
缺点 无法存储大数据，数组扩容耗性能 频繁地插入删除操作，会导致内存碎片的增加，导致频繁的 GC

相关练习

参考资料