Project 1 Data Structures§

private class Node {  
    T data; // 此项目中 T 都表示泛型类型参数(type parameter)的占位符
    Node next;  
    Node prev;  

    public Node(T data) {  
        this.data = data;  
        next = null;  
        prev = null;  
    }  
}

private Node sentinel; // 哨兵节点  
private int size;

public LinkedListDeque() {  
    sentinel = new Node(null);
    sentinel.next = sentinel;  // 循环链表, 初始时刻前一个与后一个都指向自己
    sentinel.prev = sentinel;

    size = 0;  
}

/**  
 * * @return Returns `true` if deque is empty, `false` otherwise.  
 */
public boolean isEmpty() {  
    return size == 0;  
}  

/**  
 * * @return Returns the number of items in the deque.  
 */
public int size() {  
    return size;  
}

/**  
 * Prints the items in the deque from first to last, separated by a space. 
 * Once all the items have been printed, print out a new line. 
 */
public void printDeque() {  
    Node current = sentinel.next;  
    while (current.data != null) {  
        System.out.print(current.data + " ");  
        current = current.next;  
    }  
    System.out.println();  
}

/**  
 * * @param index  
 * @return Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth.  
 * If no such item exists, returns `null`. Must not alter the deque! 
 */
public T get(int index) {  
    if (index < 0 || index >= size) {  
        return null;  
    }  

    Node current = sentinel;  
    for (int i = 0; i <= index; ++i) {  
        current = current.next;  
    }  
    return current.data;  
}

/**  
 * * @param current  
 * @param restOffset  
 * @return 在不考虑边界条件的情况下的对值的递归式读取  
 */  
private T getRecursiveWithoutNull(Node current, int restOffset) {  
    if (restOffset == 0) {  
        return current.data;  
    }  
    return getRecursiveWithoutNull(current.next, restOffset - 1);  
}

/**  
 * * @param index  
 * @return Same as get, but uses recursion.  
 */
public T getRecursive(int index) {  
    if (index < 0 || index >= size) {  
        return null;  
    }  

    return getRecursiveWithoutNull(sentinel, index + 1);  
}

/**  
 * Adds an item of type `T` to the front of the deque. 
 * You can assume that `item` is never `null`. 
 * @param data  
 */  
public void addFirst(T data) {  
    Node newNode = new Node(data);  
    newNode.prev = sentinel;  
    newNode.next = sentinel.next;  
    sentinel.next.prev = newNode;  
    sentinel.next = newNode;  

    size++;  
}  

/**  
 * Adds an item of type `T` to the back of the deque. 
 * You can assume that `item` is never `null`. 
 * @param data  
 */  
public void addLast(T data) {  
    Node newNode = new Node(data);  
    newNode.next = sentinel;  
    newNode.prev = sentinel.prev;  
    sentinel.prev.next = newNode;  
    sentinel.prev = newNode;  

    size++;  
}  

/**  
 * * @return Removes and returns the item at the front of the deque.  
 * If no such item exists, returns `null`. 
 */
public T removeFirst() {  
    if (size == 0) {  
        return null;  
    }  
    Node toBeRemoved = sentinel.next;  
    T data = toBeRemoved.data;  
    toBeRemoved.next.prev = sentinel;  
    sentinel.next = toBeRemoved.next;  

    toBeRemoved.data = null;  
    toBeRemoved.prev = null;  
    toBeRemoved.next = null;  

    size--;  
    return data;  
}  

/**  
 * * @return Removes and returns the item at the back of the deque.  
 * If no such item exists, returns `null`. 
 */
public T removeLast() {  
    if (size == 0) {  
        return null;  
    }  
    Node toBeRemoved = sentinel.prev;  
    T data = toBeRemoved.data;  
    toBeRemoved.prev.next = sentinel;  
    sentinel.prev = toBeRemoved.prev;  

    toBeRemoved.data = null;  
    toBeRemoved.next = null;  
    toBeRemoved.prev = null;  

    size--;  
    return data;  
}