Question

In Java

The following Java implementation of a class Node is given:

private class Node<Object>

{

Node()

{

this(null, null);

}

Node(Object d)

{

this(d, null);

}

Node(Object d, Node n)

{

data = d; next = n;

}

Object data; Node next;

}

Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a reference to the header node.

Using the class Node described above, write a MySingleLinkedList class in Java includes methods to:

int size() - return the size of the linked list.

void print() - print the linked list.

boolean contains(Object x) - test if a value x is contained in the linked list.

boolean add(Object x) - add a value x if it is not already contained in the linked list.

boolean remove(Object x) - remove a value x if it is contained in the linked list.

Very important!

In the implementation of the MySingleLinkedList class resolution it is not allowed to use the interface Iterator.

Answer 1

public class MySingleLinkedList<Object> {

    /* below definition of Node was given in question */
    private class Node<Object>
    {
        Node()
        {
            this(null, null);
        }
        Node(Object d)
        {
            this(d, null);
        }
        Node(Object d, Node n)
        {
            data = d; next = n;
        }

        Object data;
        Node next;
    }

    //declaration of only data member head
    Node<Object> head;

    /* Below is size function which will run till the end of list
    * How it will find end ?
    * end node next will be null
    *
    * So for each non null node encounter it will increment it's count value
    * and finally return it's node count value*/
    int size(){
        int count = 0;
        Node<Object> temp = head;
        while(temp != null){
            ++count;
            temp = temp.next;
        }
        return  count;
    }

    /*Below function will iterate through list
    * and print it's content untill end*/
    void print(){
        Node<Object> temp = head;
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    /* iterate untill end
    * and check whether data x is present or not
    * if present then set the flag (which represent found) to true
    *
    * finally return flag
    * Note if data x is not present then flag value remain false
    * and as a result false value will returned which represent data is not in list*/
    boolean contains(Object x){
        boolean flag = false;
        Node<Object> temp = head;
        while(temp != null){
            if(temp.data == x){
                flag = true;
            }
            temp = temp.next;
        }
        return  flag;
    }

    /*IMPORTANT NOTE
    * i am adding node to begining of list
    * as it was not mentioned where to add
    * why i adding to begining
    * bcoz it will reduce running time of code
    *
    * if x is already present then don't add it and return false
    * else
    * add it to begining and return true*/
    boolean add(Object x){
        if(this.contains(x)){
            return false;
        }
        else{
            Node<Object> temp = new Node<>(x,head);
            this.head = temp;
            return true;
        }
    }

    /*first we have to check whether data is present or not
    * bcoz if x is not present then there is no meaning of removing x
    *
    * so
    *
    * if present then remove it*/

    boolean remove(Object x){
        if(this.contains(x)){
            Node<Object> temp = head;
            Node<Object> temp2 = temp;
            while(temp.data != x){
                temp2 = temp;
                temp = temp.next;
            }
            if(temp.next == null){
                temp2.next = null;
            }
            else {
                temp2.next = temp.next;
            }
            return true;
        }
        return  false;
    }

    /* Main to test functionality
    * Please add or test code according to your need*/
    
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        /*adding data by running a loop */
        for(int i=0;i<10;++i){
            list.add(i);
        }
        System.out.println("Initially linked list contain : ");
        list.print();

        System.out.println("Size of linked list : " + list.size());

        if(list.contains(5)){
            System.out.println("our list contain 5");
        }
        else {
            System.out.println("our list does not contain 5");
        }

        if(list.remove(6)){
            System.out.println("6 was removed and updated list is :");
            list.print();
        }
        else {
            System.out.println("6 was not present in list");
        }
    }
}

//sample output

Run MySingleLinkedList "C:|Program Files\Java\jdkl.8.0 131\binljava" Initially linked list contain: 9 8 7 6 5 4 3 2 1 0 Size of linked list 10 our list contain 5 6 was removed and updated list is 987543210 Process finished with exit code 0