Question

Based on a Node class;

Use Java to implement the OrderedList class which represents an ordered singly linked list that cannot contain any duplicates. Note that items in the OrderedList are always kept in descending order. Complete the class with the following methods.

• Default constructor
  Create an empty list i.e., head is null.
• boolean insert(int data)
  Insert the given data into the list at the proper location in the list. If the insertion is successful, the function returns true; otherwise, returns false.
• boolean delete(int data)
  Delete the node that contains the given data from the list. If the deletion is successful, the function returns true; otherwise, returns false.
• int find(int data)
  Search and return the index to the node that contains the data. Note that the index starts from 0. If it is not found, return -1.
• int count()
  Count and return the number of nodes in the list
• String toString()
  Return the string representation of this List where all data in the list are enclosed in square brackets [ ].

Then write the program that accepts a sequence of commands and print out the number of successful insertions, the number of successful deletions, the number of successful searches (through the “find” command), the number of items remaining in the list after executing all commands and the final contents of the list.

There are 3 commands which are “insert”, “delete” and “find”.

Input

Line 1: The number of transactions m on the list, where 1  m 200.

Line 2 to m+1: A string command (“insert”, “delete”, “find”) followed by an integer n (separated by a space).

• • “insert” means insert n into the list
• • “delete” means delete n from the list
• • “find” means find n in the list

Output

Line 1: Display 4 integers (each number is separated by a space) which are:

• • the number of successful insertions,
• • the number of successful deletions,
• • the number of items found (from the command “find”), and
• • the number of items remaining in the list

Line 2: The final contents of the list

Sample Input	Sample Output
3 insert 1 delete 5 find 2	1 0 0 1 [ 1 ]
8 find 10 insert 3 insert 2 insert 1 delete 4 delete 3 insert 1 find 2	3 1 1 2 [ 2 1 ]

Answer 1

Here I have provided the solution. Ihave taken the attributes of the Node class randomly as val and next. You can configure it as required. The rest of it is the same. Also I have used the Scanner class for input.

import java.util.Scanner;

class Node
{
    public int val;
    public Node next;

    Node(int i)
    {
        this.val = i;
        this.next = null;
    }
}


public class OrderedList
{
    public Node head;
    OrderedList(){
        this.head = null;
    }

    public boolean insert(int data)
    {
        Node newNode = new Node(data);
        if(head == null)    head = newNode;
        else{
            Node trav = head;
            while(trav.next!=null){
                if(trav.val == data)    return false;
                trav = trav.next;
            }
            if(trav.val == data)    return false;
            trav.next = newNode;
        }
        return true;
    }

    public boolean delete(int data)
    {
        if(head.val == data)    head = head.next;
        else{
            Node trav = head, prev = null;
            while(trav != null && trav.val != data){
                prev = trav;
                trav = trav.next;
            }
            if(trav == null)    return false;
            prev.next = trav.next;
        }
        return true;
    }

    public int find(int data)
    {
        Node trav = head;
        int i = 0;
        while(trav!=null){
            if(trav.val == data)    return i;
            trav = trav.next;
            i++;
        }
        return -1;
    }

    public int count()
    {
        Node trav = head;
        int i = 0;
        while(trav !=null){
            trav = trav.next;
            i++;
        }
        return i;
    }

    public String toString()
    {
        String output = "[";
        Node trav = head;
        while(trav!=null){
            output += " "+trav.val;
            trav = trav.next;
        }
        output += " ]";
        return output;
    }

    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        OrderedList ol = new OrderedList();
        String command[];
        int n = sc.nextInt();
        int succ_insert = 0, succ_delete = 0, succ_find = 0, num_items = 0;
        while(n >= 0)
        {
            command = sc.nextLine().split(" ");
            if(command[0].equals("insert")){
                if(ol.insert(Integer.parseInt(command[1]))) {succ_insert++; num_items++;}
            }
            else if (command[0].equals("delete")){
                if(ol.delete(Integer.parseInt(command[1]))) {succ_delete++; num_items--;}
            }
            else if(command[0].equals("find"))
            {
                if(ol.find(Integer.parseInt(command[1])) > -1)  succ_find++;
            }
            n--;
        }
        System.out.println(succ_insert+" "+succ_delete+" "+succ_find+" "+num_items);
        System.out.println(ol.toString());
    }
}