引言：数据结构——链表队列
LinkedListQueue
如果我们直接使用之前我们编写的LinkedList的话，为了实现队列的FIFO的特性，我们必须选一端入，一端出，但是这就有了一个问题
我们的LinkedList有头结点，向头添加或者删除都是O(1)，很方便，但是如果是对尾部的操作的话，就都是O(n)了
这其实和使用Array来实现的一样，在数组中，操作尾部是简单的，但是操作头是困难的
所以为了提高链表队列的性能，我们需要改进一下现有的LinkedList，即再增添一个尾节点
又因为实现队列，只需要FIFO，即只需要对头和尾来进行操作，所以我们不需要设置一个虚拟头结点
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
|
public class LinkedListQueue<E> implements Queue{
private class Node{
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e,null);
}
public Node() {
this(null,null);
}
@Override
public String toString() {
return "Node{" +
"e=" + e +
", next=" + next +
'}';
}
}
private Node head;
private Node tail;
private int size;
public LinkedListQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public void enqueue(Object o) {
if(tail == null){
tail = new Node((E)o);
head = tail;
}else {
tail.next = new Node((E)o);
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空，出队错误");
}
Node delNode = head;
head = head.next;
delNode.next = null;
if(head == null){
tail = null;
}
size--;
return delNode.e;
}
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空，出队错误");
}
return head.e;
}
@Override
public String toString() {
StringJoiner sj = new StringJoiner("->","Queue: Head [","] tail");
Node cur = head;
while (cur!=null){
sj.add(cur.e+"");
cur = cur.next;
}
return sj.toString();
}
}
|
复杂度分析
1
2
3
4
5
6
7
| 方法名 | 时间复杂度 |
-------------------------------------------------
enqueue() | O(1) |
dequeue() | O(1) |
front() | O(1) |
getSize() | O(1) |
isEmpty() | O(1) |
|
LinkedListQueue 对比 LoopQueue
Queue现在我们有三种
- ArrayQueue
- LoopQueue
- LinkedListQueue
ArrayQueue速度慢于LoopQueue很多，那么LinkedListQueue和LoopQueue相比会怎么样呢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class SpeedTest {
public static void main(String[] args) {
int loopTurn = 10_000_000;
Queue<Integer> loopQueue = new LoopQueue<>();
Queue<Integer> linkedListQueue = new LinkedListQueue<>();
System.out.println("loopQueue运行时间："+testSpeed(loopTurn,loopQueue)+"s");
System.out.println("linkedListQueue运行时间："+testSpeed(loopTurn,linkedListQueue)+"s");
}
private static double testSpeed(int loopTurn, Queue<Integer> q) {
long startTime = System.nanoTime();
for(int i=0;i<loopTurn;i++) {
Random r = new Random();
q.enqueue(r.nextInt(Integer.MAX_VALUE));
}
for(int i=0;i<loopTurn;i++) {
q.dequeue();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
}
|
执行一百万次代码
1
2
| loopQueue运行时间：2.8736317s
linkedListQueue运行时间：4.035901s
|
对比结果，LinkedListQueue慢了几秒，这是由于不断的new结点造成的速度下降