hw4 打卡

荒废已久啦~~回归打卡

DListNode.java:

package hw4;

/* 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;

  /* 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);
  }

  /**2
    *  DList() constructor for an empty DList.
   */
  public DList() {      
    //  Your solution here.
      head=new newNode(null,null,null);
      head.next=head;
      head.prev=head;
      size=0;
  }

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

  /**
   *  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 null;
      }else {
          return head.next;
      }
  }

  /**
   *  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 null;
        }else{
          return head.prev;
        }
  }

  /**
   *  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) {
    // Your solution here.
      if(size==0||node==head.prev) {
          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) {
    // Your solution here.
      if(size == 0||node==head.next){
          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);
          node.next.next.prev=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);
          node.prev.prev.next=node.prev;
          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 + "]";
  }
}

View Code

LockDListNode.java:

package hw4;

public class LockDListNode extends DListNode{
    protected boolean lock;
    LockDListNode(Object i,DListNode p,DListNode n){
        super(i,p,n);
        lock=false;
    }
}

View Code

LockDList.java:

package hw4;

public class LockDList extends DList{ 
     public void LockNode(DListNode node){
         ((LockDListNode)node).lock=true;
     }
     protected LockDListNode newNode(Object item, DListNode prev, DListNode next){
         return new LockDListNode(item, prev, next);
     }
     public LockDListNode front(){
         return (LockDListNode)(super.front());
     }
     public LockDListNode back(){
         return (LockDListNode)(super.back());
     }
     public LockDListNode next(DListNode node){
         return (LockDListNode)(super.next(node));
     }
     public LockDListNode prev(DListNode node){
         return (LockDListNode)(super.prev(node));
     }
     public void remove(DListNode node){
         if(!((LockDListNode)node).lock){
         super.remove(node);
        }
     }
}

View Code

测试结果：

测试代码网上找的，感觉大家的都差不多哈哈哈