Java学习笔记之LinkedList基本用法

发表于   |   分类于   |     |   阅读次数

LinkedList简介

  • LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList 实现 List 接口，能进行队列操作。
  • LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
  • ArrayList底层是由数组支持，而LinkedList 是由双向链表实现的，其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。

LinkedList遍历方式

LinkedList有以下几种遍历方式：

迭代器遍历

1
2
3
4
Iterator<Integer> iterator = linkedList.iterator();
while(iterator.hasNext()){
	iterator.next();
}

for循环get()遍历

1
2
3
for(int i = 0; i < linkedList.size(); i++){
	linkedList.get(i);
}

Foreach循环遍历

1
for(Integer i : linkedList);

通过pollFirst()或pollLast()遍历

1
2
3
while(linkedList.size() != 0){
	linkedList.pollFirst();
}

通过removeFirst()或removeLast()遍历

1
2
3
while(linkedList.size() != 0){
	linkedList.removeFirst();
}

效率测试

测试以上几种遍历方式的效率，部分代码如下：

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
/************************** 遍历操作   ************************/
System.out.println("-----------------------------------------");
linkedList.clear();
for(int i = 0; i < 100000; i++){
	linkedList.add(i);
}
// 迭代器遍历
long start = System.currentTimeMillis();
Iterator<Integer> iterator = linkedList.iterator();
while(iterator.hasNext()){
	iterator.next();
}
long end = System.currentTimeMillis();
System.out.println("Iterator：" + (end - start) +" ms");

// 顺序遍历(随机遍历)
start = System.currentTimeMillis();
for(int i = 0; i < linkedList.size(); i++){
	linkedList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for：" + (end - start) +" ms");

// 另一种for循环遍历
start = System.currentTimeMillis();
for(Integer i : linkedList);
end = System.currentTimeMillis();
System.out.println("for2：" + (end - start) +" ms");

//  通过pollFirst()或pollLast()来遍历LinkedList
LinkedList<Integer> temp1 = new LinkedList<>();
temp1.addAll(linkedList);
start = System.currentTimeMillis();
while(temp1.size() != 0){
	temp1.pollFirst();
}
end = System.currentTimeMillis();
System.out.println("pollFirst()或pollLast()：" + (end - start) +" ms");

// 通过removeFirst()或removeLast()来遍历LinkedList
LinkedList<Integer> temp2 = new LinkedList<>();
temp2.addAll(linkedList);
start = System.currentTimeMillis();
while(temp2.size() != 0){
	temp2.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("removeFirst()或removeLast()：" + (end - start) +" ms");

输出：

1
2
3
4
5
6
-----------------------------------------
Iterator：17 ms
for：8419 ms
for2：12 ms
pollFirst()或pollLast()：12 ms
removeFirst()或removeLast()：10 ms

由测试结果可以看出，遍历LinkedList时，使用removeFirst()或removeLast()效率最高，而for循环get()效率最低，应避免使用这种方式进行。应当注意的是，使用pollFirst()或pollLast()或removeFirst()或removeLast()遍历时，会删除原始数据，若只单纯的读取，应当选用第一种或第三种方式。

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
/**
 * @author GongchuangSu
 * @since 2016.05.11
 */
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
	public static void main(String[] srgs){
		LinkedList<Integer> linkedList = new LinkedList<>();
		
		/************************** 基本操作 ************************/
		linkedList.addFirst(0);    // 添加元素到列表开头
		linkedList.add(1);         // 在列表结尾添加元素
		linkedList.add(2,2);       // 在指定位置添加元素
		linkedList.addLast(3);     // 添加元素到列表结尾
		
		System.out.println("LinkedList: " + linkedList);
				
		System.out.println("getFirst(): " + linkedList.getFirst());       // 返回此列表的第一个元素
		System.out.println("getLast(): " + linkedList.getLast());		  // 返回此列表的最后一个元素		
		System.out.println("removeFirst(): " + linkedList.removeFirst()); // 移除并返回此列表的第一个元素		
		System.out.println("removeLast(): " + linkedList.removeLast());   // 移除并返回此列表的最后一个元素
		System.out.println("After remove:" + linkedList);                	
		System.out.println("contains(1) is :" + linkedList.contains(1));  // 判断此列表包含指定元素，如果是，则返回true	
		System.out.println("size is : " + linkedList.size());             // 返回此列表的元素个数
		
		/************************** 位置访问操作 ************************/
		System.out.println("-----------------------------------------");
		linkedList.set(1, 3);                                             // 将此列表中指定位置的元素替换为指定的元素
		System.out.println("After set(1, 3):" + linkedList);  
		System.out.println("get(1): " + linkedList.get(1));               // 返回此列表中指定位置处的元素
		
		/************************** Search操作  ************************/
		System.out.println("-----------------------------------------");
		linkedList.add(3);
		System.out.println("indexOf(3): " + linkedList.indexOf(3));        // 返回此列表中首次出现的指定元素的索引
		System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));// 返回此列表中最后出现的指定元素的索引
		
		/************************** Queue操作   ************************/
		System.out.println("-----------------------------------------");
		System.out.println("peek(): " + linkedList.peek());                // 获取但不移除此列表的头
		System.out.println("element(): " + linkedList.element());          // 获取但不移除此列表的头
		linkedList.poll();                                                 // 获取并移除此列表的头
		System.out.println("After poll():" + linkedList);
		linkedList.remove();
		System.out.println("After remove():" + linkedList);                // 获取并移除此列表的头
		linkedList.offer(4);
		System.out.println("After offer(4):" + linkedList);                // 将指定元素添加到此列表的末尾  
		
		/************************** Deque操作   ************************/
		System.out.println("-----------------------------------------");
		linkedList.offerFirst(2);                                          // 在此列表的开头插入指定的元素
		System.out.println("After offerFirst(2):" + linkedList);
		linkedList.offerLast(5);                                           // 在此列表末尾插入指定的元素
		System.out.println("After offerLast(5):" + linkedList);
		System.out.println("peekFirst(): " + linkedList.peekFirst());      // 获取但不移除此列表的第一个元素
		System.out.println("peekLast(): " + linkedList.peekLast());        // 获取但不移除此列表的第一个元素
		linkedList.pollFirst();                                            // 获取并移除此列表的第一个元素
		System.out.println("After pollFirst():" + linkedList);
		linkedList.pollLast();                                             // 获取并移除此列表的最后一个元素
		System.out.println("After pollLast():" + linkedList);
		linkedList.push(2);                                                // 将元素推入此列表所表示的堆栈（插入到列表的头）
		System.out.println("After push(2):" + linkedList);
		linkedList.pop();                                                  // 从此列表所表示的堆栈处弹出一个元素（获取并移除列表第一个元素）
		System.out.println("After pop():" + linkedList);
		linkedList.add(3);
		linkedList.removeFirstOccurrence(3);                               // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）
		System.out.println("After removeFirstOccurrence(3):" + linkedList);
		linkedList.removeLastOccurrence(3);                                // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）
		System.out.println("After removeFirstOccurrence(3):" + linkedList);
		
		/************************** 遍历操作   ************************/
		System.out.println("-----------------------------------------");
		linkedList.clear();
		for(int i = 0; i < 100000; i++){
			linkedList.add(i);
		}
		// 迭代器遍历
		long start = System.currentTimeMillis();
		Iterator<Integer> iterator = linkedList.iterator();
		while(iterator.hasNext()){
			iterator.next();
		}
		long end = System.currentTimeMillis();
		System.out.println("Iterator：" + (end - start) +" ms");
		
		// 顺序遍历(随机遍历)
		start = System.currentTimeMillis();
		for(int i = 0; i < linkedList.size(); i++){
			linkedList.get(i);
		}
		end = System.currentTimeMillis();
		System.out.println("for：" + (end - start) +" ms");
		
		// 另一种for循环遍历
		start = System.currentTimeMillis();
		for(Integer i : linkedList);
		end = System.currentTimeMillis();
		System.out.println("for2：" + (end - start) +" ms");
		
		//  通过pollFirst()或pollLast()来遍历LinkedList
		LinkedList<Integer> temp1 = new LinkedList<>();
		temp1.addAll(linkedList);
		start = System.currentTimeMillis();
		while(temp1.size() != 0){
			temp1.pollFirst();
		}
		end = System.currentTimeMillis();
		System.out.println("pollFirst()或pollLast()：" + (end - start) +" ms");
		
		// 通过removeFirst()或removeLast()来遍历LinkedList
		LinkedList<Integer> temp2 = new LinkedList<>();
		temp2.addAll(linkedList);
		start = System.currentTimeMillis();
		while(temp2.size() != 0){
			temp2.removeFirst();
		}
		end = System.currentTimeMillis();
		System.out.println("removeFirst()或removeLast()：" + (end - start) +" ms");
	}
}
/**Output
LinkedList: [0, 1, 2, 3]
getFirst(): 0
getLast(): 3
removeFirst(): 0
removeLast(): 3
After remove:[1, 2]
contains(1) is :true
size is : 2
-----------------------------------------
After set(1, 3):[1, 3]
get(1): 3
-----------------------------------------
indexOf(3): 1
lastIndexOf(3): 2
-----------------------------------------
peek(): 1
element(): 1
After poll():[3, 3]
After remove():[3]
After offer(4):[3, 4]
-----------------------------------------
After offerFirst(2):[2, 3, 4]
After offerLast(5):[2, 3, 4, 5]
peekFirst(): 2
peekLast(): 5
After pollFirst():[3, 4, 5]
After pollLast():[3, 4]
After push(2):[2, 3, 4]
After pop():[3, 4]
After removeFirstOccurrence(3):[4, 3]
After removeFirstOccurrence(3):[4]
-----------------------------------------
Iterator：17 ms
for：8419 ms
for2：12 ms
pollFirst()或pollLast()：12 ms
removeFirst()或removeLast()：10 ms
*/

LinkedList和ArrayList比较

  • LinkedList中插入元素很快，而ArrayList中插入元素很慢
  • LinkedList中随机访问很慢，而ArrayList中随机访问很快

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
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
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
package java.util;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    // 第一个结点
    transient Node<E> first;

    // 最后一个结点
    transient Node<E> last;

    // 构造一个空列表
    public LinkedList() {
    }

    // 构造一个包含指定 Collection 中的元素的列表，
	// 这些元素按其 Collection 的迭代器返回的顺序排列
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    // 返回此列表的第一个元素
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    // 返回此列表的最后一个元素
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    // 移除并返回此列表的第一个元素
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    // 移除并返回此列表的最后一个元素
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    // 将指定元素插入此列表的开头
    public void addFirst(E e) {
        linkFirst(e);
    }

    // 将指定元素添加到此列表的结尾
    public void addLast(E e) {
        linkLast(e);
    }

    // 判断此列表包含指定元素，如果是，则返回true
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    // 返回此列表的元素个数
    public int size() {
        return size;
    }

    // 将指定元素添加到此列表的结尾
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    // 从此列表中移除首次出现的指定元素(如果存在返回true，否则返回false)
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    // 添加指定 collection 中的所有元素到此列表的结尾，
	// 顺序是指定 collection 的迭代器返回这些元素的顺序
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    // 将指定 collection 中的所有元素从指定位置开始插入此列表
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);// 检查index的范围
		
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)          // 如果c为空，则返回false
            return false;

        Node<E> pred, succ;
        if (index == size) {      // 插入位置为列表末尾
            succ = null;
            pred = last;
        } else {
            succ = node(index);   // 插入位置不是列表末尾
            pred = succ.prev;
        }
		// 将元素添加到pred末尾
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
		// 将剩余元素整合一起
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

    // 从此列表中移除所有元素
    public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }
	
	/********************** 位置访问操作 **************************/

    // 返回此列表中指定位置处的元素
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    // 将此列表中指定位置的元素替换为指定的元素
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    // 在此列表中指定的位置插入指定的元素
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)     // 插入到末尾
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    // 移除此列表中指定位置处的元素
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    // （包访问权限）返回指定位置上的结点（非空）
    Node<E> node(int index) {
        // assert isElementIndex(index);
        // 根据指定位置是在左半边还是在右半边，
		// 来决定是用正向寻找还是反向寻找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
	
	/********************** Search操作 **************************/

    // 返回此列表中首次出现的指定元素的索引，
	// 如果此列表中不包含该元素，则返回 -1
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    // 返回此列表中最后出现的指定元素的索引，
	// 如果此列表中不包含该元素，则返回 -1
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

	/********************** Queue操作 **************************/

    // 获取但不移除此列表的头（第一个元素）
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    // 获取但不移除此列表的头（第一个元素）
    public E element() {
        return getFirst();
    }

    // 获取并移除此列表的头（第一个元素）
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    // 获取并移除此列表的头（第一个元素）
    public E remove() {
        return removeFirst();
    }

    // 将指定元素添加到此列表的末尾（最后一个元素）
    public boolean offer(E e) {
        return add(e);
    }

	/********************** Deque操作 **************************/
	
    // 在此列表的开头插入指定的元素
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    // 在此列表末尾插入指定的元素
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    // 获取但不移除此列表的第一个元素
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

    // 获取但不移除此列表的最后一个元素
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

    // 获取并移除此列表的第一个元素
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    // 获取并移除此列表的最后一个元素
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    // 将元素推入此列表所表示的堆栈（插入到列表的头）
    public void push(E e) {
        addFirst(e);
    }

    // 从此列表所表示的堆栈处弹出一个元素（获取并移除列表第一个元素）
    public E pop() {
        return removeFirst();
    }

    // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）
    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    // 返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

	// （私有类）结点结构
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

    /**
     * @since 1.6
     */
    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

    /**
     * Adapter to provide descending iterators via ListItr.previous
     */
    private class DescendingIterator implements Iterator<E> {
        private final ListItr itr = new ListItr(size());
        public boolean hasNext() {
            return itr.hasPrevious();
        }
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }

    @SuppressWarnings("unchecked")
    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    // 返回此 LinkedList 的浅表副本
    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

    // 返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    // 返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组；
	// 返回数组的运行时类型为指定数组的类型。
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

	// 版本序列号
    private static final long serialVersionUID = 876323262645176354L;

    // java.io.Serializable的写入函数
    // 将LinkedList的“容量，所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

    // java.io.Serializable的读取函数：根据写入方式反向读出
    // 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }
}