1
\$\begingroup\$

I am trying to follow the template provided here to create a doubly linked list in java. This homework is based on this lecture. Can someone please review my implementation?

No change to this part of the code

/* DListNode.java */



/**
 *  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;
  protected DListNode prev;
  protected 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;
    prev = p;
    next = n;
  }
}

This is the code that I updated

/* DList.java */



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

public class DList {

  /**
   *  head 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 head;
  protected int size;
  private DListNode sentinel;

  /* DList invariants:
   *  1)  head != 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 (head) 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() {
    //  Your solution here.
      sentinel=newNode(null,null,null);
      sentinel.prev=sentinel;
      sentinel.next=sentinel;
      head=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) {
    // Your solution here.
      sentinel.next=newNode(item,sentinel,sentinel.next);
      if(sentinel.prev==sentinel)
      {
          sentinel.prev=sentinel.next;
      }
      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) {
    // Your solution here.
      sentinel.prev=newNode(item,sentinel.prev,sentinel);
      if(sentinel.next==sentinel)
      {
          sentinel.next=sentinel.prev;
      }
      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() {
    // Your solution here.
      if(size>0)
      {
          return sentinel.next;
      }
      else
      {
          return null;
      }
  }

  /**
   *  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() {
    // Your solution here.
      if(size>0)
      {
          return sentinel.prev;
      }
      else
      {
          return null;
      }
  }

  /**
   *  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.next==sentinel)
    {
        return null;
    }
    else
    {
        return node.next;
    }
  }

  /**
   *  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.prev==sentinel)
        {
            return null;
        }
        else
        {
            return node.prev;
        }
  }

  /**
   *  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) {
    // Your solution here.
      if(node!=null);
        {
          node.next=newNode(item,node,node.next);
          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) {
    // Your solution here.
      if(node!=null);
        {
          node.prev=newNode(item,node.prev,node);
          size++;
        }
  }

  /**
   *  remove() removes "node" from this DList.  If "node" is null, do nothing.
   *  Performance:  runs in O(1) time.
   */
  public void remove(DListNode node) {
    // Your solution here.
      if(node!=null);
        {

                node.prev.next=node.next;
                node.next.prev=node.prev; 
                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 = head.next;
    while (current != head) {
      result = result + current.item + "  ";
      current = current.next;
    }
    return result + "]";
  }
}
\$\endgroup\$
  • \$\begingroup\$ Do you already know, what generics are? If yes, then try to update your DListNode and DList classes to use generics there. It improves type safety. \$\endgroup\$ – Tom Nov 24 '14 at 22:26
2
\$\begingroup\$

No, this is not correct. Your solution does nothing to satisfy these invariants:

   *  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.

For example:

  public void insertFront(Object item) {
      sentinel.next=newNode(item,sentinel,sentinel.next);
      if(sentinel.prev==sentinel)
      {
          sentinel.prev=sentinel.next;
      }
      size++;
  }

For any DListNode x, x.prev is the sentinel.

You have the same kind of mistake in insertBack too.


The ternary operator can make some of your functions much more compact. For example, instead of:

  public DListNode front() {
    // Your solution here.
      if(size>0)
      {
          return sentinel.next;
      }
      else
      {
          return null;
      }
  }

You can write:

public DListNode front() {
    return size > 0 ? sentinel.next : null;
}

I recommend to follow this formatting style:

public void insertBack(Object item) {
    DListNode node = newNode(item, sentinel.prev, sentinel);
    sentinel.prev = node;
    if (sentinel.next == sentinel) {
        sentinel.next = sentinel.prev;
    }
    size++;
}

Notice the indentation, the placement of {, and the use of spaces between parameters (in the newNode call), and around operators (=, and ==).

\$\endgroup\$
1
\$\begingroup\$

In addition to what others have answered, I don't know if you are aware of this typo that you made:

if (node != null);
{
    ...
}

You have an extraneous semicolon after your if statement which makes your if useless.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.