【CS61B】Project1A-Linked List Deque 61B

Project1A-Linked List Deque 61B

这个项目要求我们用链表实现双端队列(Deque)

Javadoc comment

1
2
3
4
5

/** ...
 * @param index index to get
 * @return element at {@code index} in the deque
 */
T get(int index);

如以上注释，该形式的注释为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

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)  // `expected` is a List
    .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;
}