Question

When I run the main method with the test case, it returns the list backwards. How can I fix it so that it gives me all 6 correct actions? My guess is that the problem is in the getAction() function.



public class StringDoublyLinkedList {

    /**
     * A private class to represent a link in the linked list.
     */
    private class Node {
        String value;
        Node next;
        Node prev;

        Node(String value) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }

    private int size = 0;
    private Node head = null;
    private Node tail = null;
    private Node head_2 = null;

    /**
     * Add a String to the end of the list.
     *
     * @param value The String to add.
     */
    public void add(String value) {
        Node newNode = new Node(value);
        if (this.size == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.size += 1;
    }

    /**
     * Get the number of elements in the list.
     *
     * @return The number of elements in the list.
     */
    public int size() {
        return this.size;
    }

    public String get(int index) {
        return this.getNode(index).value;
    }

    public void remove(int index) {
        Node curr = this.head;
        if (index == 0) {
            this.head = curr.next;
        } else {
            Node node = this.getNode(index - 1);
            node.next = node.next.next;
            if (node.next == tail) {
                this.tail = node;
            }
        }
        this.size -= 1;
    }

    private Node getNode(int index) {
        Node curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    }

    public boolean undo() {
        Node curr = this.head;
        if (this.size > 0) {
            curr.next.prev = null;
            this.head = curr.next;
            this.head_2 = curr;
        } else if (this.size == 0) {
            return false;
        }
        this.size -= 1;
        return true;
    }

    public boolean redo() {
        Node curr = this.head;
        Node curr_2 = this.head_2;
        if (this.size > 0) {
            curr_2.next.prev = null;
            this.head_2 = curr_2.next;
            curr.next = this.head;
            this.head.prev = curr;
            this.head = curr;
            } if (this.size == 0) {
            return false;
        }
        this.size += 1;
        return false;
    }

    /**
     * Record an action.
     *
     * @param action The action to record.
     */
    public void doAction(String action) {
        Node newNode = new Node(action);
        if (this.size == 0) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.head.prev = newNode;
            newNode.next = this.head;
            this.head = newNode;
        }
        this.size += 1;
    }

    /**
     * Get the number of actions recorded. Does *not* include actions that were undone.
     *
     * @return The number of actions recorded.
     */
    public int getNumActions() {
        int count = 1;
        int i;
        for (i = this.size() - 1; i > 0; i--) {
            count++;
        }
        return count;
    }

    /**
     * Get the action at the specified index.
     *
     * Assumes the index < this.getNumActions().
     *
     * @param index The index of the desired action.
     * @return The action (String).
     */

    public String getAction(int index) {
        int i;
        for (i = 0; i < this.size(); i++) {
            index = this.size() - index - 1;
        }
        String Actions = this.get(index);
        return Actions;
    }

    public void print() {
        Node curr = this.head;
        while (curr != null) {
            System.out.print(curr.value);
            System.out.print(", ");
            curr = curr.next;
        }
        System.out.println();
    }

public static void main(String[] args) {
    StringDoublyLinkedList actions = new StringDoublyLinkedList();

    actions.doAction("create outline");
    actions.doAction("write introduction paragraph");
    actions.doAction("write paragraph 1a");
    actions.undo();
    actions.doAction("write paragraph 1b");
    actions.doAction("write paragraph 2a");
    actions.undo();
    actions.undo();
    actions.redo();
    actions.doAction("write paragraph 2b");
    actions.doAction("write paragraph 3");
    actions.doAction("write paragraph 4");
    actions.undo();
    actions.doAction("write conclusion paragraph");
    actions.doAction("add expletive about how long this assignment took");
    actions.undo();


    String[] correctActions = {
            "create outline",
            "write introduction paragraph",
            "write paragraph 1b",
            "write paragraph 2b",
            "write paragraph 3",
            "write conclusion paragraph"
    };

    // create a variable for overall correctness
    boolean allCorrect;
    // check the number of actions
    System.out.println(
            "Expected " + Integer.toString(correctActions.length) + " actions " +
                    "and found " + Integer.toString(actions.getNumActions())
    );
    allCorrect = (actions.getNumActions() == correctActions.length);
    // if the number of actions is correct, check each action
    if (allCorrect) {
        for (int i = 0; i < correctActions.length; i++) {
            // get the expected and action actions
            String expectedAction = correctActions[i];
            String actualAction = actions.getAction(i);
            // compare them
            boolean correct = (expectedAction == actualAction);
            // print them out
            System.out.println(
                    "(" + (correct ? "correct" : "incorrect") + ") " +
                            "Action " + Integer.toString(i) + " should be \"" + correctActions[i] + "\" " +
                            "and got \"" + actions.getAction(i) + "\"."
            );
            // update the overall correctness
            allCorrect = (allCorrect && correct);
        }
    }
    // give a summary correct/incorrect judgment
    if (allCorrect) {
        System.out.println("CORRECT!");
    } else {
        System.out.println("INCORRECT!");
    }
}

}

Answer 1

The problem is not with getAction().

The problems are with the following methods:

• doAction() -> in this method, you are adding a new element to the start of the list, but the expectation is to append the new action at the end of the list
• undo() -> in this method, you are removing the element from the head of the list, but the expectation is to remove from the end of the list
• redo() -> again you are operating at the beginning of the list, rather you should redo at the end of the list.

Once you do the above changes, you should get all correct.