Question

1) Modify all methods that have used count, especially rewrite length method by traversing the list and counting no. of elements.

import java.util.*;
import java.io.*;

public class Qup3 implements xxxxxlist {// implements interface
   // xxxxxlnk class variables
   // head is a pointer to beginning of rlinked list
   private node head;
   // no. of elements in the list
   // private int count;

// xxxxxlnk class constructor
   Qup3() {
       head = null;
       count = 0;
   } // end Dersop3 class constructor

   PrintStream prt = System.out;

   // class node
   private class node {
       // class node variables
       int data;
       node rlink;

       // class node constructor
       node(int x) {
           data = x;
           rlink = null;
       } // class node constructor
   } // end class node

   // isEmpty() returns true if list is empty, false otherwise.
   public boolean isEmpty() {
       return (count == 0);
   } // end isEmpty

   // length() returns number of list elements.
   public int length() {
       return count;
   } // end length

   // insert x at position p, for successful insertion:
   // list should not be full and 1 <= p <= count+1
   public int insert(int x, int p) {
       int i;
       prt.printf("\n Insert %4d at position %2d:", x, p);
      
       if (p < 1 || p > ( count + 1) ) {
           return 0;
       }
       node tmp = new node(x);
       // p == 1 Inserts x to front of list,
       // is a special case where head changes
       if (p == 1) {
           tmp.rlink = head;
           head = tmp;
       } else {// traverse the list till element before p
           node current = head;
           // Find node before p
           for (i = 2; i < p; i++, current = current.rlink)
               ; // end for
           // insert node after cur node
           tmp.rlink = current.rlink;
           current.rlink = tmp;
       }
       count++;
       return 1; // successful insertion
   } // end insert

   // delete x at position p, for successful deletion:
   // list should not be empty and 1 <= p <= count
   public int delete(int p) {
       prt.printf("\n Delete element at position %2d:", p);
       if (isEmpty() || p < 1 || p > length())
           return 0; // invalid deletion
       int count = length();
       node tmp = head;
       // p == 1 deletes front of list.
       // This is a special case where head changes
       if (p == 1) { // Delete Front of List
           head = head.rlink;
           tmp.rlink = null;
           } else { // Find node before p
           node current = head;
           for (int i = 2; i < p; i++, current = current.rlink; ) ;// end for
           // Delete node after current node
           tmp = current.rlink;
           current.rlink = tmp.rlink;
           tmp.rlink = null; // delete tmp;
           }
       count--;
       return 1; // successful deletion
   } // end delete

   // sequential serach for x in the list
   // if successful return position of x in the
   // list otherwise return 0;
   public int searchx(int x) {
       prt.printf("\n search for %4d:", x);
       // complete the rest
       //.........
       return 0;
   } // end searchx

   // print list elements formatted
   public void printlist() {
       prt.print("\n List contents: ");
       for (node current = head; current != null; current = current.rlink)
           prt.printf("%4d, ", current.data);
      
       // end for
   } // end printlist

   public static void main(String args[]) throws Exception {
       int j, m, k, p, x, s;
       try {
           // open input file
           Scanner inf = new Scanner(System.in);
           // Create a List of type Integer of size n
           Qup3 lst = new Qup3();

           // read no. of elements to insert
           m = inf.nextInt();
           System.out.printf("\n\tInsert %2d elements in the list.", m);
           for (j = 1; j <= m; j++) {
               x = inf.nextInt(); // read x
               p = inf.nextInt(); // read position

               s = lst.insert(x, p); // insert x at position p
               if (s == 1)
                   System.out.printf(" Successful insertion.");
               else
                   System.out.printf(" %2d is invalid position for insertion.", p);
           } // end for
           lst.printlist(); // print linked list elements
           // read no. of elements to search in the list
           m = inf.nextInt();
           System.out.printf("\n\tSearch for %d elements in the list.", m);
           for (j = 1; j <= m; j++) {
               x = inf.nextInt(); // read x
               p = lst.searchx(x); // search for x
               if (p > 0)
                   System.out.printf(" found at position %d.", p);
               else
                   System.out.printf(" is not found.");
           } // end for
               // read no. of positions to delete from list
           m = inf.nextInt();
           System.out.printf("\n\tDelete %d elements from list.", m);
           for (j = 1; j <= m; j++) {
               p = inf.nextInt(); // read position
               s = lst.delete(p); // delete position p
               if (s == 1)
                   System.out.printf(" Successful deletion.");
               else
                   System.out.printf(" %2d is invalid position for deletion.", p);
           } // end for
           lst.printlist(); // print array elements
           inf.close(); // close input file
      
       } catch (Exception e) {
           System.out.print("\nException " + e + "\n");
       }
   } // end main
} // end class xxxxxlnk

Answer 1

import java.util.*;
import java.io.*;

public class Qup3 implements xxxxxlist {// implements interface
   // xxxxxlnk class variables
   // head is a pointer to beginning of rlinked list
   private node head;
  
   // no. of elements in the list
   // private int count;

   // xxxxxlnk class constructor
   Qup3() {
       head = null;
       //count = 0;
   } // end Dersop3 class constructor

   PrintStream prt = System.out;

   // class node
   private class node {
       // class node variables
       int data;
       node rlink;

       // class node constructor
       node(int x) {
           data = x;
           rlink = null;
       } // class node constructor
   } // end class node

   // isEmpty() returns true if list is empty, false otherwise.
   public boolean isEmpty() {
//return (count == 0);
       return (head == null);
   } // end isEmpty

   // length() returns number of list elements.
   public int length() {
       //return count;
      
       node curr = head; // set curr to head
       int l = 0; // sel l to 0
      
       // loop over the list
       while(curr != null)
       {
           l++; // increment l
           curr = curr.rlink; // move to the next node in the list
       }
      
       return l;
   } // end length

// insert x at position p, for successful insertion:
// list should not be full and 1 <= p <= count+1
public int insert(int x, int p) {
       int i;
       prt.printf("\n Insert %4d at position %2d:", x, p);
  
//if (p < 1 || p > ( count + 1) ) {
       if(p < 1 || p > length()+1){
           return 0;
       }

       node tmp = new node(x);
       // p == 1 Inserts x to front of list,
       // is a special case where head changes
       if (p == 1) {
           tmp.rlink = head;
           head = tmp;
       }else
       {
           // traverse the list till element before p
           node current = head;
          
           // Find node before p
           for (i = 2; i < p; i++, current = current.rlink); // end for

       // insert node after cur node
tmp.rlink = current.rlink;
current.rlink = tmp;
}
     
// count++;
       return 1; // successful insertion
} // end insert

// delete x at position p, for successful deletion:
   // list should not be empty and 1 <= p <= count
   public int delete(int p) {

       prt.printf("\n Delete element at position %2d:", p);
       if (isEmpty() || p < 1 || p > length())
           return 0; // invalid deletion

       //int count = length();
       node tmp = head;
      
       // p == 1 deletes front of list.
       // This is a special case where head changes
       if (p == 1)
       {
           // Delete Front of List
           head = head.rlink;
           tmp.rlink = null;
}
       else
       {
           // Find node before p
           node current = head;

           for (int i = 2; i < p; i++, current = current.rlink; ) ;// end for

           // Delete node after current node
           tmp = current.rlink;
           current.rlink = tmp.rlink;
           tmp.rlink = null; // delete tmp;
}

       //count--;
       return 1; // successful deletion
} // end delete

  
   // sequential serach for x in the list
   // if successful return position of x in the
   // list otherwise return 0;
   public int searchx(int x) {

       prt.printf("\n search for %4d:", x);
       node curr = head; // set curr to head
       int pos = 0; // set current position to 0
      
       // loop over the list
       while(curr != null)
       {
           pos++; // increment pos by 1
           if(curr.data == x) // x found, return pos
               return pos;
           curr = curr.rlink;
       }
      
       return 0; // x not found
   } // end searchx

// print list elements formatted
   public void printlist() {
       prt.print("\n List contents: ");
       for (node current = head; current != null; current = current.rlink)
           prt.printf("%4d, ", current.data);
  
       // end for
   } // end printlist

   public static void main(String args[]) throws Exception {
       int j, m, k, p, x, s;
      
       try {
           // open input file
           Scanner inf = new Scanner(System.in);
           // Create a List of type Integer of size n
           Qup3 lst = new Qup3();

           // read no. of elements to insert
           m = inf.nextInt();
           System.out.printf("\n\tInsert %2d elements in the list.", m);
           for (j = 1; j <= m; j++) {
               x = inf.nextInt(); // read x
               p = inf.nextInt(); // read position

               s = lst.insert(x, p); // insert x at position p
               if (s == 1)
                   System.out.printf(" Successful insertion.");
               else
                   System.out.printf(" %2d is invalid position for insertion.", p);
           } // end for

           lst.printlist(); // print linked list elements
           // read no. of elements to search in the list
           m = inf.nextInt();
           System.out.printf("\n\tSearch for %d elements in the list.", m);
           for (j = 1; j <= m; j++) {
               x = inf.nextInt(); // read x
               p = lst.searchx(x); // search for x
               if (p > 0)
                   System.out.printf(" found at position %d.", p);
               else
                   System.out.printf(" is not found.");
           } // end for
  
           // read no. of positions to delete from list
           m = inf.nextInt();
           System.out.printf("\n\tDelete %d elements from list.", m);
           for (j = 1; j <= m; j++) {
               p = inf.nextInt(); // read position
               s = lst.delete(p); // delete position p
               if (s == 1)
                   System.out.printf(" Successful deletion.");
               else
                   System.out.printf(" %2d is invalid position for deletion.", p);
           } // end for

           lst.printlist(); // print array elements
           inf.close(); // close input file
  
       } catch (Exception e) {
           System.out.print("\nException " + e + "\n");
       }
} // end main
} // end class xxxxxlnk