PART I:

DList:

1 public DList() {  2     // Your solution here.  Similar to Homework 4, but now you need to specify  3     //   the `list' field (second parameter) as well.  4     head = newNode(null, null, null, null);  5     head.prev =head;  6     head.next =head;  7     size = 0;  8   }  9  10   /** 11    *  insertFront() inserts an item at the front of this DList. 12    * 13    *  @param item is the item to be inserted. 14    * 15    *  Performance:  runs in O(1) time. 16    **/ 17   public void insertFront(Object item) { 18     // Your solution here.  Similar to Homework 4, but now you need to specify 19     //   the `list' field (second parameter) as well. 20     head.next = newNode(item, this, head, head.next); 21     head.next.next.prev = head.next; 22     size++; 23   } 24  25   /** 26    *  insertBack() inserts an item at the back of this DList. 27    * 28    *  @param item is the item to be inserted. 29    * 30    *  Performance:  runs in O(1) time. 31    **/ 32   public void insertBack(Object item) { 33     // Your solution here.  Similar to Homework 4, but now you need to specify 34     //   the `list' field (second parameter) as well. 35     head.prev = newNode(item, this, head.prev, head); 36     head.prev.prev.next = head.prev; 37     size++; 38   } 39 DListNode: 40 public void insertAfter(Object item) throws InvalidNodeException { 41         if (!isValidNode()) { 42           throw new InvalidNodeException("insertAfter() called on invalid node"); 43         } 44         // Your solution here.  Will look something like your Homework 4 solution, 45         //   but changes are necessary.  For instance, there is no need to check if 46         //   "this" is null.  Remember that this node's "myList" field tells you 47         //   what DList it's in.  You should use myList.newNode() to create the 48         //   new node. 49         DListNode newNode=new DListNode(item, (DList)this.myList, this, this.next);       50         this.next.prev=newNode; 51         this.next=newNode; 52         this.myList.size++; 53       } 54  55       /** 56        *  insertBefore() inserts an item immediately preceding this node.  If this 57        *  node is invalid, throws an exception. 58        * 59        *  @param item the item to be inserted. 60        *  @exception InvalidNodeException if this node is not valid. 61        * 62        *  Performance:  runs in O(1) time. 63        */ 64       public void insertBefore(Object item) throws InvalidNodeException { 65         if (!isValidNode()) { 66           throw new InvalidNodeException("insertBefore() called on invalid node"); 67         } 68         // Your solution here.  Will look something like your Homework 4 solution, 69         //   but changes are necessary.  For instance, there is no need to check if 70         //   "this" is null.  Remember that this node's "myList" field tells you 71         //   what DList it's in.  You should use myList.newNode() to create the 72         //   new node. 73         DListNode newNode=new DListNode(item,(DList)this.myList,this.prev,this); 74         this.prev.next = newNode; 75         this.prev=newNode; 76         this.myList.size++; 77 } 78  79       /** 80        *  remove() removes this node from its DList.  If this node is invalid, 81        *  throws an exception. 82        * 83        *  @exception InvalidNodeException if this node is not valid. 84        * 85        *  Performance:  runs in O(1) time. 86        */ 87       public void remove() throws InvalidNodeException { 88         if (!isValidNode()) { 89           throw new InvalidNodeException("remove() called on invalid node"); 90         } 91         // Your solution here.  Will look something like your Homework 4 solution, 92         //   but changes are necessary.  For instance, there is no need to check if 93         //   "this" is null.  Remember that this node's "myList" field tells you 94         //   what DList it's in. 95         this.prev.next=this.next; 96         this.next.prev=this.prev; 97         this.myList.size--;  98  99         // Make this node an invalid node, so it cannot be used to corrupt myList.100         myList = null;101         // Set other references to null to improve garbage collection.102         next = null;103         prev = null;104       }

结果无误，太长了所以不贴了hhh

PART II:

1. insert主要就是遍历list，然后找出合适的位置插入。一般情况下使用前插即可，遍历到list末端时可以使用后插。
2. union比较两个list，由于都是sorted list所以也是从前往后遍历即可。通常情况下也是使用前向插入。注意遍历到末尾的情况。
3. intersect操作方法类似，需要注意sList的长度问题，SList到达末端后需要依次删除curNode的内容。还有就是remove node的方式，之前使用curNode = curNode.next();

curNode.prev().remove(); 这样在最后一个node的情况不太好处理，于是更改了一下

1 /**  2    *  insert() inserts a Comparable element into this Set.  3    *  4    *  Sets are maintained in sorted order.  The ordering is specified by the  5    *  compareTo() method of the java.lang.Comparable interface.  6    *  7    *  Performance:  runs in O(this.cardinality()) time.  8    **/  9       public void insert(Comparable c) { 10           try { 11           if(setList.isEmpty()) { 12               setList.insertFront(c);           13           }else { 14                ListNode currentNode=setList.front(); 15          while(currentNode.isValidNode()) {                         16             if(((Comparable)currentNode.item()).compareTo(c)==0) { 17             break; 18            }else if(((Comparable)currentNode.item()).compareTo(c)>0) { 19                currentNode.insertBefore(c);             20                break; 21            }else if(!currentNode.next().isValidNode()){ 22             currentNode.insertAfter(c);             23             break; 24             } 25             currentNode=currentNode.next(); 26             } 27                } 28             }catch(InvalidNodeException e) { 29                       System.out.println(e); 30                   } 31           } 32  33   /** 34    *  union() modifies this Set so that it contains all the elements it 35    *  started with, plus all the elements of s.  The Set s is NOT modified. 36    *  Make sure that duplicate elements are not created. 37    * 38    *  Performance:  Must run in O(this.cardinality() + s.cardinality()) time. 39    * 40    *  Your implementation should NOT copy elements of s or "this", though it 41    *  will copy _references_ to the elements of s.  Your implementation will 42    *  create new _nodes_ for the elements of s that are added to "this", but 43    *  you should reuse the nodes that are already part of "this". 44    * 45    *  DO NOT MODIFY THE SET s. 46    *  DO NOT ATTEMPT TO COPY ELEMENTS; just copy _references_ to them. 47    **/ 48   public void union(Set s) { 49     // Your solution here. 50     if(s != null && !s.setList.isEmpty()){ 51       ListNode curNode = setList.front(); 52       ListNode sNode = s.setList.front(); 53       Comparable curItem, sItem;  54       try{ 55       while(curNode.isValidNode() && sNode.isValidNode()){ 56         curItem = (Comparable)curNode.item(); 57         sItem = (Comparable)sNode.item(); 58         if(curItem.compareTo(sItem) == 0){ 59            60           sNode = sNode.next(); 61         }else if(curItem.compareTo(sItem) < 0){ 62           if(curNode.next().isValidNode()) { 63               curNode = curNode.next();} 64           else { 65              curNode.insertAfter(sItem); 66              curNode=curNode.next(); 67              sNode = sNode.next(); 68           } 69         }else{           70           curNode.insertBefore(sItem); 71           sNode = sNode.next(); 72            73         } 74       }     75     }catch(InvalidNodeException e){ 76       System.err.println("union() failed"); 77     } 78   } 79   } 80   /** 81    *  intersect() modifies this Set so that it contains the intersection of 82    *  its own elements and the elements of s.  The Set s is NOT modified. 83    * 84    *  Performance:  Must run in O(this.cardinality() + s.cardinality()) time. 85    * 86    *  Do not construct any new ListNodes during the execution of intersect. 87    *  Reuse the nodes of "this" that will be in the intersection. 88    * 89    *  DO NOT MODIFY THE SET s. 90    *  DO NOT CONSTRUCT ANY NEW NODES. 91    *  DO NOT ATTEMPT TO COPY ELEMENTS. 92    **/ 93   public void intersect(Set s) { 94     // Your solution here. 95          ListNode curNode = setList.front(); 96       ListNode sNode = s.setList.front(); 97       Comparable curItem, sItem; 98       try{ 99         while(curNode.isValidNode()){100         if (!sNode.isValidNode()){101               ListNode node=curNode;102               curNode=curNode.next();103               node.remove();104 105         }else {106           curItem = (Comparable)curNode.item();107           sItem = (Comparable)sNode.item();108           if(curItem.compareTo(sItem) == 0){109           curNode = curNode.next();110           sNode = sNode.next();111           }else if(curItem.compareTo(sItem) < 0){              112               ListNode node=curNode;113               curNode=curNode.next();114               node.remove();115 116           }else if(curItem.compareTo(sItem) > 0){117                 sNode = sNode.next();118           }119         }120       }121       }catch(InvalidNodeException e){122         System.err.println("intersect() failed.");123       }124 125     }

结果：