import java.io.*; import java.util.*; public class CDLL_List { private CDLL_Node 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 FORM INCOMING FILE public CDLL_List( String fileName, String insertionMode ) throws Exception { BufferedReader infile = new BufferedReader( new FileReader( fileName ) ); while ( infile.ready() ) { @SuppressWarnings("unchecked") T data = (T) infile.readLine(); // CAST CUASES WARNING (WHICH WE CONVENIENTLY SUPPRESS) if ( insertionMode.equals("atFront") ) insertAtFront( data ); else if ( insertionMode.equals( "atTail" ) ) insertAtTail( data ); else die( "FATAL ERROR: Unrecognized insertion mode . Aborting program" ); } infile.close(); } private void die( String errMsg ) { System.out.println( errMsg ); System.exit(0); } // ########################## Y O U W R I T E / F I L L I N T H E S E M E T H O D S ######################## // OF COURSE MORE EFFICIENT TO KEEP INTERNAL COUNTER BUT YOU COMPUTE IT DYNAMICALLY WITH A TRAVERSAL LOOP @SuppressWarnings("unchecked") public int size() { return 0; } // TACK A NEW NODE ONTO THE FRONT OF THE LIST public void insertAtFront(T data) { // BASE CASE WRITTEN FOR YOU CDLL_Node newNode = new CDLL_Node( data,null,null); if (head==null) { newNode.next=newNode; newNode.prev=newNode; head = newNode; return; } // CAN YOU WRITE THE CODE BELOW IN LESS LINES OF CODE ? CDLL_Node old1st=head,oldlast=head.prev; head=newNode; newNode.next=old1st; newNode.prev=oldlast; old1st.prev=newNode; oldlast.next=newNode; } // TACK ON NEW NODE AT END OF LIST @SuppressWarnings("unchecked") public void insertAtTail(T data) { // CALL INSERT AT FRONT AND THEN MOVE THE HEAD TO THE RIGHT PLACE } // RETURN TRUE/FALSE THIS LIST CONTAINS A NODE WITH DATA EQUALS KEY public boolean contains( T key ) { return false; } // RETURN REF TO THE FIRST NODE (SEARCH CLOCKWISE FOLLOWING next) THAT CONTAINS THIS KEY. DO -NOT- RETURN REF TO KEY ISIDE NODE // RETURN NULL IF NOT FOUND public CDLL_Node search( T key ) { return null; } // RETURNS CONATENATION OF CLOCKWISE TRAVERSAL @SuppressWarnings("unchecked") public String toString() { return ""; } } // END CDLL_LIST CLASS // PRIVATE TO CODE OUTSIDE FILE. BUT PUBLIC TO CODE INSIDE class CDLL_Node { T data; // DONT DEFINE MEMBERS AS PUBLIC OR PRIVATE CDLL_Node prev, next; // CDLL_Node() { this( null, null, null ); } CDLL_Node(T data) { this( data, null, null); } CDLL_Node(T data, CDLL_Node prev, CDLL_Node next) { this.data=data; this.prev=prev; this.next=next; } public String toString() // TOSTRING MUST BE PUBLIC { return ""+data; } } //END NODE CLASS 

Do not modify : 

import java.io.*; import java.util.*; public class CDLL_ListTester { @SuppressWarnings("unchecked") public static void main( String args[] ) throws Exception { String[] keys = { "charlie", "golf", "bravo", "dragonfly" }; // WE WILL SEARCH THE LISTS FOR THESE CDLL_List cdll_1 = new CDLL_List( args[0], "atFront" ); System.out.format( "cdll_1 loaded from %s (insertAtFront) size=%d %s ",args[0],cdll_1.size(),cdll_1 ); for ( String key : keys ) System.out.format( "cdll_1.contains(%s) returns %b ", key,cdll_1.contains(key) ); CDLL_List cdll_2 = new CDLL_List( args[0], "atTail" ); System.out.format( "cdll_2 loaded from %s (insertAtTail) size=%d %s ",args[0],cdll_2.size(),cdll_2 ); for ( String key : keys ) System.out.format( "cdll_2.contains(%s) returns %b ", key,cdll_2.contains(key) ); } // END MAIN } // END CDLL_ListTester CLASS

2021 SPRING CS 445 PROJECT #4: CIRCULAR DOUBLY LINKED LISTS AND THEIR BASIC OPERATIONS head CDLL_List CDLL_Node "abel" P T data ZMXH "baker" V "hotel" co "golf" "charlie" "foxtrot" "delta" // PRIVATE CODE OUTSIDE FILE. BUT PUBLIC TO CODE INSIDE class CDLL_Node { T data; // DONT DEFINE MEMBERS AS PUBLIC OR PRIVATE CDLL_Node prev, next; // CDLL_Node() { this( null, null, null ); } COLL_Node(T data) { this( data, null, null); } COLL_Node(T data, CDLL_Node prev, CDLL_Node next) { this.data-data; this.prev=prev; this.next-next; } public String toString() // TOSTRING MUST BE PUBLIC { return ""+data; } } //END NODE CLASS "echo" public class CDLL_List { private CDLL_Node head; private int count=0; public CDLL_List( String fileName, String insertionMode ) public int size) public void insertAtFront (T data) public void insertAtTail(T data) public boolean contains ( T key ) public CDLL_Node search( T key ) public String toString() } You are given the following files which comprise a partial implementation of a Linked List + a Tester o the CDLL List.java class FILL IN THE METHODS AT BOTTOM o the CDLL ListTester.java class DO NOT MODIFY You are given the following input file used by Tester o names.txt This week's lecture topic is Circular Doubly Linked Lists and their fundamental operations. You are given a partially written List class file and you must sill in the methods at the bottom, similar to what you did in Lab#3. You must fill in the incomplete methods at the bottom of the CDLL_Linked List class such that it executes correctly with the Tester. As usual your output must match the expected output indicated by the screen shots. WRITE AND TEST ONE METHOD AT A TIME IN THIS ORDER 1. insertAtFront(): as you write it print the data of each node as you insert it. This will verify you are not hung in an infinite 2. size(): once you are sure your insertAtFront() is at least creating new nodes and not infinite looping, traverse the list CLOCKWISE (following the next pointer ) and count the nodes. 3. toString(): once your size works, your InsertAtFront() is probably correct so now you should write your to String using the size() code as a template. Instead of incrementing a counter as the visitation operation, you tack that Node's data onto your string. (SEE OUTPUT SCREENSHOT). 4. search(): it's just the Same traversal as size() but a different visitation operation ( .equals() ). 5. contains(): just return the success/failure of search() 6. insertAtTail(): use your insertAtFront as a starting point. ON. Command Prompt $ java CDLL_ListTester names.txt cdil_1 loaded from names.txt (insertAtFront) size=8 charliehotelalphagolfdeltaechozebrabravo cdll_1. contains (charlie) returns true cdll_1. contains (golf) returns true cd11_1.contains (bravo) returns true cdll_1. contains (dragonfly) returns false cdll_2 loaded from names.txt (insertAtTail) size=8 bravozebraechodeltagolfalphahotelcharlie cdll_1. contains (charlie) returns true