Homework SourseLinked Lists NOTICE There are NO static variables allowed Th
Linked Lists
NOTICE: There are NO static variables allowed. The only class that a static method is allowed is in theTestDriver class. The only static method that you actually really need is main.
The purpose of this is to create your own linked list data structure and implement all the methods specified below to do list operations.
The following specifies the linked list class which you must implement. Only implement the methods listed below. Do NOT add any additional member variables.
class OrderedLinkedList
{
private class Node
{
// NOTE: The member variables are public so the methods
// of the OrderedLinkedList class have direct access to them
// NO setters and getters are needed – more efficient access.
public String payload;
public int keyValue;
public Node next;
// Explicit value constructor for the Node class
public Node(String payload, int value) { …. }
}
private Node first; // This is the only member variable allowed.
// You can NOT add any other member variables!!!
public OrderedLinkedList ( ) { … } // default constructor
public boolean empty( ) { … } // returns true if list is empty
public String getFirst( ) throws Exception { … }
// The first node is removed from the list and its payload is returned.
// An exception with a meaningful error message is thrown if the list is empty.
public String getLast( ) throws Exception { … }
// The last node is removed from the list and its payload is returned.
// An exception with a meaningful error message is thrown if the list is empty.
public void insert(String payload, int key) throws Exception { … }
// The insert method creates a new node, puts the input parameter values
// into the new node, and then inserts the node into the list in sorted order
// based on the keyValue. For example, if a list has 3 nodes with key values
// of 5, 10, and 15, insertion of a new node which has a key value of 12 would
// require that the new node was inserted after the node with key value of 10.
// If the key being inserted is already in the list, throw an Exception with a
// meaningful error string. Make sure that you test all possible cases for insertion.
public void remove(int key) throws Exception { … }
// Traverse the list, keeping track of where the precedessor for each node
// is located. When the value is found in some node in the list, make the
// predecessor node bypass the node which holds the value. If the key value
// is not found, throw an Exception that indicates the error has occurred.
public int listCount( ) { … } // Returns the number of nodes in the list.
public String getValue(int key) throws Exception { … }
// Traverse the list until you locate the requested key value. Return the
// payload from the node which has the requested key value. If the key value
// is not found, throw an Exception that indicates the error has occurred.
public String toString( ) { … }
// Override the toString method and create a string that contains the information
// from all the nodes currently in the list. The string should be constructed such
// that the data from each node will appear on a separate line. If the list is empty
// the returned string should indicate that the list was empty.
}
Implement all the methods of this class and write a test program which thoroughly tests all of the methods in this class. Carefully consider each method and what meaningful test cases are needed to fully test each method.Make sure to identify each test case in your test driver class with a comment. You can write your test program any way you like, but your program must thoroughly exercise your class. Running the test program one time must result in the successful execution of every test case. It can be interactive with the user, or just have some specific hardwired test cases. Make sure that the output generated by your test program clearly indicates what each of your test cases is doing and what the results are. By running your test program one time, you should be convinced that every method of your class is running correctly under all circumstances. Make sure to test all the exception cases!
Solution
Hi, Please find my code/implementation.
Please let me know in case of any issue.
########################
public class OrderedLinkedList
{
private class Node
{
// NOTE: The member variables are public so the methods
// of the OrderedLinkedList class have direct access to them
// NO setters and getters are needed – more efficient access.
public String payload;
public int keyValue;
public Node next;
// Explicit value constructor for the Node class
public Node(String payload, int value) {
this.payload = payload;
this.keyValue = value;
next = null;
}
}
private Node first; // This is the only member variable allowed.
// You can NOT add any other member variables!!!
// default constructor
public OrderedLinkedList ( ) {
first = null;
}
// returns true if list is empty
public boolean empty( ) {
return first == null;
}
// The first node is removed from the list and its payload is returned.
// An exception with a meaningful error message is thrown if the list is empty.
public String getFirst( ) throws Exception {
if(first == null)
throw new Exception(\"List is Empty\");
String payload = first.payload;
first = first.next; // removing first node
return payload;
}
// The last node is removed from the list and its payload is returned.
// An exception with a meaningful error message is thrown if the list is empty.
public String getLast( ) throws Exception {
if(first == null)
throw new Exception(\"List is Empty\");
String payload;
if(first.next == null){ // we have only one node
payload = first.payload;
first = null; // removed last element
}else{
Node temp = first;
while(temp.next.next != null){ // traverse till second last node
temp = temp.next;
}
payload = temp.next.payload; // setting last node null
temp.next = null;
}
return payload;
}
// The insert method creates a new node, puts the input parameter values
// into the new node, and then inserts the node into the list in sorted order
// based on the keyValue. For example, if a list has 3 nodes with key values
// of 5, 10, and 15, insertion of a new node which has a key value of 12 would
// require that the new node was inserted after the node with key value of 10.
// If the key being inserted is already in the list, throw an Exception with a
// meaningful error string. Make sure that you test all possible cases for insertion.
public void insert(String payload, int key) throws Exception {
// creating new node
Node newNode = new Node(payload, key);
if(first==null || first.keyValue > key){
newNode.next = first;
first = newNode;
}else{
Node temp = first;
Node prev = null;
while(temp != null && temp.keyValue < key){
prev = temp;
temp = temp.next;
}
if(temp != null && temp.keyValue == key)
throw new Exception(key+ \" is already in list\");
newNode.next = prev.next;
prev.next = newNode;
}
}
// Traverse the list, keeping track of where the precedessor for each node
// is located. When the value is found in some node in the list, make the
// predecessor node bypass the node which holds the value. If the key value
// is not found, throw an Exception that indicates the error has occurred.
public void remove(int key) throws Exception {
if(first == null)
throw new Exception(\"List is Empty\");
if(first.keyValue == key){
first= first.next;
return;
}
Node curr = first;
Node prev = null;
while(curr != null){
if(curr.keyValue == key)
break;
prev = curr;
curr = curr.next;
}
if(curr == null){
throw new Exception(key+ \" is not available in list\");
}
prev.next = curr.next;
}
// Returns the number of nodes in the list.
public int listCount( ) {
int count = 0;
Node temp = first;
while(temp !=null){
count++;
temp = temp.next;
}
return count;
}
// Traverse the list until you locate the requested key value. Return the
// payload from the node which has the requested key value. If the key value
// is not found, throw an Exception that indicates the error has occurred.
public String getValue(int key) throws Exception {
if(first == null)
throw new Exception(\"List is Empty\");
Node curr = first;
String payload = \"\";
while(curr != null){
if(curr.keyValue == key){
payload = curr.payload;
break;
}
curr = curr.next;
}
if(curr == null){
throw new Exception(key+ \" is not available in list\");
}
return payload;
}
// Override the toString method and create a string that contains the information
// from all the nodes currently in the list. The string should be constructed such
// that the data from each node will appear on a separate line. If the list is empty
// the returned string should indicate that the list was empty.
public String toString( ) {
String list = \"\";
Node temp = first;
while(temp != null){
list = list+ temp.keyValue+\", \"+temp.payload+\"\ \";
temp = temp.next;
}
return list;
}
}
public class TestOrderedList {
public static void main(String[] args) throws Exception {
OrderedLinkedList list = new OrderedLinkedList();
list.insert(\"abc\", 1);
list.insert(\"xyz\", 2);
list.insert(\"volve\",3);
list.insert(\"landon\", 4);
System.out.println(list.getFirst());
System.out.println(list.getLast());
System.out.println(list.getValue(3));
System.out.println(list.toString());
list.insert(\"bangalore\", 5);
//list.insert(\"abc\", 5);
}
}
#################
abc
landon
volve
2, xyz
3, volve
