Lesson 8: Advanced Data Structures in Java

Activity 32: Creating a Custom Linked List in Java

Solution:

1. Create a class named, SimpleObjLinkedList.

   public class SimpleObjLinkedList {

2. Create a class named Node that represents each element in a Linked List. Each node will have an Object that it needs to hold, and it will have a reference to the next Node. The LinkedList class will have a reference to the head node and will be able to traverse to the next Node by using Node.getNext(). Head being the first element, we could traverse to the next element by moving next in the current Node. Like this, we could traverse till the last element of the list:

   static class Node {
   Object data;
   Node next;
   Node(Object d) {
   data = d;
   next = null;
   }
   Node getNext() {
   return next;
   }
   void setNext(Node node) {
   next = node;
   }
   Object getData() {
   return data;
   }
   }

3. Implement a toString() method to represent this object. Starting from the head Node, iterate all the nodes until the last node is found. On each iteration, construct a string representation of the object stored in each node:

   public String toString() {
   String delim = ",";
   StringBuffer stringBuf = new StringBuffer();
   if (head == null)
   return "LINKED LIST is empty";    
   Node currentNode = head;
   while (currentNode != null) {
   stringBuf.append(currentNode.getData());
   currentNode = currentNode.getNext();
   if (currentNode != null)
   stringBuf.append(delim);
   }
   return stringBuf.toString();
   }

4. Implement the add(Object item) method so that any item/object can be added into this List. Construct a new Node object by passing the newItem = new Node(item) Item. Starting at the head node, crawl to the end of the list. In the last node, set the next node as our newly created node (newItem). Increment the index:

   // appends the specified element to the end of this list.    
   public void add(Object element) {
   // create a new node
   Node newNode = new Node(element);
   //if head node is empty, create a new node and assign it to Head
   //increment index and return
   if (head == null) {
   head = newNode;
   return;
   }
   Node currentNode = head;
   // starting at the head node
   // move to last node
   while (currentNode.getNext() != null) {
   currentNode = currentNode.getNext();
   }
   // set the new node as next node of current
   currentNode.setNext(newNode);
   }

5. Implement get(Integer index) method to retrieve the item from the list based on the index. Index must not be less than 0. Write a logic to crawl to the specified index, identify the node, and return the value from the node.

   public Object get(int index) {
   // Implement the logic returns the element
   // at the specified position in this list.
   if (head == null || index < 0)
   return null;        
   if (index == 0){
   return head.getData();
   }    
   Node currentNode = head.getNext();
   for (int pos = 0; pos < index; pos++) {
   currentNode = currentNode.getNext();
   if (currentNode == null)
   return null;
   }
   return currentNode.getData();
   }

6. Implement the remove(Integer index) method to remove the item from the list based on the index. Write logic to crawl to the node before the specified index and identify the node. In this node, set the next as getNext(). Return true if the element was found and deleted. If the element was not found, return false:

   public boolean remove(int index) {
   if (index < 0)
   return false;
   if (index == 0)
   {
   head = null;
   return true;
   }
   
   Node currentNode = head;
   for (int pos = 0; pos < index-1; pos++) {
   if (currentNode.getNext() == null)
   return false;
   currentNode = currentNode.getNext();
   }    
   currentNode.setNext(currentNode.getNext().getNext());
   return true;
   }

7. Create a member attribute of type Node (pointing to the head node). Write a main method, create an object of SimpleObjLinkedList, and add five strings, one after the other ("INPUT-1", "INPUT-2", "INPUT-3", "INPUT-4","INPUT-5"), to it respectively. Print the SimpleObjLinkedList object. In the main method, get the item from the list using get(2) and print the value of the item retrieved. Also, remove the item from list remove(2) and print the value of the list. One element should have been deleted from the list:

   Node head;    
       public static void main(String[] args) {
           SimpleObjLinkedList list = new SimpleObjLinkedList();
           list.add("INPUT-1");
           list.add("INPUT-2");
           list.add("INPUT-3");
           list.add("INPUT-4");
           list.add("INPUT-5");
           System.out.println(list);
           System.out.println(list.get(2));
           list.remove(3);
           System.out.println(list);
   }
   }

   The output is as follows:

   [INPUT-1 ,INPUT-2 ,INPUT-3 ,INPUT-4 ,INPUT-5 ]
   INPUT-3
   [INPUT-1 ,INPUT-2 ,INPUT-3 ,INPUT-5 ]

Activity 33: Implementing the Methods in the BinarySearchTree Class to Find the Highest and Lowest Value in the BST

Solution:

1. Take the same class we used in the previous exercise: BinarySearchTree. Add a new method, int getLow(), to find the lowest value in the BST and return it. As we learned about the BST, the leftmost node will be the lowest of all the values. Iterate all of the left nodes until we reach an empty left node and get the value of its root:

       /**
        * As per BST, the left most node will be lowest of the all. iterate all the
        * left nodes until we reach empty left and get the value of it root.
        * @return int lowestValue
        */
       public int getLow() {
           Node current = parent;
           while (current.left != null) {
               current = current.left;
           }
           return current.data;
       }

2. Add a new method, int getHigh(), to find the highest value in the BST and return it. As we learned about the BST, the rightmost node will be the highest of all the values. Iterate all the right nodes until we reach an empty right node and get the value of its root:

       /**
        * As per BST, the right most node will be highest of the all. iterate all
        * the right nodes until we reach empty right and get the value of it root.
        * @return int highestValue
        */
       public int getHigh() {
           Node current = parent;
           while (current.right != null) {
               current = current.right;
           }
           return current.data;
       }

3. In the main method, construct a BST, add values to it, and then print the highest and lowest values by calling getLow() and getHigh():

   /**
        * Main program to demonstrate the BST functionality.
        * - Adding nodes
        * - finding High and low 
        * - Traversing left and right
        * @param args
        */
       public static void main(String args[]) {
           BinarySearchTree bst = new BinarySearchTree();
           // adding nodes into the BST
           bst.add(32);
           bst.add(50);
           bst.add(93);
           bst.add(3);
           bst.add(40);
           bst.add(17);
           bst.add(30);
           bst.add(38);
           bst.add(25);
           bst.add(78);
           bst.add(10);
           //printing lowest and highest value in BST
           System.out.println("Lowest value in BST :" + bst.getLow());
           System.out.println("Highest value in BST :" + bst.getHigh());
       }

   The output is as follows:

   Lowest value in BST :3
   Highest value in BST :93

Activity 34: Using an Enum to Hold College Department Details

Solution:

1. Create a DeptEnum enum using the enum keyword. Add two private attributes (String deptName and int deptNo) to hold the values to be kept in the enum. Override a constructor to take an acronym and deptNo and place it in the member variables. Add enum constants adhering to the constructor:

       public enum DeptEnum {
       BE("BACHELOR OF ENGINEERING", 1), BCOM("BACHELOR OF COMMERCE", 2), BSC("BACHELOR OF SCIENCE",
               3), BARCH("BACHELOR OF ARCHITECTURE", 4), DEFAULT("BACHELOR", 0);
   
       private String acronym;
       private int deptNo;
   
       DeptEnum(String accr, int deptNo) {
           this.accronym = acr;
           this.deptNo = deptNo;
       }

2. Add getter methods for deptName and deptNo:

       public String getAcronym() {
           return acronym;
       }
   
       public int getDeptNo() {
           return deptNo;
       }

3. Let's write a main method and sample program to demonstrate the use of enums:

   public static void main(String[] args) {
   // Fetching the Enum using Enum name as string
   DeptEnum env = DeptEnum.valueOf("BE");
   System.out.println(env.getAcronym() + " : " + env.getDeptNo());
   
   // Printing all the values of Enum
   for (DeptEnum e : DeptEnum.values()) {
   System.out.println(e.getAcronym() + " : " + e.getDeptNo());    }
   // Compare the two enums using the the equals() method or using //the == operator.                
   System.out.println(DeptEnum.BE == DeptEnum.valueOf("BE"));
   }
   }

4. Output:

   BACHELOR OF ENGINEERING : 1
   BACHELOR OF ENGINEERING : 1
   BACHELOR OF COMMERCE : 2
   BACHELOR OF SCIENCE : 3
   BACHELOR OF ARCHITECTURE : 4
   BACHELOR : 0
   True

Activity 35: Implementing Reverse Lookup

Solution:

1. Create an enum App, that declares constants BE, BCOM, BSC and BARC, along with their full forms and department numbers.

   public enum App {
       BE("BACHELOR OF ENGINEERING", 1), BCOM("BACHELOR OF COMMERCE", 2), BSC("BACHELOR OF SCIENCE", 3), BARCH("BACHELOR OF ARCHITECTURE", 4), DEFAULT("BACHELOR", 0);

2. Also declare two private variables accronym and deptNo.

       private String accronym;
       private int deptNo;

3. Create a parameterized constructor and assign the variables accronym and deptNo with values passed as arguments.

       App(String accr, int deptNo) {
           this.accronym = accr;
           this.deptNo = deptNo;
       }

4. Declare a public method getAccronym() that returns the variable accronym and a public method getDeptNo() that returns the variable deptNo.

       public String getAccronym() {
           return accronym;
       }
       public int getDeptNo() {
           return deptNo;
       }

5. Implement reverse look up that takes in the course name, and searches the corresponding acronym in the App enum.

       //reverse lookup 
       public static App get(String accr) {
           for (App e : App.values()) {
               if (e.getAccronym().equals(accr))
                   return e;
           }
           return App.DEFAULT;
       }

6. Implement the main method, and run the program.

       public static void main(String[] args) {
    
           // Fetching Enum with value of Enum (reverse lookup)
           App noEnum = App.get("BACHELOR OF SCIENCE");
           System.out.println(noEnum.accronym + " : " + noEnum.deptNo);
           // Fetching Enum with value of Enum (reverse lookup)
    
           System.out.println(App.get("BACHELOR OF SCIENCE").name());
       }
   }

   Your Output should be similar to:

   BACHELOR OF SCIENCE : 3
   BSC

Lesson 9: Exception Handling Activity 36: Handling Mistakes in Numeric User Input

Solution:

1. Right-click the src folder and select New | Class.

2. Create a class Adder, and then click OK.

3. Import the java.util.Scanner package:

   import java.util.Scanner;

4. Create a class named Adder:

   import java.util.Scanner;
   public class Adder {

5. In main() method, use the for loop to read values from the user:

      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          int total = 0;
          for (int i = 0; i < 3; i++) {
              System.out.print("Enter a whole number: ");

6. In the same loop, check if the valid value is entered. If the value is valid, add a try block to calculate the sum of three numbers.

              boolean isValid = false;
              while (!isValid) {
                  if (input.hasNext()) {
                      String line = input.nextLine();
                      try {
                          int newVal = Integer.parseInt(line);
                          isValid = true;
                          total += newVal;

7. The catch block should prompt the user to input valid numbers.

   } catch (NumberFormatException e) {
                          System.out.println("Please provide a valid whole number");
                      }
                  }
              }
          }

8. Print the sum:

   System.out.println("Total is " + total);
      }
   }

   Print the result to the console. Here is a sample output of a case with no errors:

   Enter a whole number: 10
   Enter a whole number: 11
   Enter a whole number: 12
   Total is 33

   And here is a sample output of a run with errors:

   Enter a whole number: 10
   Enter a whole number: hello
   Please provide a valid whole number
   11.1
   Please provide a valid whole number
   11
   Enter a whole number: 12
   Total is 33

Activity 37: Writing Custom Exceptions in Java

Solution:

1. Right-click the src folder and select New | Class.

2. Enter RollerCoasterWithAge as the class name, and then click OK.

3. Import the java.util.Scanner package:

   import java.util.Scanner;

4. Create an exception class, TooYoungException:

   class TooYoungException extends Exception {
      int age;
      String name;
      TooYoungException(int age, String name) {
          this.age = age;
          this.name = name;
      }
   }

5. In main(), create a loop that reads in the names of the visitors:

   public class RollerCoasterWithAge {
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
   
          while (true) {
              System.out.print("Enter name of visitor: ");
              String name = input.nextLine().trim();
              if (name.length() == 0) {
                  break;
              }

6. The try block, read the age of the visitors, throws TooYoungException if the age is below 15, prints the name of the visitor riding the Roller Coaster:

              try {
                  System.out.printf("Enter %s's age: ", name);
                  int age = input.nextInt();
                  input.nextLine();
                  if (age < 15) {
                      throw new TooYoungException(age, name);
                  }
   
                  System.out.printf("%s is riding the roller coaster.\n", name);

7. The catch block will display the message that is to be displayed for visitors below the age of 15:

              } catch (TooYoungException e) {
                  System.out.printf("%s is %d years old, which is too young to ride.\n", e.name, e.age);
              }
          }
      }
   }

Activity 38: Dealing with Multiple Exceptions in a Block

Solution:

1. Right-click the src folder and select New | Class.

2. Enter RollerCoasterWithAgeAndHeight as the class name, and then click OK.

3. Import the java.util.Scanner package:

   import java.util.Scanner;

4. Create an exception class, TooYoungException:

   class TooYoungException extends Exception {
      int age;
      String name;
      TooYoungException(int age, String name) {
          this.age = age;
          this.name = name;
      }
   }

5. Create an exception class, TooShortException:

   class TooShortException extends Exception {
      int height;
      String name;
      TooShortException(int height, String name) {
          this.height = height;
          this.name = name;
      }
   }

6. In main(), create a loop that reads in the names of the visitors:

   public class RollerCoasterWithAgeAndHeight {
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
   
          while (true) {
              System.out.print("Enter name of visitor: ");
              String name = input.nextLine().trim();
              if (name.length() == 0) {
                  break;
              }

7. The try block, read the age of the visitors, throws TooYoungException if the age is below 15, TooShortException if the height is below 130, and prints the name of the visitor riding the Roller Coaster:

              try {
                  System.out.printf("Enter %s's age: ", name);
                  int age = input.nextInt();
                  input.nextLine();
                  if (age < 15) {
                      throw new TooYoungException(age, name);
                  }
                  System.out.printf("Enter %s's height: ", name);
                  int height = input.nextInt();
                  input.nextLine();
                  if (height < 130) {
                      throw new TooShortException(height, name);
                  }
   
                  System.out.printf("%s is riding the roller coaster.\n", name);
              } 

8. The catch block will display the message that is to be displayed for visitors below the age of 15 or height below 130:

   catch (TooYoungException e) {
                  System.out.printf("%s is %d years old, which is too young to ride.\n", e.name, e.age);
              } catch (TooShortException e) {
                  System.out.printf("%s is %d cm tall, which is too short to ride.\n", e.name, e.height);
              }
          }
      }
   }

Activity 39: Working with Multiple Custom Exceptions

Solution:

1. Right-click the src folder and select New | Class.

2. Enter RollerCoasterWithAgeAndHeight as the class name, and then click OK.

3. Import the java.util.Scanner package:

   import java.util.Scanner;

4. Create an exception class, TooYoungException:

   class TooYoungException extends Exception {
      int age;
      String name;
      TooYoungException(int age, String name) {
          this.age = age;
          this.name = name;
      }
   }

5. Create an exception class, TooShortException

   class TooShortException extends Exception {
      int height;
      String name;
      TooShortException(int height, String name) {
          this.height = height;
          this.name = name;
      }
   }

6. In main(), create a loop that reads in the names of the visitors:

   public class Main {
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
   
          while (true) {
              System.out.print("Enter name of visitor: ");
              String name = input.nextLine().trim();
              if (name.length() == 0) {
                  break;
              }

7. The try block, read the age of the visitors, throws TooYoungException if the age is below 15, TooShortException if the height is below 130, and prints the name of the visitor riding the Roller Coaster:

              try {
                  System.out.printf("Enter %s's age: ", name);
                  int age = input.nextInt();
                  input.nextLine();
                  if (age < 15) {
                      throw new TooYoungException(age, name);
                  }
                  System.out.printf("Enter %s's height: ", name);
                  int height = input.nextInt();
                  input.nextLine();
                  if (height < 130) {
                      throw new TooShortException(height, name);
                  }
   
                  System.out.printf("%s is riding the roller coaster.\n", name);
              } 

8. Create a catch block for TooYoungException:

   catch (TooYoungException e) {
                  System.out.printf("%s is %d years old, which is too young to ride.\n", e.name, e.age);
              } 

9. Create a catch block for TooShortException:

   catch (TooShortException e) {
                  System.out.printf("%s is %d cm tall, which is too short to ride.\n", e.name, e.height);
              } 

10. Create a finally block that prints a message for escorting visitors off the premises:

    finally {
                   System.out.printf("Escorting %s outside the premises.\n", name);
               }
           }
       }
    }