Question

Java

The List ADT has an interface and a linked list implementation whose source code is given at the bottom of this programming lab description. You are to modify the List ADT's source code by adding the method corresponding to the following UML:

+hasRepeats() : boolean

hasRepeats() returns true if the list has a value that occurs more than once in the list

hasRepeats() returns false if no value in the list occurs more than once in the list

For example, if a List ADT object is created and has the following values inserted into it:

1, 1, 3, 4, 5

hasRepeats() would return true because the value 1 occurs more than once in the list

but if a List ADT object is created and has the following values inserted into it:

1, 2, 3, 4, 5

hasRepeats() would return false because no value in the list occurs more than once in the list.

The List ADT has methods that may be useful in writing hasRepeats(). You may call any existing methods of the List ADT inside hasRepeats().

Once you have modified the List ADT to have the hasRepeats() method, write a Java Client program that makes a List ADT object, takes integers as input from a user, stores the integers in the List ADT object, and uses the hasRepeats() method to display whether the List ADT object contains repeated values.

The Client program will have a main() method and is the program that is run at the command line. You may give your Client program any name you like. The Client program should perform a loop, ask for input, and display output in the following way.

Input a list of integers: 1 1 3 4 5
The list has repeated values.
Do you want to continue (y/n):  y
  
Input a list of integers: 1 2 10 20 100 200
The list does not have repeated values.
Do you want to continue (y/n):  y
 
Input a list of integers:
The list does not have repeated values.
Do you want to continue (y/n):  y

Input a list of integers: 2
The list does not have repeated values.
Do you want to continue (y/n):  

public interface ListInterface
{
   public void add(T newEntry);
   public void add(int newPosition, T newEntry);
   public T remove(int givenPosition);
   public void clear();
   public T replace(int givenPosition, T newEntry);
   public T getEntry(int givenPosition);
   public T[] toArray();
   public boolean contains(T anEntry);
   public int getLength();
   public boolean isEmpty();
}

public class LList implements ListInterface
{
   private Node firstNode; // reference to the first node of chain
   private int numberOfEntries;
   public LList ()
   {
       initializeDataFields();
   }// end default constructor
  
   public void clear()
   {
       initializeDataFields();
   }//end clear
  
   public void add(T newEntry) // outOfMemoryError possible
   {
       Node newNode = new Node(newEntry);
       if (isEmpty())
           firstNode = newNode;
       else                    // add to end of nonempty link list
       {
           Node lastNode = getNodeAt(numberOfEntries);
           lastNode.setNextNode(newNode);   // Make last node reference new node
          
       }// end if
       numberOfEntries++;
   }// end add
  
   public void add(int givenPosition, T newEntry) // outOfMemoryError possible
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries +1))
       {
           Node newNode = new Node(newEntry);
          
           if(givenPosition == 1)       // case 1
           {
               newNode.setNextNode(firstNode);
               firstNode = newNode;
           }
           else                        // case 2
           {                           // and givenPosition > 1
               Node nodeBefore = getNodeAt(givenPosition -1);
               Node nodeAfter = nodeBefore.getNextNode();
               newNode.setNextNode(nodeAfter);
               nodeBefore.setNextNode(newNode);
           }// end if
           numberOfEntries ++;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to add operation");
   }// end add
  
   public T remove(int givenPosition)
   {
       T result = null;                   //return value
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
       {   // assertion: !isEmpty
           if(givenPosition == 1)
           {
               result = firstNode.getData();
               firstNode = firstNode.getNextNode();
           }
           else
           {
               Node nodeBefore = getNodeAt(givenPosition -1);
               Node nodeToRemove = nodeBefore.getNextNode();
               result = nodeToRemove.getData();
               Node nodeAfter = nodeToRemove.getNextNode();
               nodeBefore.setNextNode(nodeAfter);
           }
           numberOfEntries--;
           return result;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to remove operation.");
   }
  
   public T replace(int givenPosition, T newEntry)
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
           Node desiredNode = getNodeAt(givenPosition);
           T originalEntry = desiredNode.getData();
           desiredNode.setData(newEntry);
           return originalEntry;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to replace operation.");
   }
   public T getEntry(int givenPosition)
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
           return getNodeAt(givenPosition).getData();
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to getEntry operation.");
   }
   public T[] toArray()
   {
       T[] result = (T[])new Object[numberOfEntries];
       int index = 0;
       Node currentNode = firstNode;
       while ((index < numberOfEntries) && (currentNode != null)) {
           result[index] = currentNode.getData();
           currentNode = currentNode.getNextNode();
           index ++;
       }
       return result;
   }
  
  
  
  
   public boolean contain(T anEntry)
   {
       boolean found = false;
       Node currentNode = firstNode;
       while (!found && (currentNode != null)) {
           if (anEntry.equals(currentNode.getData()))
               found = true;
           else
               currentNode = currentNode.getNextNode();
       }
       return found;
   }
   public int getLength() {
       return numberOfEntries;
      
   }
   public boolean isEmpty()
   {
       boolean result;
       if (numberOfEntries == 0) // Or getLength() == 0
       {
           // Assertion: firstNode == null
           result = true;
       }
       else
       {
           // Assertion: firstNode != null
           result = false;
       }
       return result;
   }
   private void initializeDataFields()
   {
       firstNode = null;
       numberOfEntries = 0;
   }
   private Node getNodeAt(int givenPosition)
   {
       Node currentNode = firstNode;
       for (int counter =1; counter < givenPosition; counter++)
           currentNode = currentNode.getNextNode();
       return currentNode;
   }
   private class Node
   {
       private T data;
       private Node next;
      
       private Node(T dataPortion) {
           data = dataPortion;
           next = null;
       }
      
       private Node(T dataPortion, Node nextNode) {
           data = dataPortion;
           next = nextNode;
       }
       private T getData() {
           return data;
       }
       private void setData(T newData) {
           data = newData;
       }
       private Node getNextNode()
       {
           return next;
       }
       private void setNextNode(Node nextNode) {
           next = nextNode;
       }
   }
  
  
}

Answer 1

Java LList Class:

interface ListInterface<T>
{
   public void add(T newEntry);
   public void add(int newPosition, T newEntry);
   public T remove(int givenPosition);
   public void clear();
   public T replace(int givenPosition, T newEntry);
   public T getEntry(int givenPosition);
   public T[] toArray();
   public boolean contains(T anEntry);
   public int getLength();
   public boolean isEmpty();
}

public class LList<T> implements ListInterface<T>
{
   private Node firstNode; // reference to the first node of chain
   private int numberOfEntries;
   public LList ()
   {
       initializeDataFields();
   }// end default constructor
  
   public void clear()
   {
       initializeDataFields();
   }//end clear
  
   public void add(T newEntry) // outOfMemoryError possible
   {
       Node newNode = new Node(newEntry);
       if (isEmpty())
           firstNode = newNode;
       else                    // add to end of nonempty link list
       {
           Node lastNode = getNodeAt(numberOfEntries);
           lastNode.setNextNode(newNode);   // Make last node reference new node
          
       }// end if
       numberOfEntries++;
   }// end add
  
   public void add(int givenPosition, T newEntry) // outOfMemoryError possible
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries +1))
       {
           Node newNode = new Node(newEntry);
          
           if(givenPosition == 1)       // case 1
           {
               newNode.setNextNode(firstNode);
               firstNode = newNode;
           }
           else                        // case 2
           {                           // and givenPosition > 1
               Node nodeBefore = getNodeAt(givenPosition -1);
               Node nodeAfter = nodeBefore.getNextNode();
               newNode.setNextNode(nodeAfter);
               nodeBefore.setNextNode(newNode);
           }// end if
           numberOfEntries ++;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to add operation");
   }// end add
  
   public T remove(int givenPosition)
   {
       T result = null;                   //return value
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
       {   // assertion: !isEmpty
           if(givenPosition == 1)
           {
               result = firstNode.getData();
               firstNode = firstNode.getNextNode();
           }
           else
           {
               Node nodeBefore = getNodeAt(givenPosition -1);
               Node nodeToRemove = nodeBefore.getNextNode();
               result = nodeToRemove.getData();
               Node nodeAfter = nodeToRemove.getNextNode();
               nodeBefore.setNextNode(nodeAfter);
           }
           numberOfEntries--;
           return result;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to remove operation.");
   }
  
   public T replace(int givenPosition, T newEntry)
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
           Node desiredNode = getNodeAt(givenPosition);
           T originalEntry = desiredNode.getData();
           desiredNode.setData(newEntry);
           return originalEntry;
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to replace operation.");
   }
   public T getEntry(int givenPosition)
   {
       if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
           return getNodeAt(givenPosition).getData();
       }
       else
           throw new IndexOutOfBoundsException("illegal position given to getEntry operation.");
   }
   public T[] toArray()
   {
       T[] result = (T[])new Object[numberOfEntries];
       int index = 0;
       Node currentNode = firstNode;
       while ((index < numberOfEntries) && (currentNode != null)) {
           result[index] = currentNode.getData();
           currentNode = currentNode.getNextNode();
           index ++;
       }
       return result;
   }
   public boolean contains(T anEntry)
   {
       boolean found = false;
       Node currentNode = firstNode;
       while (!found && (currentNode != null)) {
           if (anEntry.equals(currentNode.getData()))
               found = true;
           else
               currentNode = currentNode.getNextNode();
       }
       return found;
   }
   public int getLength() {
       return numberOfEntries;
      
   }
   public boolean isEmpty()
   {
       boolean result;
       if (numberOfEntries == 0) // Or getLength() == 0
       {
           // Assertion: firstNode == null
           result = true;
       }
       else
       {
           // Assertion: firstNode != null
           result = false;
       }
       return result;
   }
   private void initializeDataFields()
   {
       firstNode = null;
       numberOfEntries = 0;
   }
   private Node getNodeAt(int givenPosition)
   {
       Node currentNode = firstNode;
       for (int counter =1; counter < givenPosition; counter++)
           currentNode = currentNode.getNextNode();
       return currentNode;
   }
   private class Node
   {
       private T data;
       private Node next;
      
       private Node(T dataPortion) {
           data = dataPortion;
           next = null;
       }
      
       private Node(T dataPortion, Node nextNode) {
           data = dataPortion;
           next = nextNode;
       }
       private T getData() {
           return data;
       }
       private void setData(T newData) {
           data = newData;
       }
       private Node getNextNode()
       {
           return next;
       }
       private void setNextNode(Node nextNode) {
           next = nextNode;
       }
   }

   public boolean hasRepeats()
   {
     for(int i=1;i<numberOfEntries;i++)
     {
       T data=getEntry(i);
       for(int j=i+1;j<numberOfEntries+1;j++)
       {
         if(data==getEntry(j))
         {
           return true;
         }
       }
     }
     return false;
   }
}

Java Client Program:

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

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); 
    while(true)
    {
      System.out.print("Input a list of integers:");
      LList l=new LList();
      String ar[]=sc.nextLine().split(" ");
      for(int i=0;i<ar.length;i++)
      {
        l.add(Integer.parseInt(ar[i]));
      }
      if(l.hasRepeats())
      {
        System.out.println("The list has repeated values.");
      }
      else
      {
        System.out.println("The list does not have repeated values.");
      }
      System.out.print("Do you want to continue (y/n):");
      String c=sc.nextLine();
      System.out.println();
      if(c.equals("n"))
      {
        break;
      }
    }
  }
}

Sample Output: