Question

public class CDLL_Node<T>
{
  private T data;
  private CDLL_Node<T> prev, next; // EACH CDLL_Node PTS TO ITS PREV  & NEXT

  public CDLL_Node()
  {
    this( null, null, null );  // 3 FIELDS TO INIT
  }

  public CDLL_Node(T data)
  {
    this( data, null, null);
  }

  public CDLL_Node(T data, CDLL_Node<T> prev, CDLL_Node<T> next)
  {
    setData( data );
        setPrev( prev );
    setNext( next );
  }

  public T getData()
  {
    return data;
  }

  public CDLL_Node<T> getPrev()
  {
    return prev;
  }
  public CDLL_Node<T> getNext()
  {
    return next;
  }

  public void setData(T data)
  {
     this.data = data;
  }

  public void setNext(CDLL_Node<T> next)
  {
    this.next = next;
  }
  
  public void setPrev(CDLL_Node<T> prev)
  {
    this.prev = prev;
  }
 
  public String toString()
  {
          return ""+getData();
  } 
         
} //EOF

import java.io.*;
import java.util.*;

public class CDLL_List<T>
{
        private CDLL_Node<T> head;  // pointer to the front (first) element of the list
        private int count=0;
        
        public CDLL_List()
        {
                head = null; // compiler does this anyway. just for emphasis
        }

        // LOAD LINKED LIST FROM INCOMING FILE
        @SuppressWarnings("unchecked")
        public CDLL_List( String fileName, boolean orderedFlag )
        {       head = null;
                try
                {
                        BufferedReader infile = new BufferedReader( new FileReader( fileName ) );
                        while ( infile.ready() )
                        {
                                if (orderedFlag)
                                        insertInOrder( (T)infile.readLine() );  // WILL INSERT EACH ELEM INTO IT'S SORTED POSITION
                                else
                                        insertAtTail( (T)infile.readLine() );  // TACK EVERY NEWELEM ONTO END OF LIST. ORIGINAL ORDER PRESERVED
                        }
                        infile.close();
                }
                catch( Exception e )
                {
                        System.out.println( "FATAL ERROR CAUGHT IN C'TOR: " + e );
                        System.exit(0);
                }
        }

        //-------------------------------------------------------------



        // ########################## Y O U   W R I T E    T H E S E    M E T H O D S ########################

        // inserts new elem at front of list - pushing old elements back one place

        public void insertAtFront(T data)
        {
                // WRITE THE LINES OF CODE TO DO THE INSERT
        }
        public void insertAtTail(T data)
        {
                // CALL INSERT AT FRONT HERE 
                // THEN ADJUST THE HEAD POINTER 
        }
        public boolean removeAtTail()   // RETURNS TRUE IF THERE WAS NODE TO REMOVE
        {
                return false; // YOUR CODE HERE. TRY TO DO CODE RE-USE SIMILAR TO FRONT
        }

        public boolean removeAtFront() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
        {
                return false; // YOUR CODE HERE.  // TRY TO DO CODE RE-USE SIMILAR TO FRONT
        }

        public String toString()
        {
                String toString = "";  // NO <=> DELIMITERS REQUIRED ANYWHERE IN OUTPUT

                return toString;  // JUST A SPACE BETEEN ELEMENTS LIKE IN LAB3
        }

        public int size() // OF COURSE MORE EFFICIENT to KEEP COUNTER BUT YOU  MUST WRITE LOOP
        {
                return 0; // YOUR CODE HERE
        }

        public boolean empty()
        {
                return false;  // YOUR CODE HERE
        }

        public boolean contains( T key )
        {
                return false;  // YOUR CODE HERE
        }

        public CDLL_Node<T> search( T key )
        {
                return null;  // YOUR CODE HERE
        }

        @SuppressWarnings("unchecked")  //CAST TO COMPARABLE THROWS WARNING
        public void insertInOrder(T  data)
        {
                // YOUR CODE HERE
        }

        public boolean remove(T key)
        {
                return false; //  REPLACE WITH YOUR CODE 
        }


        public CDLL_List<T> union( CDLL_List<T> other )
        {
                CDLL_List<T> union = new CDLL_List<T>();

                // YOUR CODE HERE

                return union;
        }
        public CDLL_List<T> inter( CDLL_List<T> other )
        {
                CDLL_List<T> inter = new CDLL_List<T>();

                // YOUR CODE HERE

                return inter;
        }
        public CDLL_List<T> diff( CDLL_List<T> other )
        {
                CDLL_List<T> diff = new CDLL_List<T>();

                // YOUR CODE HERE

                return diff;
        }
        public CDLL_List<T> xor( CDLL_List<T> other )
        {
                return  null;  // REPLACE WITH YOUR CODE 
        }

} //END CDLL_LIST CLASS

// A D D   C D L L  N O D E   C L A S S  D O W N   H E R E 
// R E M O V E  A L L  P U B L I C  &  P R I V A T E (except toString)
// R E M O V E  S E T T E R S  &  G E T T E R S 
// M A K E  T O  S T R I N G  P U B L I C

import java.io.*;
import java.util.*;

public class CDLL_Tester
{
        public static void main( String args[] ) throws Exception
        {
                CDLL_List<String> list1 = new CDLL_List<String>( args[0], false );  // false = INSERTATTAIL CALLED ON EACH T READ FROM FILE
                System.out.format("list1 %s size %d unordered %s\n",args[0],list1.size(),list1 ); // invokes toString
                
                list1.remove( "charlie" ); list1.remove("echo"); list1.remove("zebra"); // HEAD, TAIL, NOWHERE
                System.out.format("list1 (after remove charlie, echo & zebra) %s\n",list1 ); // invokes toString
                
                CDLL_List<String> list2 = new CDLL_List<String>( args[0], true );  // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
                System.out.format("list2 %s size %d ordered %s\n",args[0],list2.size(),list2 ); // invokes toString

                CDLL_List<String> list3 = new CDLL_List<String>( args[1], true );  // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
                System.out.format("list3 %s size %d ordered %s\n",args[1],list3.size(),list3 ); // invokes toString     
                
                // MUST RETURN ALL SET OP LISTS IN SORTED ORDER NO DUPES 
                CDLL_List<String> unionList = list2.union(list3);
                System.out.println("list2.union(list3) " + unionList);  
                
                CDLL_List<String> interList = list2.inter(list3); 
                System.out.println("list2.inter(list3) " + interList); 
                
                CDLL_List<String> diffList = list2.diff(list3);           
                System.out.println("list2.diff(list3)  " + diffList); 
                
                CDLL_List<String> xorList = list2.xor(list3);                             
                System.out.println("list2.xor(list3)   " + xorList); 
                
                // ECHO LISTS 2 & 3  TO PROVE THEY WERE NOT MODIFIED
                
                System.out.println();
                System.out.println( "list2 after set ops: " + list2 );
                System.out.println( "list3 after set ops: " + list3 );
                
                // DESTROY LIST2 BY REPEATEDLY CALLING REMOVE AT TAIL UNTIL EMPTY
                while ( ! list2.empty() ) list2.removeAtTail();

                // DESTROY LIST3 BY REPEATEDLY CALLING REMOVE AT FRONT
                while ( ! list3.empty() ) list3.removeAtFront();
                
        // ECHO LISTS 2 & 3  TO PROVE THEY WERE DESTROYED
                
                System.out.println();
                System.out.println( "list2 after all nodes removedAtTail: " + list2 );
                System.out.println( "list3 after all nodes removedAtFront: " + list3 );
        } // END MAIN
} // EOF

set1.txt

charlie
bravo
delta
alpha
golf
india
hotel
echo

set2.txt

foxtrot
baker
xray
zebra
charlie
victor

Answer 1

//============CDLL_Node.java======================
public class CDLL_Node<T>
{
private T data;
private CDLL_Node<T> prev, next; // EACH CDLL_Node PTS TO ITS PREV & NEXT

public CDLL_Node()
{
this( null, null, null ); // 3 FIELDS TO INIT
}

public CDLL_Node(T data)
{
this( data, null, null);
}

public CDLL_Node(T data, CDLL_Node<T> prev, CDLL_Node<T> next)
{
setData( data );
setPrev( prev );
setNext( next );
}

public T getData()
{
return data;
}

public CDLL_Node<T> getPrev()
{
return prev;
}
public CDLL_Node<T> getNext()
{
return next;
}

public void setData(T data)
{
this.data = data;
}

public void setNext(CDLL_Node<T> next)
{
this.next = next;
}
  
public void setPrev(CDLL_Node<T> prev)
{
this.prev = prev;
}

public String toString()
{
return ""+getData();
}

} //EOF CDLL_Node.java
//==================================

//============CDLL_List.java======================
import java.io.*;

public class CDLL_List<T>
{
private CDLL_Node<T> head; // pointer to the front (first) element of the list
private int count=0;
//________________________________
public CDLL_List()
{
head = null; // compiler does this anyway. just for emphasis
}

// LOAD LINKED LIST FROM INCOMING FILE
//________________________________
@SuppressWarnings("unchecked")
public CDLL_List( String fileName, boolean orderedFlag )
{ head = null;
try
{
BufferedReader infile = new BufferedReader( new FileReader( fileName ) );
while ( infile.ready() )
{
if (orderedFlag)
insertInOrder( (T)infile.readLine() ); // WILL INSERT EACH ELEM INTO IT'S SORTED POSITION
else
insertAtTail( (T)infile.readLine() ); // TACK EVERY NEWELEM ONTO END OF LIST. ORIGINAL ORDER PRESERVED
}
infile.close();
}
catch( Exception e )
{
System.out.println( "FATAL ERROR CAUGHT IN C'TOR: " + e );
System.exit(0);
}
}
//________________________________
public void insertAtFront(T data)
{
   CDLL_Node<T> node=new CDLL_Node<T>(data);   
   if(head==null) {
       node.setNext(node);
       node.setPrev(node);
       head=node;
       return;
}
   node.setNext(head);
   node.setPrev(head.getPrev());
   head.getPrev().setNext(node);
   head.setPrev(node);
   head=node;

}
//________________________________
public void insertAtTail(T data)
{
   insertAtFront(data);
   head=head.getNext();
}
//________________________________
public T removeAtFront() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
{
if(head==null)
   return null;
//only one item
if(head.getNext()==head.getPrev()) {
   T key=head.getData();
   head=null;
   return key;
}
T key=head.getData();
head.getNext().setPrev(head.getPrev());
head.getPrev().setNext(head.getNext());
head=head.getNext();
return key;
}
//________________________________
public boolean removeAtTail() // RETURNS TRUE IF THERE WAS NODE TO REMOVE
{
   if(head==null)
   return false;
//only one item
if(head.getNext()==head.getPrev()) {
   head=null;
   return true;
}
head=head.getPrev();
removeAtFront();
return true;
}
//________________________________
public String toString()
{
String toString = ""; // NO <=> DELIMITERS REQUIRED ANYWHERE IN OUTPUT
CDLL_Node<T> temp=head;
if(head==null)
   return toString;
//only one item
if(head.getNext()==head.getPrev()) {
   toString=toString+head.getData();
   return toString;
}
toString=toString+temp.getData()+" ";
temp=temp.getNext();
while(temp!=head) {
   toString=toString+temp.getData()+" ";
temp=temp.getNext();
}
return toString; // JUST A SPACE BETEEN ELEMENTS LIKE IN LAB3
}
//________________________________
public int size() // OF COURSE MORE EFFICIENT to KEEP COUNTER BUT YOU MUST WRITE LOOP
{
int count=0;
CDLL_Node<T> temp=head;
if(head==null)
   return count;
//only one item
if(head.getNext()==head.getPrev()) {
   count++;
   return count;
}
count++;
temp=temp.getNext();
while(temp!=head) {
   count++;
temp=temp.getNext();
}
return count;
}
//________________________________
public boolean empty()
{
return head==null; // YOUR CODE HERE
}
//________________________________
public boolean contains( T key )
{
   CDLL_Node<T> temp=head;
  
if(head==null)
   return false;
//only one item
if(head.getNext()==head.getPrev()) {
   if(key==head.getData())
       return true;
   else
       return false;
}
//check the first node
if(key==head.getData())
       return true;
//check rest of the nodes
temp=temp.getNext();
while(temp!=head) {
   if(key==head.getData())
       return true;
temp=temp.getNext();
}
return false; // YOUR CODE HERE
}
//________________________________
public CDLL_Node<T> search( T key )
{
   CDLL_Node<T> temp=head;
   if(head==null)
   return null;
   //only one item
if(head.getNext()==head.getPrev()) {
   if(key==head.getData())
       return temp;
   else
       return null;
}
//check the first node
if(key==temp.getData())
       return temp;
//check rest of the nodes
temp=temp.getNext();
while(temp!=head) {
   if(key==head.getData())
       return temp;
temp=temp.getNext();
}
return null; // YOUR CODE HERE
}
//________________________________
//@SuppressWarnings("unchecked") //CAST TO COMPARABLE THROWS WARNING
public void insertInOrder(T data)
{
if(head==null) {
   insertAtFront(data);
   return;
}
CDLL_Node<T> node=new CDLL_Node<T>(data);
CDLL_Node<T> temp=head;
if(head.getNext()==head.getPrev()) {
   if(data.toString().compareTo(head.getData().toString())<=0)
                       insertAtFront(data);
               else {
                   node.setNext(head.getNext());
                   node.setPrev(head);
                   head.setNext(node);
               }
               return;
}
do {
   if(data.toString().compareTo(temp.getData().toString())>=0 && data.toString().compareTo(temp.getNext().getData().toString())<0) {
       node.setNext(temp.getNext());
       node.setPrev(temp);
       temp.getNext().setPrev(node);
       temp.setNext(node);
       return;
   }
   temp=temp.getNext();
  
}while(temp!=head);
//insert at the tail of the list
insertAtTail(data);
}
//________________________________
public boolean remove(T key)
{
if(head==null)
   return false;
if(head.getData()==key) {
   removeAtFront();
   return true;
}
CDLL_Node<T> temp=head;
do {
   if(temp.getData()==key) {
       temp.getPrev().setNext(temp.getNext());
       temp.getNext().setPrev(temp.getPrev());
       return true;
   }
   temp=temp.getNext();
}while(temp!=head);
  
   return false; // REPLACE WITH YOUR CODE
}
//________________________________
public CDLL_List<T> union( CDLL_List<T> other )
{
CDLL_List<T> union = new CDLL_List<T>();
CDLL_List<T> tempList = new CDLL_List<T>();

if(!empty()) {
   CDLL_Node<T> temp=head;
   do {
       union.insertAtFront(temp.getData());
       temp=temp.getNext();
   }while(temp!=head);
}
while(!other.empty()) {
   T key=other.removeAtFront();
   if(union.contains(key)==false)
       union.insertAtFront(key);
   tempList.insertAtTail(key);
}
other=tempList;
return union;
}
//________________________________
public CDLL_List<T> inter( CDLL_List<T> other )
{
CDLL_List<T> inter = new CDLL_List<T>();

if(!empty()) {
    CDLL_Node<T> temp=head;
    do {
        if(other.contains(temp.getData())==true) {
            inter.insertAtFront(temp.getData());
        }
        temp=temp.getNext();
    }while(temp!=head);
}

return inter;
}
//________________________________
public CDLL_List<T> diff( CDLL_List<T> other )
{
CDLL_List<T> diff = new CDLL_List<T>();

if(!empty()) {
   CDLL_Node<T> temp=head;
   do {
       if(other.contains(temp.getData())==false) {
           diff.insertAtFront(temp.getData());
       }
       temp=temp.getNext();
   }while(temp!=head);
}

return diff;
}
//________________________________
       public int getCount() {
           size();
           return count;
       }
       //________________________________
}

//=====end of CDLL_List.java====================================

//============CDLL_Tester.java========================
public class CDLL_Tester
{
public static void main( String args[] ) throws Exception
{
CDLL_List<String> list1 = new CDLL_List<String>( args[0], false ); // false = INSERTATTAIL CALLED ON EACH T READ FROM FILE
System.out.format("list1 %s size %d unordered %s\n",args[0],list1.size(),list1 ); // invokes toString
  
list1.remove( "charlie" ); list1.remove("echo"); list1.remove("zebra"); // HEAD, TAIL, NOWHERE
System.out.format("list1 (after remove charlie, echo & zebra) %s\n",list1 ); // invokes toString
  
CDLL_List<String> list2 = new CDLL_List<String>( args[0], true ); // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
System.out.format("list2 %s size %d ordered %s\n",args[0],list2.size(),list2 ); // invokes toString

CDLL_List<String> list3 = new CDLL_List<String>( args[1], true ); // true = INSERTINORDER CALLED ON EACH T READ FROM FILE
System.out.format("list3 %s size %d ordered %s\n",args[1],list3.size(),list3 ); // invokes toString   
  
// MUST RETURN ALL SET OP LISTS IN SORTED ORDER NO DUPES
CDLL_List<String> unionList = list2.union(list3);
System.out.println("list2.union(list3) " + unionList);
  
CDLL_List<String> interList = list2.inter(list3);
System.out.println("list2.inter(list3) " + interList);
  
CDLL_List<String> diffList = list2.diff(list3);   
System.out.println("list2.diff(list3) " + diffList);
  
  
// ECHO LISTS 2 & 3 TO PROVE THEY WERE NOT MODIFIED
  
System.out.println();
System.out.println( "list2 after set ops: " + list2 );
System.out.println( "list3 after set ops: " + list3 );
  
// DESTROY LIST2 BY REPEATEDLY CALLING REMOVE AT TAIL UNTIL EMPTY
while ( ! list2.empty() ) list2.removeAtTail();

// DESTROY LIST3 BY REPEATEDLY CALLING REMOVE AT FRONT
while ( ! list3.empty() ) list3.removeAtFront();
  
// ECHO LISTS 2 & 3 TO PROVE THEY WERE DESTROYED
  
System.out.println();
System.out.println( "list2 after all nodes removedAtTail: " + list2 );
System.out.println( "list3 after all nodes removedAtFront: " + list3 );
} // END MAIN
} // EOF
//===========end of CDLL_Tester.java=================