In order to practice on Linked Lists, you will implement onefrom scratch which will allow you to examine how they work andexplore their capabilities and limitations. You will build adoubly-circular linked list. In doubly linked lists, each node inthe list has a pointer to the next node and the previous node. Incircular linked lists, the tail node’s next pointer refers to thehead and the head node’s previous pointer refers to the tail ratherthan null. For this linked list, you will not explicitly define atail pointer; however, you should see that you can reach the tailsimply by following the head’s previous pointer. For this homework,we will model navigating through a show catelog called ShowCat andbase our system’s behaviors on behaviors we see in similar existingcatelog based services. A user might browse through a catelogmoving back and forth between shows in a catelog. If the userscrolls far enough, the catelog returns back to the first show inthe catelog. You should see that this catelog behavior closelyresembles the list behavior described above. To track which showthe user has currently selected in the catelog, your list will alsotrack the ”current” show which you will change 2 using simpleforward and backward controls. A framework for this project hasbeen provided to you. Your implementation will run inside of theUnitTests.java class that you implement. All of your implementationwill go inside of the Catelog.java class. The extension, as well asan implementation example, takes place in the class defined byShowCat.java. In order to compile and test your work, compile andrun UnitTests, or you can run the example and extension bycompiling and running ShowCat.

Base Functions This section gives a general explanation of therequirements for each function. public boolean addToBack(Stringshow) This function is responsible for placing a new show into acatelog. It places this show at the tail of the list. Note that youdo not have a tail pointer for this list, but because it iscircular and doubly-linked, the head can give quick access to thetail. If this show is already in the list, then return false. Anyinvalid inputs or failures must return false. This function mustreturn true if the show is successfully added. Adding the firstelement to an empty list should set current to the head. If thelist is non-empty, current must and can only refer to an element inthe list or null. public boolean addToFront(String show) Thisfunction is responsible for placing a new show in your a catelog.It places this show at the front (1st element) of the list. If thisshow is already in the list, then return false. Any invalid inputsor failures must return false. This function must return true ifthe show is successfully added to the list. Adding the firstelement 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 toremove a show by name from the linked list if the show exists inthe list. If the show does not exist in the list or there are anyother errors, this function must return false. If this function issuccessful in removing the specified show, it must return true.Reminder, if you are removing the “current” show, the current showmust step forward. If you are removing the only show in the list,then both the head and current nodes must be null. public voidclear() This function must remove all elements from the list andsets the current node to null. public boolean isEmpty() Thisfunction must indicate whether or not the list is empty. It mustreturn 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 arenull
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 exposedfor
general usage like toString and checkIntegrity.
For example, you might add a search function here.
---------------------------------------------------------------------*/
/// This method is inherited from the Object base class andallows
/// a user of this class to serialize the state which might be usedfor
/// printing. If the list is not internally consistent, thenthis
/// 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 theintegrity
/// 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, integritycompromised
if(head.next == null || head.prev == null) {
return false;
}

// check that the rest of the list has the correctreferences.
// 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 atcreation
// @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 notthe
// information stored inside this instance is 'less than' theparameter
  
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. Evaluateswhether
// 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 thisinstance
// @returns -1 if this instance preceeds the parameter, 1 ifthis
// instance follows the parameter, 0 if the two areequivalent
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 likewhen 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'sshow

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

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 theprogram
// with a specific sort implementation, uncomment the sort youwant
// 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 thatcan 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;
}
}