Question

In order to practice on Linked Lists, you will implement one from scratch which will allow you to examine how they work and explore their capabilities and limitations. You will build a doubly-circular linked list. In doubly linked lists, each node in the list has a pointer to the next node and the previous node. In circular linked lists, the tail node’s next pointer refers to the head and the head node’s previous pointer refers to the tail rather than null. For this linked list, you will not explicitly define a tail pointer; however, you should see that you can reach the tail simply by following the head’s previous pointer. For this homework, we will model navigating through a show catelog called ShowCat and base our system’s behaviors on behaviors we see in similar existing catelog based services. A user might browse through a catelog moving back and forth between shows in a catelog. If the user scrolls far enough, the catelog returns back to the first show in the catelog. You should see that this catelog behavior closely resembles the list behavior described above. To track which show the user has currently selected in the catelog, your list will also track the ”current” show which you will change 2 using simple forward and backward controls. A framework for this project has been provided to you. Your implementation will run inside of the UnitTests.java class that you implement. All of your implementation will go inside of the Catelog.java class. The extension, as well as an implementation example, takes place in the class defined by ShowCat.java. In order to compile and test your work, compile and run UnitTests, or you can run the example and extension by compiling and running ShowCat.

Base Functions This section gives a general explanation of the requirements for each function. public boolean addToBack(String show) This function is responsible for placing a new show into a catelog. It places this show at the tail of the list. Note that you do not have a tail pointer for this list, but because it is circular and doubly-linked, the head can give quick access to the tail. If this show is already in the list, then return false. Any invalid inputs or failures must return false. This function must return true if the show is successfully added. Adding the first element to an empty list should set current to the head. If the list is non-empty, current must and can only refer to an element in the list or null. public boolean addToFront(String show) This function is responsible for placing a new show in your a catelog. It places this show at the front (1st element) of the list. If this show is already in the list, then return false. Any invalid inputs or failures must return false. This function must return true if the show is successfully added to the list. Adding the first element to an empty list should set the current to the head. current must and can only refer to an element in the list or null. public boolean removeShow(String show) This function attempts to remove a show by name from the linked list if the show exists in the list. If the show does not exist in the list or there are any other errors, this function must return false. If this function is successful in removing the specified show, it must return true. Reminder, if you are removing the “current” show, the current show must step forward. If you are removing the only show in the list, then both the head and current nodes must be null. public void clear() This function must remove all elements from the list and sets the current node to null. public boolean isEmpty() This function must indicate whether or not the list is empty. It must return false if the list is empty

Existing code:

public class Catelog {

private Node head;
private Node current; //the show you are currently looking at

//A newly created linked list is completely and all members are null
public Catelog() {
head = null;
current = null;
}

public boolean addToBack(String show) {
return false;
}

public boolean addToFront(String show) {
return false;
}

public boolean removeShow(String show) {
return false;
}

public void clear() {

}

public boolean isEmpty() {
return true;
}

public String getCurrentShow() {
return null;
}

public String stepForward() {
return null;
}

public String stepBackward() {
return null;
}

/* ---------------------------- HELPERS -------------------------------
This section contians helper functions that support the class. Some
may only be internally used while others may be publicly exposed for
general usage like toString and checkIntegrity.
For example, you might add a search function here.
---------------------------------------------------------------------*/
/// This method is inherited from the Object base class and allows
/// a user of this class to serialize the state which might be used for
/// printing. If the list is not internally consistent, then this
/// method might generate an exception.
public String toString() {
if(head == null) {
return null;
}

String s = new String("[");

Node it = head;
s += it.data.show + "<=>";
it = it.next;

while(it != head) {
s += it.data.show + "<=>";
it = it.next;
}

s += "], current:";
if(current != null) {
s += current.data.show;
} else {
s += "null";
}
  
return s;
}

/// This method performs a number of tests to validate the integrity
/// of the linked list
/// @returns true if the list is internally consistent; otherwise,
/// returns false.
public boolean checkIntegrity() {
// sanity check
if(head == null) {
// if list empty, but current is set, integrity compromised
if(current != null) {
return false;
}   
// otherwise, empty list has full integrity
return true;
}

// if the head has any illegal pointers, integrity compromised
if(head.next == null || head.prev == null) {
return false;
}

// check that the rest of the list has the correct references.
// already checked head, move to second element
Node it = head.next;
while(it != head) { // when we circle back to head, done
if(it.next.prev != it) {
return false;
}
if(it.prev.next != it) {
return false;
}
it = it.next;
}

// at this point, current should be set. If it is not, the
// integrity is compromised
if(current == null) {
return false;
}

return true;
}

public class Data {
public final String show;

// Parameterized constructor requires the show be assigned at creation
// @param show the show to store in this instance
public Data(String show) {
this.show = show;
}

// Equivalent to a less than operator. Evaluates whether or not the
// information stored inside this instance is 'less than' the parameter
  
public boolean lessThan(Data data) {
assert(data != null);

if(show.compareTo(data.show) < 0) {
return true;
}
return false;
}

// Equivalent to a less than or equal to operator. Evaluates whether
// or not the information stored inside this instance is
// 'less than or equal to' the parameter
// @param data a data instance to compare to this instance.
// @returns true if this instance is 'less than or equal to' the
// parameter; otherwise, false.
public boolean lessThanOrEqual(Data data) {
assert(data != null);

if(show.compareTo(data.show) <= 0) {
return true;
}
return false;
}

// Comparison function
// @param show a show to compare to the show stored in this instance
// @returns -1 if this instance preceeds the parameter, 1 if this
// instance follows the parameter, 0 if the two are equivalent
public int compareTo(String show) {
assert(show != null);

return this.show.compareTo(show);
}
}

public class ShowCat {

//runs the example as well as launches the extension.
public static void main(String[] args){

exampleRun();
extensionInterface();
}

/**
* provides a non interactive example of what it should look like when your list is operating as a Netflix scroller
*/
private static void exampleRun(){

String[] shows = ShowFactory.getShows();

Catelog cat = new Catelog();

cat.addToFront(shows[0]); // Bojack Horseman
//System.out.println(cat);
cat.addToBack(shows[1]); // That 70's Show
//System.out.println(cat);
cat.addToFront(shows[2]); // Orange is the New Black
//System.out.println(cat);
cat.addToBack(shows[3]); // LetterKenny
//System.out.println(cat);
report(cat); // should not be empty, current should be Bojack

cat.stepForward();
report(cat); // should not be empty, current should be That 70's show

cat.removeShow(shows[3]); // LetterKenny
cat.addToBack(shows[4]); // Lucifer
report(cat); // should not be empty, current should be That 70's Show

cat.stepBackward();
report(cat); // should be non-empty, current should be Bojack

cat.clear();
report(cat); // should be empty

}

// This method allows you to demo the extension. To run the program
// with a specific sort implementation, uncomment the sort you want
// to run, recompile, and run.
private static void extensionInterface(){
String[] shows = ShowFactory.getShows();

Catelog cat = new Catelog();
for(int i = 0; i < shows.length; i++) {
cat.addToFront(shows[i]);
}
  
//cat.sort(Catelog.SortType.SELECTION);
//cat.sort(Catelog.SortType.BUBBLE);
//cat.sort(Catelog.SortType.INSERTION);
//cat.sort(Catelog.SortType.QUICK);
//cat.sort(Catelog.SortType.MERGE);

report(cat);
}
  
private static void report(Catelog cat) {
boolean value;
// print the catelog contents
System.out.println(cat);

// print out whether the catelog is empty
value = cat.isEmpty();
if(value) {
System.out.println("Catelog is empty");
} else {
System.out.println("Catelog is not empty");
}

// integrity check
value = cat.checkIntegrity();
if(value) {
System.out.println("Catelog passed integrity check");
} else {
System.out.println("Catelog failed integrity check");
}
System.out.println();
}
}

public class ShowFactory {

// Simple factory method that builds an array of strings that can be
// used as data in the ShowCat program
public static String[] getShows() {
String[] shows = new String[10];

shows[0] = new String("Bojack Horseman");
shows[1] = new String("That 70's Show");
shows[2] = new String("Orange is the New Black");
shows[3] = new String("LetterKenny");
shows[4] = new String("Lucifer");
shows[5] = new String("The Office");
shows[6] = new String("Futurama");
shows[7] = new String("Rick and Morty");
shows[8] = new String("Friends");
shows[9] = new String("Seinfeld");

return shows;
}
}

Answer 1

ShowCat.java

=============================

public class ShowCat {
   //runs the example as well as launches the extension.
   public static void main(String[] args){

       exampleRun();
       extensionInterface();
   }

   /**
   * provides a non interactive example of what it should look like when your list is operating as a Netflix scroller
   */
   private static void exampleRun(){

       String[] shows = ShowFactory.getShows();
  
       Catelog cat = new Catelog();
  
       cat.addToFront(shows[0]); // Bojack Horseman
       //System.out.println(cat);
       cat.addToBack(shows[1]); // That 70's Show
       //System.out.println(cat);
       cat.addToFront(shows[2]); // Orange is the New Black
       //System.out.println(cat);
       cat.addToBack(shows[3]); // LetterKenny
       //System.out.println(cat);
       report(cat); // should not be empty, current should be Bojack
  
       cat.stepForward();
       report(cat); // should not be empty, current should be That 70's show
  
       cat.removeShow(shows[3]); // LetterKenny
       cat.addToBack(shows[4]); // Lucifer
       report(cat); // should not be empty, current should be That 70's Show
  
       cat.stepBackward();
       report(cat); // should be non-empty, current should be Bojack
  
       cat.clear();
       report(cat); // should be empty

   }

   // This method allows you to demo the extension. To run the program
   // with a specific sort implementation, uncomment the sort you want
   // to run, recompile, and run.
   private static void extensionInterface(){
       String[] shows = ShowFactory.getShows();

       Catelog cat = new Catelog();
       for(int i = 0; i < shows.length; i++) {
           cat.addToFront(shows[i]);
       }
      
       //cat.sort(Catelog.SortType.SELECTION);
       //cat.sort(Catelog.SortType.BUBBLE);
       //cat.sort(Catelog.SortType.INSERTION);
       //cat.sort(Catelog.SortType.QUICK);
       //cat.sort(Catelog.SortType.MERGE);
  
       report(cat);
   }
  
   private static void report(Catelog cat) {
       boolean value;
       // print the catelog contents
       System.out.println(cat);

       // print out whether the catelog is empty
       value = cat.isEmpty();
       if(value) {
           System.out.println("Catelog is empty");
       } else {
           System.out.println("Catelog is not empty");
       }

       // integrity check
       value = cat.checkIntegrity();
       if(value) {
           System.out.println("Catelog passed integrity check");
       } else {
           System.out.println("Catelog failed integrity check");
       }
       System.out.println();
   }
}

===============================

ShowFactory.java

===============================

public class ShowFactory {

   // Simple factory method that builds an array of strings that can be
   // used as data in the ShowCat program
   public static String[] getShows() {
       String[] shows = new String[10];
  
       shows[0] = new String("Bojack Horseman");
       shows[1] = new String("That 70's Show");
       shows[2] = new String("Orange is the New Black");
       shows[3] = new String("LetterKenny");
       shows[4] = new String("Lucifer");
       shows[5] = new String("The Office");
       shows[6] = new String("Futurama");
       shows[7] = new String("Rick and Morty");
       shows[8] = new String("Friends");
       shows[9] = new String("Seinfeld");
  
       return shows;
   }
}

=========================

Data.java

=========================

public class Data {

   public final String show;

   // Parameterized constructor requires the show be assigned at creation
   // @param show the show to store in this instance
   public Data(String show) {
       this.show = show;
   }

   // Equivalent to a less than operator. Evaluates whether or not the
   // information stored inside this instance is 'less than' the parameter
   public boolean lessThan(Data data) {
       assert(data != null);
      
       if(show.compareTo(data.show) < 0) {
           return true;
       }
       return false;
   }

   // Equivalent to a less than or equal to operator. Evaluates whether
   // or not the information stored inside this instance is
   // 'less than or equal to' the parameter
   // @param data a data instance to compare to this instance.
   // @returns true if this instance is 'less than or equal to' the
   // parameter; otherwise, false.
   public boolean lessThanOrEqual(Data data) {
       assert(data != null);

       if(show.compareTo(data.show) <= 0) {
           return true;
       }
       return false;
   }

   // Comparison function
   // @param show a show to compare to the show stored in this instance
   // @returns -1 if this instance preceeds the parameter, 1 if this
   // instance follows the parameter, 0 if the two are equivalent
   public int compareTo(String show) {
       assert(show != null);

       return this.show.compareTo(show);
   }
}

=========================

Node.java

=========================

public class Node {
  
   // data field
   protected Data data;
   protected Node next;
   protected Node prev;
  
   // constructor
   public Node(String show){
       // create new show as data
       this.data = new Data(show);
       // circular node should have next and prev referred to self
       this.next = this;
       this.prev = this;
   }
}

============================

Catelog.java

============================

public class Catelog {
  
   private Node head;
   private Node current; //the show you are currently looking at

   //A newly created linked list is completely and all members are null
   public Catelog() {
       head = null;
       current = null;
   }

   public boolean addToBack(String show) {
       if(show == null) {
           return false;
       }
       // create a new node to add in Catelog
       Node node = new Node(show);
       // if list is empty than assign new node to head
       if(head == null) {
           head = current = node;
           return true;
       }
       else {
           // check if show is already in Catelog
           // check if head contains show
           if(head.data.compareTo(show) == 0) {
               return false;
           }
           // check remaining nodes
           Node itr = head.next;
           while(itr != head) {
               if(itr.data.compareTo(show) == 0) {
                   return false;
               }
               itr = itr.next;
           }
          
           // node is not in list
           // add node before head as tail
           head.prev.next = node;
           node.prev = head.prev;
           head.prev = node;
           node.next = head;
           return true;
       }
   }

   public boolean addToFront(String show) {
       // in circular list its same as adding node to front as
       // adding node to back
       // except for the head position
       // add node to back of head
       boolean isAdded = addToBack(show);
       if(isAdded) {
           // move head to one position back
           head = head.prev;
       }
       return isAdded;
   }

   public boolean removeShow(String show) {
       if(show == null) {
           return false;
       }
       else {
           // look for show in list
           // if list is empty return false
           if(head == null) {
               return false;
           }
           else {
               // check if head is needed to be removed
               if(head.data.compareTo(show) == 0) {
                   // remove head
                   // check if head is only node
                   if(head.next == head) {
                       head = null;
                       current = null;
                       return true;
                   }
                   Node itr = head.next;
                   // if current node is being removed move current node to next
                   if(current == head) {
                       current = current.next;
                   }
                   head.prev.next = head.next;
                   head.next.prev = head.prev;
                   head.next = null;
                   head.prev = null;
                   head = itr;
                   return true;
               }
               else {
                   Node itr = head.next;
                   // find and remove show from remaining nodes
                   while(itr != head) {
                       if(itr.data.compareTo(show) == 0) {
                           // remove itr from list
                           // if current node is being removed move current node to next
                           if(current == itr) {
                               current = current.next;
                           }
                           itr.prev.next = itr.next;
                           itr.next.prev = itr.prev;
                           itr.next = null;
                           itr.prev = null;
                           itr = null;
                           return true;
                       }
                       itr = itr.next;
                   }
                   // node with given show not present in catelog
                   return false;
               }
           }
       }
   }

   public void clear() {
       // remove all nodes
       head = null;
       current = null;
   }

   public boolean isEmpty() {
       return head == null;
   }

   public String getCurrentShow() {
       return current.data.show;
   }

   public String stepForward() {
       current = current.next;
       return current.data.show;
   }

   public String stepBackward() {
       current = current.prev;
       return current.data.show;
   }

   /* ---------------------------- HELPERS -------------------------------
   This section contians helper functions that support the class. Some
   may only be internally used while others may be publicly exposed for
   general usage like toString and checkIntegrity.
   For example, you might add a search function here.
   ---------------------------------------------------------------------*/
   /// This method is inherited from the Object base class and allows
   /// a user of this class to serialize the state which might be used for
   /// printing. If the list is not internally consistent, then this
   /// method might generate an exception.
   public String toString() {
       if(head == null) {
           return null;
       }
       String s = new String("[");
       Node it = head;
       s += it.data.show + "<=>";
       it = it.next;
       while(it != head) {
           s += it.data.show + "<=>";
           it = it.next;
       }
       s += "], current:";
       if(current != null) {
           s += current.data.show;
       } else {
           s += "null";
       }
       return s;
   }

   /// This method performs a number of tests to validate the integrity
   /// of the linked list
   /// @returns true if the list is internally consistent; otherwise,
   /// returns false.
   public boolean checkIntegrity() {
       // sanity check
       if(head == null) {
           // if list empty, but current is set, integrity compromised
           if(current != null) {
               return false;
           }
           // otherwise, empty list has full integrity
           return true;
       }
  
       // if the head has any illegal pointers, integrity compromised
       if(head.next == null || head.prev == null) {
           return false;
       }
  
       // check that the rest of the list has the correct references.
       // already checked head, move to second element
       Node it = head.next;
       while(it != head) { // when we circle back to head, done
           if(it.next.prev != it) {
               return false;
           }
           if(it.prev.next != it) {
               return false;
           }
           it = it.next;
       }

       // at this point, current should be set. If it is not, the
       // integrity is compromised
       if(current == null) {
           return false;
       }
       return true;
   }
}