LinkedList简介
LinkedList
是一个继承于AbstractSequentialList
的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList
实现List
接口,能进行队列操作。LinkedList
实现Deque
接口,即能将LinkedList
当作双端队列使用。ArrayList
底层是由数组支持,而LinkedList
是由双向链表实现的,其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。
LinkedList遍历方式
LinkedList
有以下几种遍历方式:
迭代器遍历
1 | Iterator<Integer> iterator = linkedList.iterator(); |
for循环get()遍历
1 | for(int i = 0; i < linkedList.size(); i++){ |
Foreach循环遍历
1 | for(Integer i : linkedList); |
通过pollFirst()或pollLast()遍历
1 | while(linkedList.size() != 0){ |
通过removeFirst()或removeLast()遍历
1 | while(linkedList.size() != 0){ |
效率测试
测试以上几种遍历方式的效率,部分代码如下: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 | /** |
LinkedList和ArrayList比较
LinkedList
中插入元素很快,而ArrayList
中插入元素很慢LinkedList
中随机访问很慢,而ArrayList
中随机访问很快
LinkedList源码解析
1 | package java.util; |