LINKED LIST ASSIGNMENT, READ CAREFULLY (GIVEN CODE IS AT THE BOTTOM)

You are given three files Main.Java, Student.Java, LinkedList.java. Student is completed for you and is only used to test the LinkedList with an object (we will pass in Student for the generic parameter of the list). Your mission is to implement LinkedList.java, but I highly recommend you do this in a piecewise fashion as outlined in the //TODO s in Main.java (This assignment is easy if you do it piecewise and traumatic if you don't). You can go down this description of the TODO's for a few additional hints. You can try to pass the test cases as you go through (they should be in order I think but sometimes the order gets scrambled when I create the test cases and there is no easy way to unscramble, so just be aware of that). Each test case includes the code of how I made it so you can try to do it in main if you are not passing a test case for some reason for further investigatio

For this assignment you can assume that each student in the list is unique (for all of the tests I do not add any duplicate students, we will deal with this case later, it's slightly more code but nothing too crazy)

TODO 1: Implement the private inner class Node in LinkedList

You will find this at the bottom of LinkedList. This should be very straightforward. Note that the Node's data is a type T (generic) and that generic type is part of the outer class LinkedList, which is why Node doesn't need the parameter itself. This implementation should be very straight forward.

//TODO 2: Make a new LinkedList with the generic parameter of Student

The constructor for LinkedList is implemented for you, you can look at it-- what does it initialize the list to?\

//TODO 3: Define 5 Students, remember to invoke the constructor using the new command, make them all have different ID's

This is very straight forward, but make them all have different ID's because that is how we tell if two students are equal

//TODO 4: Implement addToFront and getLength in Linked List Add some of the students to the list using addToFront print out the length run your program and make sure it equals the number of students before continuing

If I have a list head->Student A->null and I addToFront(B) my list will be head->Student B->Student A->null

with a length of 2. Of course we have not implemented toString yet so you won't be able to check, in main, if the list is correct, but you can check if it's the right length which will ensure your getLength() function is working.

//TODO 5: Implement toString in Node and LinkedList. The Node toString should just print out the data field of the node. Note that toString is implemented in Student, so this should be easy-- creating a string out of the data should invoke the toString in Student (i.e. if I have a student instance named A saying String x= ""+A; will invoke A's toString. Alternatively you can explicitly call A.toString() from within Node (but understand why ""+A will work). Then implement toString in LinkedList. If one prints out a list with two students (Eugenio and Daniqua), with Danica added to the front first and Eugenio added second our list should look as follows

head->name: Eugenio id: 700555555->name: Daniqua id: 700444444->null

note the spaces. Print out your list to ensure it works.

LinkedList's toString will rely on Node's toString as described in the todo. Remember that Node's toString will rely on T's toString since we're printing out the data. Since T is an object, it HAS to have a toString (it's guaranteed to have a toString). You can look at Student's toString to see what it does (prints out the student name and id-- pretty simple). If the list is empty you should have the following head->null; otherwise it should print out all the Node's values in order

head->name: Eugenio id: 700555555->name: Daniqua id: 700444444->null

//TODO 6: Implement addToEnd in LinkedList and then add another Student, but this time to the end, and print out the length (should be one more) and the list to ensure it added the student to the end.

With addToEnd you need first identify the last node-- since we don't have a tail reference this involves looping through the linkedlist (with a WHILE loop) and when you get to the last node, making its next reference the node you are adding. Now that print should work you can print out the list to ensure it is correct (along with length to ensure it's the correct length).\

//TODO 7: Implement removeFromFront in LinkedList and print out what is returned, should be the first student in the list. Then print out the length (should be one less than what you had previously). Finally print out the length to ensure it is correct using getLength

Think about what removing from head will do, namely if I have

head->name: Eugenio id: 700555555->name: Daniqua id: 700444444->null

and I removeFromFront, Eugenio should be returned and the list should look as follows

head->name: Daniqua id: 700444444->null

//TODO 8: Implement removeFromEnd in LinkedList and print out what is returned. it should be the student who was at the end of the list, furthermore print out the list and the length to ensure it has the right students in it. Note that this function is a bit more involved, you may need to use 3 references as you iterate through the list (think about why?). Make sure your algorithm will work with a list that is of length 1, length 2, length 3, and some big length like 5

Remove from end takes the second to last node and jumps the last node. Think about why you might want to use 3 references in sequence to do this, if I have

head->name: Eugenio id: 700555555->name: Daniqua id: 700444444->null

When the front student reference is pointing to null we know we're at the end of the list. The middle reference will point to Daniqua, which we need to return. Finally, the back reference will point to Eugenio, that's the one we want to change its link (or next as it's called in the LinkedList class) to jump Daniqua so that our list will be (you could alternatively just make Eugenio's next reference null)

head->name: Eugenio id: 700555555->null

//TODO 9: Implement removeTarget in LinkedList. This should rely on the the Type T's equals. Remember our T, though it's generic, is guaranteed to have this function because it's guaranteed to be an object. In Student's case two students are equal if their student ID's are equal. Test removeTarget with a student in the list to ensure that removeTarget returns the right value when you test (and removes the actual student from the list when appropriate).

very similar to TODO number 8, you again can implement this using three references

BELOW ARE GIVEN CODE TO MODIFY:

MAIN:

import java.util.*; class Main { public static void main(String[] args) { //TODO 1: Implement the private inner class Node in LinkedList

//TODO 2: Here in Main, Make a new LinkedList with the generic parameter of Student. Note that the constuctor in LinkedList is implemented for you. What does the constructor initialize the list to? LinkedList myList= new LinkedList(); //TODO 3: Define 5 Students, remember to invoke the constructor using the new command, make them all have different ID's

//TODO 4: Implement addToFront and getLength in Linked List Add some of the students to the list using addToFront //print out the length run your program and make sure it equals the number of students before continuing

//TODO 5: Implement toString in Node and LinkedList. The Node toString should just print out the data field of the node. Note that toString is implemented in Student, so this should be easy-- creating a string out of the data should invoke the toString in Student (i.e. if I have a student instance named A saying String x= ""+A; will invoke A's toString. Alternatively you can explicitly call A.toString() from within Node (but understand why ""+A will work). Then implement toString in LinkedList. If one prints out a list with two students (Eugenio and Daniqua), with Danica added to the front first and Eugenio added second our list should look as follows head->name: Eugenio id: 700555555->name: Daniqua id: 700444444->null note the spaces. Print out your list to ensure it works. //TODO 6: Implement addToEnd in LinkedList and then add another Student, but this time to the end, and print out the length (should be one more) and the list to ensure it added the student to the end. //TODO 7: Implement removeFromFront in LinkedList and print out what is returned, should be the first student in the list. Then print out the length (should be one less than what you had previously). Finally print out the length to ensure it is correct using getLength //TODO 8: Implement removeFromEnd in LinkedList and print out what is returned. it should be the student who was at the end of the list, furthermore print out the list and the length to ensure it has the right students in it. Note that this function is a bit more involved, you may need to use 3 references as you iterate through the list (think about why?). Make sure your algorithm will work with a list that is of length 1, length 2, length 3, and some big length like 5 //TODO 9: Implement removeTarget in LinkedList. This should rely on the the Type T's equals. Remember our T, though it's generic, is guaranteed to have this function because it's guaranteed to be an object. In Student's case two students are equal if their student ID's are equal. Test removeTarget with a student in the list to ensure that removeTarget returns the right value when you test (and removes the actual student from the list when appropriate). } }

STUDENT.JAVA:

public final class Student { private int schoolID; private String name;

public Student(String namePassed,int schoolIDPassed) { schoolID= schoolIDPassed; name= namePassed; }

public int getSchoolID() { return schoolID; }

public void setSchoolID(int schoolIDPassed) { schoolID=schoolIDPassed; }

public String getName() { return name; }

public void setName(String namePassed) { name=namePassed; }

public boolean equals(Object toCompare) { Student temp= (Student) toCompare; return(temp.getSchoolID()==schoolID); } public String toString() { String toReturn="name: "+name+" id: "+schoolID; return (toReturn); }

}

LINKEDLIST.JAVA

public class LinkedList { //MUST IMPLEMENT ALL FUNCTIONS private Node head; public LinkedList() { head=null; } public int getLength() { Node current=head; int count=0; while(current!=null) { count++; current=current.getnext(); } return count; return 0; } public void addToFront(T toAdd) { } public void addToEnd(T toAdd) { } public T removeFromFront() { return null; } public T removeFromEnd() { return null; } public boolean removeTarget(T toRemove) { return true; } public String toString() { return ""; } private class Node { private T data; private Node next; Node(T dataPassed, Node nextPassed) { data= dataPassed; next=nextPassed; } public void setdata(T dataPassed) { data=dataPassed; } public T getdata() { return data; } public Node getnext() { return next; } public void setnext(Node passed) { next=passed; } } }