<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/* NetId(s): nnnn, nnnn. Time spent: hh hours, mm minutes.
 * 
 * Name(s):
 * What I thought about this assignment:
 *
 *
 */

/** An instance is a doubly linked list. It provides much of the functionality of
 * Java class java.util.LinkedList.
 * It extends class java.util.AbstractList, which just means that it must override
 * certain methods. */
public class DLinkedList&lt;E&gt; extends java.util.AbstractList&lt;E&gt; {
    private int size;  // Number of nodes in the linked list.
    private Node head; // first node of the linked list (null if none)
    private Node tail; // last node of the linked list (null if none)

    /** Constructor: an empty linked list. */
    public DLinkedList() {
        // TODO item #1
        // Look at the class invariant to determine how to implement this.
    }

    /** Return the head Node of this linked list */
    Node getHead() {// no access modifier. Accessible (only) in package
        return head;
    }

    /** Return the tail Node of this linked list */
    Node getTail() {// no access modifier. Accessible (only) in package
        return tail;
    }

    /** Return the number of elements in this list.
     * This operation must take constant time. */
    public @Override int size() {
        // TODO item #2
        // This is an extremely small method
        return 0;
    }

    /** Return the elements of this list, in order, separated by ", " (comma blank),
     * and delimited by [ and ]. Elements e are turned into Strings using String
     * catenation. Thus, if e is null, the String "null" is automatically used. */
    public @Override String toString() {
        String res= "[";
        Node n= head;
        // invariant: all elements before n (or all if n is null) have been
        //      added to res, with ", " between them and with "[" in the beginning
        while (n != null) {
            if (res.length() &gt; 1) res= res + ", ";
            res= res + n.data;
            n= n.succ;
        }
        return res + "]";
    }

    /** Return a representation of this list: its values in reverse order, with
     * adjacent ones separated by ", " (comma blank), with "[" at the beginning,
     * and with "]" at the end. &lt;br/&gt;
     *
     * E.g. for the list containing 6 3 8 in that order, the result is "[8, 3, 6]".
     *
     * To add values to a list, use String catenation as in toString above. */
    public String toStringRev() {
        // TODO item #3
        // This should use field tail and the pred fields in nodes.
        // Do NOT use field size.
        return null;
    }

    /** Place element in a new node at the end of the list and return the new node.
     * This operation must take constant time. */
    Node append(E element) {// no access modifier. Accessible (only) in package
        // TODO item #4
        // This mid-size helper function will be used by other methods
        return null;
    }

    /** Append element to the end of this list and return true. */
    public @Override boolean add(E element) {
        // TODO item #5
        // Rely on helper methods to keep this method small
        // This is THE MOST IMPORTANT method to get right because it will be used
        // in nearly every test
        return false;
    }

    /** Return Node number h of this list
     * (the first node is number 0, the second is number 1, etc.)
     * Throw an IndexOutOfBoundsException if h &lt; 0 or h &gt;= size of the list.
     * This method should take time proportional to min(h, size - h). */
    Node getNode(int h) {// no access modifier. Accessible (only) in package
        // TODO item #6
        // This large helper method is used more than any other helper method
        // It is used by other public methods or for testing.
        // Note that there are two ways to get to a node: from the head or from the tail.
        // This MUST use the fastest way for index.
        // (If h is exactly the middle, then either way is ok.)
        return null;
    }

    /** Return element number h of this list.
     * (The first element is number 0, the second is number 1, etc.)
     * Throw an IndexOutOfBoundsException if h &lt; 0 or h &gt;= size of the list.
     * The time taken should be proportional to min(h, size - h).*/
    public @Override E get(int h) {
        // TODO item #7
        // Rely on helper methods to keep this method small.
        // Note that the helper method could throw the exception; doesn't
        // have to be done here.
        return null;
    }

    /** Replace element number h of this list by e.
     * (The first element is number 0, the second is number 1, etc.)
     * Return the value that was previously element number h.
     * Throw an IndexOutOfBoundsException if h &lt; 0 or h &gt;= size of the list.
     * The time taken should be proportional to min(h, size - h). */
    public @Override E set(int h, E element) {
        // TODO item #8
        // Rely on helper methods to keep this method small.
        // Note that a helper method could throw the exception; doesn't
        // have to be done here.
        return null;
    }

    /** Insert element in a new node at the beginning of the list and
     * return the new node.
     * This operation must take constant time. */
    Node prepend(E element) {// no access modifier. Accessible (only) in package
        // TODO item #9
        // This mid-size helper function will be used by other methods
        return null;
    }

    /** Insert element into a new node before Node node and return the new node.
     * Precondition: node must be a Node of this list; it must not be null.
     * This operation must take constant time.  */
    Node insertBefore(E element, Node node) {// no access modifier. Accessible (only) in package
        // TODO item #10
        // This mid-size helper function will be used by other methods.
        // Do NOT test whether node is actually a Node of this list because
        // it will then not be a constant-time operation.
        return null;
    }

    /**  Insert element in a new node of the list, making it number h.
     * The element that was number h becomesnumber h+1, the element that was number
     * h+1 becomes number h+2, and so on. 
     * Throw an IndexOutOfBoundsException if index &lt; 0 or h &gt; size of the list.
     * Note that if h = size of the list, this means to append element.
     * This operation must take time proportional to min (h, size - index). */
    public @Override void add(int h, E element) {
        // TODO item #11
        // Note that if h = size of the list, this operation appends element to the list.
        // Rely on helper methods to keep this method small.
        // Note that a helper method could throw the exception; it doesn't
        // have to be done here.
    }

    /** Remove node from this list and return its data.
     * Precondition: node must be a Node of this list; it must not be null.
     * Postcondition: To prevent memory leaks, every field of node should be set to null. */
    E removeNode(Node node) {// no access modifier. Accessible (only) in package
        // TODO item #12
        // This is the largest helper method
        return null;
    }

    /** Remove element number h from the list and return the element that was removed.
     * Throw an IndexOutOfBoundsException if h &lt; 0 or h &gt;= size of the list. */
    public @Override E remove(int h) {
        // TODO item #13
        // Rely on helper methods to keep this method small.
        // Note that a helper method could throw the exception; it doesn't
        // have to be done here.
        return null;
    }

    /*********************/

    /** An instance is a node of this list. */
    class Node {// no access modifier. Accessible (only) in package
        /** Predecessor of this node on list (null if this is the first node). */
        Node pred; // no access modifier. Accessible (only) in package

        /** The data in this element. */
        E data; // no access modifier. Accessible (only) in package

        /** Successor of this node on list. (null if is the last node). */
        Node succ; // no access modifier. Accessible (only) in package

        /** Constructor: an instance with predecessor node p (can be null),
         * successor node s (can be null), and data e. */
        Node(Node p, E e, Node s) {// no access modifier. Accessible (only) in package
            pred= p;
            succ= s;
            data= e;
        }
    }
}
</pre></body></html>