For this assignment you will write code to construct an ordered linked list of LinkedString objects; the class LinkedString is supplied as is a program that constructs a linked list of LinkedString objects in which objects are added at the end of the current linked list. Your task will be to modify the addString() method so that the linked list is in order lexicographically.

• addString() is the only supplied code that you will modify.

An object of the class LinkedString is a node with two instance variables:

• A string (which might contain white space):
  • So it must be entered using Scanners .nextLine(), not .next().
• A reference variable for a LinkedString object.

Your task is to modify OrderedLinkedStringManagers addString() method. As currently written, this method constructs a linked list of LinkedString objects; the objects added to the linked list are added at the end of the list so when the list is printed, the strings are displayed in the order in which they were entered into the list. Your modified addString() method will enter the strings in lexicographical order into the linked list so that when the list is printed, it will be in lexicographical order.

Make no changes to anything in OrderedLinkedStringManager except the body of addString(); dont change its signature, just its body so that it constructs an ordered linked list.

The suggested order:

• First: Add a string to an empty linked list.
  • Add a string and print the list.
• Second: Add code to addString() that will add a string before the current first string in the list.
  • While your final code must handle strings with white space in them, when testing make things simple on yourself. For example, you can type in integers like 1, 2, 3,,9 , reading them as strings. This makes it easy to see if the linked list that you are constructing is ordered or not since the ASCII character codes for 19 are in increasing order.
    • Note: Dont go to two-digit numbers as that will throw off the ordering.
  • To check this code, you might first enter 3; this will be inserted as the first string in your linked list. Then enter 2 and print the list. If 2 and 3 are printed in order, theres a good chance your code for entering a string before the first string currently in the list works. To check further, now add 1; you should now get 1, 2, 3 printed in order.
• Third: Once you can enter a string into an empty list and before the first string currently in the list, its time to work on the code to insert a string inside the list or at the end of the list. To do this, you will probably want to set up current and previous pointers to allow you to traverse the list. And what are you looking for:
  • Since you want to insert the new string in its correct position in the ordered linked list, you need to keep searching until one of two things occurs:
    • The string in the node pointed to by current is larger (string-wise) than the string to be inserted. If this is true, then the new string needs to be inserted into the linked list between the nodes pointed to by previous and current.
    • The string pointed to by current is the last string in the list. This means that the new string will become the new last string in the list.

// OrderedLinkedStringManager.java // Manages an ordered linked list of LinkedString objects. // NOTE: As currently written, items are added at end of list. // Programmer needs to modify addString() so that list is // maintained in order lexicographically. import java.util.Scanner;

public class OrderedLinkedStringManager {

public static void main(String[] args) { // Set up Scanner object for keyboard input. Scanner keyboard = new Scanner(System.in); // Set up head to hold link to first node in ordered linked list. LinkedString head = null; // Display menu and allow user to: // 1] Add student to ordered linked list. // 2] Print current contents of linked list. // 0] Exit menu. int response = 1; while(response != 0) { // Print menu. System.out.println(" Menu options:"); System.out.println("1] Add string to list."); System.out.println("2] Print current contents of list."); System.out.println("0] Exit menu."); System.out.print("Menu option: "); response = keyboard.nextInt(); // Clear buffer pointer. keyboard.nextLine(); switch(response) { // Add string to list. case(1): // enter string into list. System.out.print("String: "); String str = keyboard.nextLine(); head = addString(head, str); break; // Print current contents of list. case(2): { System.out.println(" Current contents of list:"); printList(head); break; } // Exit menu. case(0): { System.out.println(" Exiting menu!"); break; } // Incorrect menu option. default: { System.out.println(" Invalid menu option!"); break; } } }

} // Method to add string to end of current linked list. public static LinkedString addString(LinkedString head, String str) { // Check if list is empty. if(head == null) { head = new LinkedString(str); return head; } // List is not empty; move to end of list. LinkedString current = head; while(current.getPtr() != null) { current = current.getPtr(); } // Current points to last node in list; add node after that node. current.setPtr(new LinkedString(str)); return head; } // Method to print current contents of linked list. public static void printList(LinkedString head) { // Check to see if list is empty. if(head == null) { System.out.println(" List is empty. "); return; } // List is not empty; print its contents. LinkedString current = head; int ctr = 1; while(current != null) { System.out.println("String #" + ctr + ": " + current.getStr()); current = current.getPtr(); ctr++; } } }

// LinkedString.java // Object holds a string and a pointer. public class LinkedString { // Constructor. public LinkedString(String st) { str = st; ptr = null; } // .get() methods. public String getStr() { return str; } public LinkedString getPtr() { return ptr; } // .set() methods. public void setStr(String st) { str = st; } public void setPtr(LinkedString pt) { ptr = pt; } // Instance variables. public String str; public LinkedString ptr; }