Instead of a String[] it must use a Doubly-Linked List with a Dummy Front and Du

Question

Instead of a String[] it must use a Doubly-Linked List with a Dummy Front and Dummy Rear to store the List's data. How do I change that in my class list?

The List class' public API is the same except:

(1) Constructor List(int size) has been replaced with List(). The Linked-List has no maximum size.

(2) Constructor List(List list) has been added. It constructs a new List with the items in the input list.

//main:

public class AssignmentFour
{
   public static void main(String[] args)
   {
       List myList = new List();
       List emptyList = new List(myList);
      
       // Cause List Empty Message
       myList.removeFront();
       myList.removeRear();
       myList.removeItem("a");
      
       // Cause Not found message
       myList.addToFront("x");
       myList.removeItem("y");
       myList.removeItem("x");
       myList.addAfterItem("x", "z");
       myList.addBeforeItem("x", "z");
          
       // Normal behavior
       myList.addToFront("not.");
       myList.addToFront("or");
       myList.addToRear("is");
       myList.addToRear("try.");
       myList.addAfterItem("is", "no");
       myList.addBeforeItem("is", "There");
       myList.addToFront("Do");
       myList.addAfterItem("or", "do");
      
       myList.print("Original list");
       myList.printSorted("Sorted Original List");
       emptyList.print("Empty List");
      
       List copyOfList = new List(myList);
          
       sop(" Front is " + myList.getFront());
       sop("Rear is " + myList.getRear());
       sop("Count is " + myList.askCount());
       sop("Is There present? " + myList.isPresent("There"));
       sop("Is Dog present? " + myList.isPresent("Dog"));
  
       myList.addToFront("junk");
       myList.addToRear("morejunk");
       myList.addAfterItem("or", "moremorejunk");
      
       myList.print("List with junk");
       sop("Count is " + myList.askCount());
      
       copyOfList.print("Untouched copy of the list");
      
       myList.removeFront();
       myList.removeRear();
       myList.removeItem("moremorejunk");
       myList.print("List with junk removed");
       sop("Count is " + myList.askCount());
       sop("");
      
       copyOfList.print("Untouched copy of the list");
      
       while(myList.askCount() > 0) myList.removeFront();
      
       myList.print("List after removing all items");
       copyOfList.print("Copy of List after removing all items");
   }
  
   private static void sop(String s)
   {
       System.out.println(s);
   }
}

//My class list:

import java.util.Arrays;

public class List {  
   private String[] mList;
   private int mCount;

   public List(int size)
   {
       mCount = 0;
       mList = new String[size];
   }

   public void addToFront(java.lang.String item)
   {
       if (mCount == mList.length)
       {
           System.out.println("List Full");
       }
       else if (mCount == 0)
       {
           mList[0] = item;
           mCount++;
       }
       else
       {
           shiftRight(mCount,0);
           mList[0] = item;
           mCount++;
       }
   }
   public void addToRear(java.lang.String item)
   {
       if (mCount == mList.length)
       {
           System.out.println("List Full");
       }
       else {
           mList[mCount++] = item;
       }
   }
   public void addBeforeItem(java.lang.String beforeItem, java.lang.String item)
   {
       if (mCount == mList.length)
       {
           System.out.println("List Full");
       }
       else if(isPresent(beforeItem) && mCount < mList.length)
       {
           if (find(beforeItem) == 0)
           {
               shiftRight(mCount,0);
               mList[0] = item;
               mCount++;
           }
           else
           {
               shiftRight(mCount,find(beforeItem));
               mList[find(beforeItem)] = item;
               mCount++;
           }
       }
       else if(!isPresent(beforeItem))
           {
               System.out.println("Item not found");
           }
   }
   //Finding the index of the specific element
   private int find (String s)
   {
       for(int i = 0; i < mCount;i++)
       {
           if (mList[i].equals(s))
           {
               return i;
           }
       }
       return -1;
   }
   public void addAfterItem(java.lang.String afterItem, java.lang.String item)
   {
       if (mCount == mList.length)
       {
           System.out.println("List Full");
       }
       else if(isPresent(afterItem) && mCount < mList.length)
       {
               shiftRight(mCount, find(afterItem));
               mList[find(afterItem)+1] = item;
               mCount++;
       }
       else
       {
           System.out.println("Item not found");
       }
   }

   public java.lang.String getFront()
   {
       return mList[0];
   }

   public java.lang.String getRear()
   {
       return mList[mCount-1];
   }

   public boolean isPresent(String item)
   {
       for (int i = 0; i < mCount; i++)
           if(mList[i].equals(item))
           {
               return true;
           }
       return false;
   }

   public int askCount()
   {
       return mCount;
   }
   public void removeFront()
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else
       {
           shiftLeft(mCount, 0);
           mCount--;
       }
   }
   public void removeRear()
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else
       {
           mCount--;
       }
   }

   public void removeItem(java.lang.String item)
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else if (!isPresent(item))
       {
           System.out.println("Item not found");
       }
       else
       {
           int x = find(item);
           shiftLeft(mCount,x);
           mCount--;
       }
   }

   public void print(java.lang.String title)
   {
       System.out.println("");
       System.out.println(title);
       for(int i = 0; i < mCount; i++)
       {
           System.out.print(mList[i] + " ");
       }
       System.out.println();
   }
  
   public void printSorted(java.lang.String title)
   {
       String[] mListC = new String[mCount];
       System.arraycopy( mList, 0,mListC, 0, mCount);
       Arrays.sort(mListC);
       System.out.println();
       System.out.println(title);
       for(String s : mListC)
       {
           System.out.print(s + " ");
       }
       System.out.println();
   }
  
   private void shiftRight(int count, int end)
   {
       for (int i = (count-1); i >= end; i--)
       {
           mList[i+1] = mList[i];
       }
   }
   private void shiftLeft(int count, int start)
   {
       for (int i = start;i < count-1; i++)
       {
           mList[i] = mList[i+1];
       }
   }  
}

// Desired Output:

Explanation / Answer

import java.util.Arrays;

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Sam
*/

public class AssignmentFour
{
   public static void main(String[] args)
   {
       List myList = new List();
       List emptyList = new List(myList);
    
       // Cause List Empty Message
       myList.removeFront();
       myList.removeRear();
       myList.removeItem("a");
    
       // Cause Not found message
       myList.addToFront("x");
       myList.removeItem("y");
       myList.removeItem("x");
       myList.addAfterItem("x", "z");
       myList.addBeforeItem("x", "z");
        
       // Normal behavior
       myList.addToFront("not.");
       myList.addToFront("or");
       myList.addToRear("is");
       myList.addToRear("try.");
       myList.addAfterItem("is", "no");
       myList.addBeforeItem("is", "There");
       myList.addToFront("Do");
       myList.addAfterItem("or", "do");
    
       myList.print("Original list");
       myList.printSorted("Sorted Original List");
       emptyList.print("Empty List");
    
       List copyOfList = new List(myList);
        
       sop(" Front is " + myList.getFront());
       sop("Rear is " + myList.getRear());
       sop("Count is " + myList.askCount());
       sop("Is There present? " + myList.isPresent("There"));
       sop("Is Dog present? " + myList.isPresent("Dog"));

       myList.addToFront("junk");
       myList.addToRear("morejunk");
       myList.addAfterItem("or", "moremorejunk");
    
       myList.print("List with junk");
       sop("Count is " + myList.askCount());
    
       copyOfList.print("Untouched copy of the list");
    
       myList.removeFront();
       myList.removeRear();
       myList.removeItem("moremorejunk");
       myList.print("List with junk removed");
       sop("Count is " + myList.askCount());
       sop("");
    
       copyOfList.print("Untouched copy of the list");
    
       while(myList.askCount() > 0) myList.removeFront();
    
       myList.print("List after removing all items");
       copyOfList.print("Copy of List after removing all items");
   }

   private static void sop(String s)
   {
       System.out.println(s);
   }
}

//My class list:

final class List {
   class Node {
       String data;
       Node prev, next;
       Node(String data){
           this.data = data;
           next = prev = null;
       }
   }
   private Node dummyFront;
   private Node dummyRear;
   private int mCount;

   public List()
   {
       mCount = 0;
       dummyFront=dummyRear=null;
   }

   public List(List sourceList){
       mCount = 0;
       dummyFront=dummyRear=null;
       Node temp = sourceList.dummyFront;
       while (temp!=null){
           addToRear(temp.data);
           temp = temp.next;
       }
   }

   public void addToFront(java.lang.String item)
   {
       Node newNode = new Node(item);
       if (dummyFront == null)
           dummyFront = dummyRear = newNode;
       else {
           newNode.next = dummyFront;
           dummyFront = newNode;
       }
   }
   public void addToRear(java.lang.String item)
   {
       Node newNode = new Node(item);
       if (dummyFront == null)
           dummyFront = dummyRear = newNode;
       else {
           newNode.prev = dummyRear;
           dummyRear = newNode;
       }
   }
   public void addBeforeItem(java.lang.String beforeItem, java.lang.String item)
   {
       if (dummyFront == null){
           System.out.println("List Empty!");
       }
       else if (dummyFront.data.equals(beforeItem))
               addToFront(item);
       else {
           Node newNode = new Node(item);
           Node tempNode = dummyFront;
           while (tempNode.next!=null){
               if (tempNode.next.data.equals(beforeItem))
                   break;
               tempNode = tempNode.next;
           }
           if (tempNode.next == null)
               return; //filure
           newNode.next = tempNode.next;
           newNode.prev = tempNode;
           tempNode.next.prev = newNode;
           tempNode.next=newNode;
       }
         
     
   }
   //Finding the index of the specific element
   private int find (String s)
   {
       Node tempNode = dummyFront;
       int i = 0;
       while (tempNode!=null)
           if (tempNode.data.equals(s))
               return i;
           else{
               tempNode = tempNode.next;
               i++;
           }
       return -1;
   }
   public void addAfterItem(java.lang.String afterItem, java.lang.String item)
   {
       if (dummyFront == null){
           System.out.println("List Empty!");
       }
       else if (dummyRear.data.equals(afterItem))
               addToRear(item);
       else {
           Node newNode = new Node(item);
           Node tempNode = dummyFront;
           while (tempNode!=null){
               if (tempNode.data.equals(afterItem))
                   break;
               tempNode = tempNode.next;
           }
           if (tempNode == null)
               return; //filure
           newNode.next = tempNode.next;
           newNode.prev = tempNode;
           tempNode.next.prev = newNode;
           tempNode.next=newNode;
       }
   }

   public java.lang.String getFront()
   {
       return dummyFront.data;
   }

   public java.lang.String getRear()
   {
       return dummyRear.data;
   }

   public boolean isPresent(String item)
   {
       Node tempNode = dummyFront;
       while (tempNode!=null)
           if (tempNode.data.equals(item))
               return true;
           else
               tempNode = tempNode.next;
             
       return false;
   }

   public int askCount()
   {
       return mCount;
   }
   public void removeFront()
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else
       {
           dummyFront = dummyFront.next;
           dummyFront.prev = null;
           mCount--;
       }
   }
   public void removeRear()
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else
       {
           dummyRear = dummyRear.prev;
           dummyRear.next = null;
           mCount--;
       }
   }

   public void removeItem(java.lang.String item)
   {
       if (mCount == 0)
       {
           System.out.println("List Empty");
       }
       else if (!isPresent(item))
       {
           System.out.println("Item not found");
       }
       else if (dummyFront.data.equals(item))
           removeFront();
       else if (dummyRear.data.equals(item))
           removeRear();
       {
           Node tempNode = dummyFront;
           while (!tempNode.data.equals(item))
               tempNode = tempNode.next;
           tempNode.prev.next = tempNode.next;
           tempNode.next.prev = tempNode.prev;
       }
   }

   public void print(java.lang.String title)
   {
       System.out.println("");
       System.out.println(title);
       Node tempNode = dummyFront;
       while (tempNode!=null){
           System.out.print(tempNode.data+",");
           tempNode = tempNode.next;
       }
       System.out.println();
   }

   public void printSorted(java.lang.String title)
   {
       String[] mListC = new String[mCount];
       int i = 0;
       Node tempNode = dummyFront;
       while (tempNode!=null){
           mListC[i++] = tempNode.data;
           tempNode = tempNode.next;
       }
       Arrays.sort(mListC);
       System.out.println();
       System.out.println(title);
       for(String s : mListC)
       {
           System.out.print(s + " ");
       }
       System.out.println();
   }

   private void shiftRight(int count, int end)
   {
      // NOT VALID
   }
   private void shiftLeft(int count, int start)
   {
       //NOT VALID
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects