Project1A-Linked List Deque
61B
这个项目要求我们用链表实现双端队列(Deque)
如以上注释，该形式的注释为java文档注释
- @param表示方法的变量
- @return表示方法的返回值类型
- @code
用于格式化文本为代码风格
步骤
创建文件
我们希望创建的类可以接受多种数据类型，故需要实现泛型，在声明类时：
public class LinkedListDeque61B<T>
另外需要指定LinkedListDeque61B是Deque61B的子类，并且实现所有接口中的方法：
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
| import java.util.List;
public class LinkedListDeque61B<T> implements Deque61B<T>{
@Override
public void addFirst(T x) {
}
@Override
public void addLast(T x) {
}
@Override
public List<T> toList() {
return List.of();
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public T removeFirst() {
return null;
}
@Override
public T removeLast() {
return null;
}
@Override
public T get(int index) {
return null;
}
@Override
public T getRecursive(int index) {
return null;
}
}
|
最后加入构造函数：
1
2
3
| public LinkedListDeque61B(){
}
|
JUnit Tests
打开LinkedListDeque61BTest文件，去除除最后一行的注释，就可以对编写代码进行本地测试
Writing and Verifying the
Constructor
实现构造函数，更具体的，构造函数应传入0个参数，并在LinkedListDeque61B类中实现嵌套类Node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| private class Node{
public T item;
public Node next;
public Node previous;
public Node(T i, Node p, Node n){
item = i;
next = n;
previous = p;
}
}
private Node sentinelFront;
private Node sentinelLast;
private int size;
public LinkedListDeque61B(){
sentinelFront = new Node(null, null, null);
sentinelLast = new Node(null, null, null);
size = 0;
}
|
这里我们在类中嵌套实现了Node类用于定义每个节点，并且对双端队列设置了两个sentinel节点，方便双端操作，同时引入size记录大小
其中，Node类包括两个指针，同时指向前一个节点与后一个节点
构造函数中，对两个sentinel节点进行初始化，并设置size为0
Writing and
Verifying addFirst and addLast
addFirst与addLast需要以常数时间实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| @Override
public void addFirst(T x) {
Node newNode = new Node(x, sentinelFront, sentinelFront.next);
sentinelFront.next.previous = newNode;
sentinelFront.next = newNode;
size++;
}
@Override
public void addLast(T x) {
Node newNode = new Node(x, sentinelLast.previous, sentinelLast);
sentinelLast.previous.next = newNode;
sentinelLast.previous = newNode;
size++;
}
|
我们直接操作sentinel节点的next与previous来添加节点
Writing and Verifying
toList
实现toList，当调用时会自动返回以列表形式表示的Deque61B
例如，如果Deque61B已经调用了addLast(5)、addLast(9)、addLast(10)，然后对其调用addFirst(3)，那么toList()的结果应该是一个以3开头，然后是5、9、10的列表。如果在Java中打印，它将显示为[3,
5, 9, 10]。
toList方法的第一行应该类似于List<T> returnList = new ArrayList<>()，标志着可以使用该结构的位置
1
2
3
4
5
6
7
8
| @Override
public List<T> toList() {
List<T> returnList = new ArrayList<>();
for (Node p = sentinelFront.next; p!=sentinelLast; p = p.next){
returnList.add(p.item);
}
return returnList;
}
|
Writing Tests
写测试例的模板：Arrange-Act-Assert
- Arrange：组织测试样例，如初始化数据结构或往里面填充元素
- Act：执行想要执行的操作
- Assert：评估Act中的结果
在单个测试方法中通常有多个act与assert步骤
真值评估的模板：
格式：assertThat(actual).isEqualTo(expected);
添加信息：
1
2
3
| assertWithMessage("actual is not expected")
.that(actual)
.isEqualTo(expected);
|
判断列表包含内容：
1
2
3
| assertThat(actualList)
.containsExactly(0, 1, 2, 3)
.inOrder();
|
对于引用类型：
1
2
3
| assertThat(actualList)
.containsExactlyElementsIn(expected)
.inOrder();
|
注意：assert一个布尔值时，记得在后面使用.isTrue() 或者
.isFalse()判断正误
其余方法
isEmpty()与size()
要求常数时间实现
1
2
3
4
5
6
7
8
9
| @Override
public boolean isEmpty() {
return size==0;
}
@Override
public int size() {
return size;
}
|
get()与getRecursive()
给予下标寻找下标对应元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| @Override
public T get(int index) {
if (index<0||index>=size){
return null;
}
Node p = sentinelFront.next;
for (int i = 0; i<index; i++){
p = p.next;
}
return p.item;
}
private T getRecursiveHelper(Node p, int index){
if (index == 0) return p.item;
return getRecursiveHelper(p.next, index-1);
}
@Override
public T getRecursive(int index) {
if (index<0||index>=size){
return null;
}
return getRecursiveHelper(sentinelFront.next, index);
}
|
写了一个辅助递归函数，可以接受当前节点与下标，进行节点的推进
removeFirst()与removeLast()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| @Override
public T removeFirst() {
if (isEmpty()){
return null;
}
Node temp = sentinelFront.next;
sentinelFront.next = temp.next;
temp.next.previous = sentinelFront;
size--;
return temp.item;
}
@Override
public T removeLast() {
if (isEmpty()){
return null;
}
Node temp = sentinelLast.previous;
sentinelLast.previous = temp.previous;
temp.previous.next = sentinelLast;
size--;
return temp.item;
}
|
