简介
LinkedList 是一个实现了List和Deque接口的双向链表， List接口都是一个常规的增删改查操作， 而Deque是的LinkedList具有队列的特性， LinkList不是线程安全的，如果先是的LinkedList变成线程安全的，可以使用1
List list=Collections.synchronizedList(new LinkedList(...));
源码分析
1 | public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable { |
JavaGuide的demo1
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
121package list;
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] srgs) {
//创建存放int类型的linkedList
LinkedList<Integer> linkedList = new LinkedList<>();
/************************** 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这个元素:" + linkedList.contains(1)); // 判断此列表包含指定元素，如果是，则返回true
System.out.println("该linkedList的大小 : " + linkedList.size()); // 返回此列表的元素个数
/************************** 位置访问操作 ************************/
System.out.println("-----------------------------------------");
linkedList.set(1, 3); // 将此列表中指定位置的元素替换为指定的元素
System.out.println("After set(1, 3):" + linkedList);
System.out.println("get(1)获得指定位置（这里为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");
}
}