Question

Add your own method (or use one or more of the existing methods) to insert the following set of numbers (1, 5, 19, 7, 23, 17, 2) in a linked list (use one function call per number, and preserve the order of insertion). Once inserted print the linked list such that the output displays the numbers in reverse order. (2, 17, 23, 7, 19, 5, 1)

package linkedlist_app;
//-------class with main()-------------------
public class LinkedList_App {
   public static void main(String[] args) {
       linkedList myLL = new linkedList();
       System.out.println("----------------------------------");
       //check for problems: myLL.delete('A');
       myLL.print();
       myLL.insert_at_begining('A');
       myLL.insert_after('X', 'A');
       myLL.insert_at_end('E');
       myLL.print();
       myLL.delete('A');
       myLL.print();
       System.out.println("----------------------------------");
       System.out.println("-- Free ALL Nodes ----------------");
       myLL.freeAll(); myLL.print();
       System.out.println("----------------------------------");
       System.out.println("--Insert at begining: A, B, C ----");
       myLL.insert_at_begining('A');
       myLL.insert_at_begining('B');
       myLL.insert_at_begining('C');
       myLL.print();
   }
}
//--------aNode class---------------------------------------------
class aNode {
   char data;
   aNode next;
   aNode(char mydata) { // Constructor
       data = mydata;
       next = null;
   }
}
//------linkedList class-----------------------------------------------
class linkedList {
    aNode head; // Head of the linked list
    aNode tail; //*** Tail of the linked list
    int size;
    linkedList() { // Constructor
       head = null;// head point to null
       tail=null;//***tail also must point to null
       size =0;
    }
    //-----------------------------------------------------
    public void insert_at_begining(char value) {
       aNode newNode = new aNode(value); // create aNew node
       if(isEmpty()){//***if the node is inserted in empty node then head and tail are same
           tail=newNode;
       }
       newNode.next = head;
       head = newNode;
       size++;
    }
    //-----------------------------------------------------
    public void insert_at_end(char value) {
       aNode newNode = new aNode(value); // create aNew node
           if (isEmpty()) {
               insert_at_begining(value); //**reuse the code already written
           }else{ //**no need to traverse the last node since reference of last node is in tail
               tail.next=newNode;
               tail=newNode;
               size++;
           }
       }
       //-----------------------------------------------------
       public void insert_after(char value, char searchValue) {
           if (isEmpty()) {
               System.out.println("Linked List is empty, no way to insert " + value + " after " + searchValue);
               return;//***for simplicity of the code return the control here
               //***it eliminates complicated nested loop
           }
          
           //find the node with searchValue
            aNode ptr;
            boolean found = false;
            ptr = head;
            while (ptr != null && found == false) {
                if (ptr.data == searchValue) {
                    found = true;
                } else {
                    ptr = ptr.next;
                }
            }
           
            if (ptr == null) {
                System.out.println("Did not find " + searchValue + "Nothing Inserted");
                return;//***for simplicity of the code return the control here
                //***it eliminates complicated nested loop
            }
           
           aNode newNode = new aNode(value); // create aNew node
           newNode.next = ptr.next;
           ptr.next = newNode; //add the node after the searchValue
           if(newNode.next==null)//***it is the last node
               tail=newNode; //***point tail to the last node
           size++;
              
          
       }
       //-----------------------------------------------------
       // Delete the first node with the value
       public void delete(char deleteValue) {
           if (isEmpty()) {
               System.out.println("Linked List is empty, nothing to delete");
               return;//***for simplicity of the code return the control here
                //***it eliminates complicated nested loop
           }
            aNode deletePtr = head; // create a reference to head
            if (head.data == deleteValue && head==tail) { //***only one node in list
                head = head.next; // remove the head and
                tail=tail.next; //tail
                deletePtr = null; // make the node available for garbage collection.
                size--;
                return;//***for simplicity of the code return the control here
                //***it eliminates complicated nested loop
            }
            if(head.data==deleteValue){ //***first node to be deleted
                head = head.next; // remove the head
                deletePtr = null; // make the node available for garbage collection.
                size--;
                return;//***for simplicity of the code return the control here
                //***it eliminates complicated nested loop
            }
           aNode prevPtr;
           deletePtr = prevPtr = head;
           boolean found = false; //find the value to be deleted
           while (deletePtr != null && found == false) {
               if (deletePtr.data == deleteValue) {
                   found = true;
                   prevPtr.next = deletePtr.next;
                   if(deletePtr.next==null)//***last node is deleted
                       tail=prevPtr;
                   deletePtr = null; // make deletePtr available to garbage collection
                   size--;
               } else {
                   prevPtr = deletePtr;
                   deletePtr = deletePtr.next;
               }
           }
           if (found == false) {
               System.out.println("Not able to find/delete " + deleteValue + " in the Linked List");
           }       
          
       }
       //-----------------------------------------------------
       public boolean isEmpty() {
           return head==null;//***single line can work to check whether linked list is empty or not
       }
       //-----------------------------------------------------
       public void print() {
           aNode ptr;
           ptr = head;
           System.out.print("Head--> ");
           while (ptr != null) {
               System.out.print(ptr.data + " --> ");
              ptr = ptr.next;
           }
           System.out.println("NULL");
       }
       //-----------------------------------------------------
       public int getSize() {
           return(size);
       }
       //-----------------------------------------------------
       public void freeAll() {
           aNode freePtr = head;
           while(head != null) {
               head = head.next; // the next two lines are unnecessary, but are included for
               // illustration of how memory is freed up
               // freePtr = null;
               // make the node available for garbage collector
               freePtr = head; // now let the freePtr to the new head
           }
           head = null;
           size = 0;
       }
}
//##############################################
//NOTE:- Changes made in the optimised code shown as *** in the comment line

Answer 1

Here is the completed code for this problem. There is no need to add any new methods as we can use the existing ones to solve this. I have only changed the main method, so that the numbers to be added are added to the beginning of the list each time using insert_at_begining() method, and just simply printed using print() method so that the numbers will be printed in reverse. Note that I have changed the data type of data field of node from char to int since we are dealing with numbers here. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// LinkedList_App.java

//-------class with main()-------------------

public class LinkedList_App {

      public static void main(String[] args) {

            // creating a linked list

            linkedList myLL = new linkedList();

            // creating an array contains the numbers to be added

            int numbers[] = { 1, 5, 19, 7, 23, 17, 2 };

            // looping and adding each number in the array to the list

            for (int i = 0; i < numbers.length; i++) {

                  // adding to the beginning of the list, so that we can print the

                  // elements in reverse order

                  myLL.insert_at_begining(numbers[i]);

            }

            // now simply printing the list, the numbers will be displayed in

            // reverse order.

            myLL.print();

      }

}

// --------aNode class---------------------------------------------

class aNode {

      int data;

      aNode next;

      aNode(int mydata) { // Constructor

            data = mydata;

            next = null;

      }

}

// ------linkedList class-----------------------------------------------

class linkedList {

      aNode head; // Head of the linked list

      aNode tail; // *** Tail of the linked list

      int size;

      linkedList() { // Constructor

            head = null;// head point to null

            tail = null;// ***tail also must point to null

            size = 0;

      }

      // -----------------------------------------------------

      public void insert_at_begining(int value) {

            aNode newNode = new aNode(value); // create aNew node

            if (isEmpty()) {// ***if the node is inserted in empty node then head

                                    // and tail are same

                  tail = newNode;

            }

            newNode.next = head;

            head = newNode;

            size++;

      }

      // -----------------------------------------------------

      public void insert_at_end(int value) {

            aNode newNode = new aNode(value); // create aNew node

            if (isEmpty()) {

                  insert_at_begining(value); // **reuse the code already written

            } else { // **no need to traverse the last node since reference of last

                              // node is in tail

                  tail.next = newNode;

                  tail = newNode;

                  size++;

            }

      }

      // -----------------------------------------------------

      public void insert_after(int value, int searchValue) {

            if (isEmpty()) {

                  System.out.println("Linked List is empty, no way to insert "

                              + value + " after " + searchValue);

                  return;// ***for simplicity of the code return the control here

                  // ***it eliminates complicated nested loop

            }

            // find the node with searchValue

            aNode ptr;

            boolean found = false;

            ptr = head;

            while (ptr != null && found == false) {

                  if (ptr.data == searchValue) {

                        found = true;

                  } else {

                        ptr = ptr.next;

                  }

            }

            if (ptr == null) {

                  System.out.println("Did not find " + searchValue

                              + "Nothing Inserted");

                  return;// ***for simplicity of the code return the control here

                  // ***it eliminates complicated nested loop

            }

            aNode newNode = new aNode(value); // create aNew node

            newNode.next = ptr.next;

            ptr.next = newNode; // add the node after the searchValue

            if (newNode.next == null)// ***it is the last node

                  tail = newNode; // ***point tail to the last node

            size++;

      }

      // -----------------------------------------------------

      // Delete the first node with the value

      public void delete(int deleteValue) {

            if (isEmpty()) {

                  System.out.println("Linked List is empty, nothing to delete");

                  return;// ***for simplicity of the code return the control here

                  // ***it eliminates complicated nested loop

            }

            aNode deletePtr = head; // create a reference to head

            if (head.data == deleteValue && head == tail) { // ***only one node in

                                                                                     // list

                  head = head.next; // remove the head and

                  tail = tail.next; // tail

                  deletePtr = null; // make the node available for garbage collection.

                  size--;

                  return;// ***for simplicity of the code return the control here

                  // ***it eliminates complicated nested loop

            }

            if (head.data == deleteValue) { // ***first node to be deleted

                  head = head.next; // remove the head

                  deletePtr = null; // make the node available for garbage collection.

                  size--;

                  return;// ***for simplicity of the code return the control here

                  // ***it eliminates complicated nested loop

            }

            aNode prevPtr;

            deletePtr = prevPtr = head;

            boolean found = false; // find the value to be deleted

            while (deletePtr != null && found == false) {

                  if (deletePtr.data == deleteValue) {

                        found = true;

                        prevPtr.next = deletePtr.next;

                        if (deletePtr.next == null)// ***last node is deleted

                              tail = prevPtr;

                        deletePtr = null; // make deletePtr available to garbage

                                                       // collection

                        size--;

                  } else {

                        prevPtr = deletePtr;

                        deletePtr = deletePtr.next;

                  }

            }

            if (found == false) {

                  System.out.println("Not able to find/delete " + deleteValue

                              + " in the Linked List");

            }

      }

      // -----------------------------------------------------

      public boolean isEmpty() {

            return head == null;// ***single line can work to check whether linked

                                           // list is empty or not

      }

      // -----------------------------------------------------

      public void print() {

            aNode ptr;

            ptr = head;

            System.out.print("Head--> ");

            while (ptr != null) {

                  System.out.print(ptr.data + " --> ");

                  ptr = ptr.next;

            }

            System.out.println("NULL");

      }

      // -----------------------------------------------------

      public int getSize() {

            return (size);

      }

      // -----------------------------------------------------

      public void freeAll() {

            aNode freePtr = head;

            while (head != null) {

                  head = head.next; // the next two lines are unnecessary, but are

                                                 // included for

                  // illustration of how memory is freed up

                  // freePtr = null;

                  // make the node available for garbage collector

                  freePtr = head; // now let the freePtr to the new head

            }

            head = null;

            size = 0;

      }

}

/*OUTPUT*/

Head--> 2 --> 17 --> 23 --> 7 --> 19 --> 5 --> 1 --> NULL