Lockable linked list

Question

The existing design of class DList and DListNode is taken. The main criteria is to do successive updates in \$O(1)\$ time.

Part III (3 points)

Implement a "lockable" doubly-linked list ADT: a list in which any node can be "locked." A locked node can never be removed from its list. Any attempt to remove a locked node has no effect (not even an error message). Your locked list classes should be in the list package alongside DList and DListNode. First, define a LockDListNode class that extends DListNode and carries information about whether it has been locked. LockDListNode's are not locked when they are first created. Your LockDListNode constructor(s) should call a DListNode constructor to avoid code duplication.

Second, define a LockDList class that extends DList and includes an additional method public void lockNode(DListNode node) { ... } that permanently locks "node".

Your LockDList class should override just enough methods to ensure that

(1) LockDListNode's are always used in LockDList's (instead of DListNode's), and

(2) locked nodes cannot be removed from a list.

WARNING: To override a method, you must write a new method in the subclass with EXACTLY the same prototype. You can’t change a parameter’s type to a subclass. Overriding won’t work if you do that.

Your overriding methods should include calls to the overridden superclass methods whenever it makes sense to do so. Unnecessary code duplication will be penalized.

Solution

/* DListNode.java */
package cs61b.homework4;

/**
 * A DListNode is a node in a DList (doubly-linked list).
 */

public class DListNode {

    /**
     * item references the item stored in the current node. prev references the
     * previous node in the DList. next references the next node in the DList.
     *
     * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
     */

    public Object item;
    private DListNode prev;
    private DListNode next;

    /**
     * DListNode() constructor.
     * 
     * @param i
     *            the item to store in the node.
     * @param p
     *            the node previous to this node.
     * @param n
     *            the node following this node.
     */
    DListNode(Object i, DListNode p, DListNode n) {
        item = i;
        setPrev(p);
        setNext(n);
    }

    DListNode getNext() {
        return next;
    }

    void setNext(DListNode next) {
        this.next = next;
    }

    DListNode getPrev() {
        return prev;
    }

    void setPrev(DListNode prev) {
        this.prev = prev;
    }
}

---

/* DList.java */
package cs61b.homework4;


/**
 *  A DList is a mutable doubly-linked list ADT.  Its implementation is
 *  circularly-linked and employs a sentinel (dummy) node at the sentinel
 *  of the list.
 *
 *  DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
 */

public class DList {

  /**
   *  sentinel references the sentinel node.
   *  size is the number of items in the list.  (The sentinel node does not
   *       store an item.)
   *
   *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
   */

  protected DListNode sentinel;
  protected int size;

  /* DList invariants:
   *  1)  sentinel != null.
   *  2)  For any DListNode x in a DList, x.next != null.
   *  3)  For any DListNode x in a DList, x.prev != null.
   *  4)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
   *  5)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
   *  6)  size is the number of DListNodes, NOT COUNTING the sentinel,
   *      that can be accessed from the sentinel (sentinel) by a sequence of
   *      "next" references.
   */

  /**
   *  newNode() calls the DListNode constructor.  Use this class to allocate
   *  new DListNodes rather than calling the DListNode constructor directly.
   *  That way, only this method needs to be overridden if a subclass of DList
   *  wants to use a different kind of node.
   *  @param item the item to store in the node.
   *  @param prev the node previous to this node.
   *  @param next the node following this node.
   */
  protected DListNode newNode(Object item, DListNode prev, DListNode next) {
    return new DListNode(item, prev, next);
  }

  /**
   *  DList() constructor for an empty DList.
   */
  public DList() {
      this.sentinel = this.newNode(null,null,null);
      this.sentinel.setNext(sentinel);
      this.sentinel.setPrev(sentinel);
  }

  /**
   *  isEmpty() returns true if this DList is empty, false otherwise.
   *  @return true if this DList is empty, false otherwise. 
   *  Performance:  runs in O(1) time.
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /** 
   *  length() returns the length of this DList. 
   *  @return the length of this DList.
   *  Performance:  runs in O(1) time.
   */
  public int length() {
    return size;
  }

  /**
   *  insertFront() inserts an item at the front of this DList.
   *  @param item is the item to be inserted.
   *  Performance:  runs in O(1) time.
   */
  public void insertFront(Object item) {
      DListNode node  = this.newNode(item, this.sentinel, this.sentinel.getNext());
      node.getNext().setPrev(node);  
      this.sentinel.setNext(node);
      this.size++;
  }

  /**
   *  insertBack() inserts an item at the back of this DList.
   *  @param item is the item to be inserted.
   *  Performance:  runs in O(1) time.
   */
  public void insertBack(Object item) {
      DListNode node = this.newNode(item, this.sentinel.getPrev(), this.sentinel);
      this.sentinel.setPrev(node);
      node.getPrev().setNext(node);
      this.size++;
  }

  /**
   *  front() returns the node at the front of this DList.  If the DList is
   *  empty, return null.
   *
   *  Do NOT return the sentinel under any circumstances!
   *
   *  @return the node at the front of this DList.
   *  Performance:  runs in O(1) time.
   */
  public DListNode front() {
      if (this.sentinel.getNext() == sentinel){
          return null;
      }else{
          return this.sentinel.getNext();
      }
  }

  /**
   *  back() returns the node at the back of this DList.  If the DList is
   *  empty, return null.
   *
   *  Do NOT return the sentinel under any circumstances!
   *
   *  @return the node at the back of this DList.
   *  Performance:  runs in O(1) time.
   */
  public DListNode back() {
    if(this.sentinel.getPrev() == sentinel){
        return null;
    }else{
        return this.sentinel.getPrev();
    }
  }

  /**
   *  next() returns the node following "node" in this DList.  If "node" is
   *  null, or "node" is the last node in this DList, return null.
   *
   *  Do NOT return the sentinel under any circumstances!
   *
   *  @param node the node whose successor is sought.
   *  @return the node following "node".
   *  Performance:  runs in O(1) time.
   */
  public DListNode next(DListNode node) {
      if ((node == null) || (node.getNext() == this.sentinel)){
          return null;
      }else{
          return node.getNext();
      }
  }

  /**
   *  prev() returns the node prior to "node" in this DList.  If "node" is
   *  null, or "node" is the first node in this DList, return null.
   *
   *  Do NOT return the sentinel under any circumstances!
   *
   *  @param node the node whose predecessor is sought.
   *  @return the node prior to "node".
   *  Performance:  runs in O(1) time.
   */
  public DListNode prev(DListNode node) {
      if ((node == null) || (node.getPrev() == this.sentinel)){
          return null;
      }else{
          return node.getPrev();
      }
  }

  /**
   *  insertAfter() inserts an item in this DList immediately following "node".
   *  If "node" is null, do nothing.
   *  @param item the item to be inserted.
   *  @param node the node to insert the item after.
   *  Performance:  runs in O(1) time.
   */
  public void insertAfter(Object item, DListNode node) {
      if (node == null){
          return;
      }else{
          DListNode newNode = this.newNode(item, node, node.getNext());
          node.getNext().setPrev(newNode);
          node.setNext(newNode);
      }
      this.size++;
  }

  /**
   *  insertBefore() inserts an item in this DList immediately before "node".
   *  If "node" is null, do nothing.
   *  @param item the item to be inserted.
   *  @param node the node to insert the item before.
   *  Performance:  runs in O(1) time.
   */
  public void insertBefore(Object item, DListNode node) {
      if (node == null){
          return;
      }else{
          DListNode newNode =  this.newNode(item, node.getPrev(), node);
          node.getPrev().setNext(newNode);
          node.setPrev(newNode);
          this.size++;
      }

  }

  /**
   *  remove() removes "node" from this DList.  If "node" is null, do nothing.
   *  Performance:  runs in O(1) time.
   */
  public void remove(DListNode node) {
      if(node == null){
          return;
      }else{
          node.item = null;
          node.getPrev().setNext(node.getNext());
          node.getNext().setPrev(node.getPrev());
          this.size--;
      }

  }

  /**
   *  toString() returns a String representation of this DList.
   *
   *  DO NOT CHANGE THIS METHOD.
   *
   *  @return a String representation of this DList.
   *  Performance:  runs in O(n) time, where n is the length of the list.
   */
  public String toString() {
    String result = "[  ";
    DListNode current = sentinel.getNext();
    while (current != sentinel) {
      result = result + current.item + "  ";
      current = current.getNext();
    }
    return result + "]";
  }
}

---

/* LockDListNode.java */

package cs61b.homework4;


public class LockDListNode extends DListNode{

    protected boolean lock;


    protected LockDListNode(Object i, DListNode p, DListNode n){
        super(i, p, n);
        this.lock = false;

    }
}

---

/* LockDList.java */
package cs61b.homework4;





public class LockDList extends DList {

    /**
     * newNode() calls the LockDListNode constructor. Use this method to
     * allocate new LockDListNodes rather than calling the LockDListNode
     * constructor directly.
     * 
     * @param item
     *            the item to store in the node.
     * @param prev
     *            the node previous to this node.
     * @param next
     *            the node following this node.
     */
    protected LockDListNode newNode(Object item, DListNode prev, DListNode next) {
        return new LockDListNode(item, prev, next);
    }

    /**
     * LockDList() constructor for an empty LockDList.
     */
    public LockDList() { 
        super();    
    }

    /**
     * remove() removes "node" from this DList. If "node" is null, do nothing.
     * Performance: runs in O(1) time.
     */
    public void remove(DListNode node) {
        if (node == null) {
            return;
        } else if (((LockDListNode)node).lock == true) {
            return;
        } else {
            node.item = null;
            node.getPrev().setNext(node.getNext());
            node.getNext().setPrev(node.getPrev());
            this.size--;
        }
    }

    public void lockNode(DListNode node) {
        if(node == null){
            return;
        }else{
            ((LockDListNode)node).lock = true;
        }

    }

}

---

With the given skeleton code for DList and DListNode here:

1. Assume that a user passes a node that is part of the correct list. This is out of scope here.
2. Access specifier for class/method/constructor can be improved (if required).
3. Can I avoid typecasting in overriding the remove method of the LockDList class?
4. Can I avoid typecasting in the lockNode method of the LockDListclass?

Note: The package name is cs61b.homework4 instead of list.

Answer 1

Simplify your boolean logic.

In LockDList.remove you can remove two of the branches and end up with

if (node != null && !((LockDListNode)node).lock) {
    node.item = null;
    node.prev.next = node.next;
    node.next.prev = node.prev;
    this.size--;
}

Because we don't do anything in the other cases we don't need those empty returns, and we don't need two separate branches for node == null and ((LockDListNode)node).lock == true because the conditional will short circuit. Furthermore, you don't need to compare a boolean to true or false because it already is either true or false.

Similarly you can simplify lockNode. You don't need the empty conditional branch.

public void lockNode(DListNode node) {
    if (node != null){
        ((LockDListNode) node).lock = true;
    }

Use the supertype's implementation where possible

In remove you can simplify even further to

if (node != null && !((LockDListNode) node).lock) {
    super.remove(node);
}

Override methods explicitly

I like to use the @Override annotation when I'm overriding a method. This provides the following benefits:

Indicates that a method declaration is intended to override a method declaration in a supertype. If a method is annotated with this annotation type compilers are required to generate an error message unless at least one of the following conditions hold:
- The method does override or implement a method declared in a supertype.
- The method has a signature that is override-equivalent to that of any public method declared in Object.

As well as making it explicit to readers that you're overriding a method.

Things I noticed in DList

Unrelated to the LockDList logic, but I notice that you're somewhat inconsistent with your whitespace. I see things like

if (this.sentinel.next == sentinel){
    return null;
}else{
    return this.sentinel.next;
}

and

if(this.sentinel.prev == sentinel){
    return null;
}else{
    return this.sentinel.prev;
}

right next to each other. In general adding extra whitespace will make things easier to read; you can change those to something like

if (this.sentinel.next == sentinel) {
    return null;
} else {
    return this.sentinel.next;
}

I like whitespace between my curly braces and their surrounding statements, and on the outside of the parens in an if statement or while/for loop.

I also notice that your DList implementations of insert and remove also have the unnecessary empty conditional branches.

Using generics

You've mentioned that you'd like to avoid typecasting and use generics instead. This is tricky, because a list shouldn't reveal it's implementation details, and making LockDList generic would do that; we can't just do

public class LockDList<T extends DListNode> extends DList {}

because now the user not only can know the internal mechanics, they must know. If we want to use generics, it has to be done internally with a factory. For example,

private class NodeFactory<T extends DListNode> {
    private final Constructor<? extends T> ctor;

    NodeFactory(Class<? extends T> impl) throws NoSuchMethodException {
        this.ctor = impl.getConstructor();
    }

    protected T getNewNode(Object item, DListNode prev, DListNode next) throws Exception {
        return ctor.newInstance(item, prev, next);
    }
}

This is a little tricky. We have to have a Constructor object because Java uses type erasure, meaning that at runtime all Java knows about T is that it is some subclass of DListNode. This means that we also need all of this messy error handling in order to compile. Then in the body of our class, we can do something like this.

private NodeFactory<LockDListNode> factory;

{
    try {
        factory = new NodeFactory(Class.forName("LockDListNode"));
    } catch (Exception cex) {
        throw new RuntimeException("LockDListNode class not found");
    }
}

Again, ugly error handling. But, at least we get to do this now!

protected LockDListNode newNode(Object item, DListNode prev, DListNode next) {
    try {
        return factory.getNewNode(item, prev, next);
    } catch (Exception e) {
        throw new RuntimeException("New node could not be created");
    }
}

Except that is WAY worse than what you had before. It is much less legible and can throw new runtime errors. We also can't effectively (or at least I didn't come up with a way to) remove the casting from remove and lockNode (although because lockNode only applies to locked lists, you could probably make that take a LockDListNode).

The long and short of it is that you'll have to do a lot of generic hacking to remove 3 casts; casts that make sense and work. The generics don't make sense and might not work. And most importantly, because of type erasure, generics will use type casting under the hood anyway to ensure type safety.

More good reading on type erasure