Question

Array-Based Linked List Implementation: JAVA

Decide how to write the methods with items being stored in an array. NOT in linked List.
Implement an array-based Linked List in your language. Use double as the item. You need to create a driver includes several items and inserts them in order in a list.

Identify the necessary methods in a List Linked implementation. Look at previous Data Structures (stack or queue) and be sure to include all necessary methods.
DO NOT USE your language's Library List. You will receive zero points.
Write a LinkedList class:
class LinkList {
// attributes
// size
// maxSize
// array   
// CONSTRUCTORS
// METHODS   
// TOSTRING/DISPLAY--returns string }

Write a driver (tester) or write unit tests to test all your methods.
Test add methods
Test delete methods
Test size
Test print
Test adding to full list--handle exception
Test adding to empty list--handle exception

Answer 1

// LinkList.java

public class LinkList {
  
   // attributes
   private int data[];
   private int size;
   private int maxSize;

   // CONSTRUCTORS
  
   // default constructor that creates an empty list of capacity 100
   public LinkList()
   {
       this(100);
   }
  
   // parameterized constructor that creates an empty list of capacity
   public LinkList(int capacity)
   {
       if(capacity < 0) // capacity < 0, create list of size 100
           maxSize = 100;
       else
           maxSize = capacity;
       size = 0;
       data = new int[maxSize];
   }
  
   // METHODS   
   // method to insert item at the end of list
   public void addLast(int item)
   {
       // list is not full
       if(!isFull())
       {
           data[size] = item;
           size++;
          
       }else   // list is full, throw exception
           throw new IllegalStateException("List is full!!!");
   }
  
   // method to insert item at the front of list
   public void addFirst(int item)
   {
       // list is not full
       if(!isFull())
       {
           for(int i=size;i > 0;i--)
               data[i] = data[i-1];
           data[0] = item;
           size++;
          
       }else   // list is full, throw exception
           throw new IllegalStateException("List is full!!!");
   }
  
   // method to remove and return the front element of the list
   public int removeFirst()
   {
       if(!isEmpty()) // list is not empty
       {
           int item = data[0]; // get the front element

           // loop to shift all elements to left by 1 position from index 1 to end
           for(int i=0;i<size-1;i++)
           {
               data[i] = data[i+1];
           }
           size--;
           return item;
          
       }else // empty list, throw exception
           throw new IllegalStateException("List is empty!!!");
   }

// method to remove and return the last element of the list
   public int removeLast()
   {
       if(!isEmpty()) // list is not empty
       {
           size--; // remove the last element
           return data[size]; // return the last element
          
       }else // empty list, throw exception
           throw new IllegalStateException("List is empty!!!");
   }

   // method to return true if list is empty else return false
   public boolean isEmpty()
   {
       return size == 0;
   }
  
   // method to return true if list is full else return false
   public boolean isFull()
   {
       return size == maxSize;
   }
  
   // method to return string representation of the list
   public String toString()
   {
       String str = "[";
       if(!isEmpty())
       {
           for(int i=0;i<size;i++) {
               str += data[i];
               if(i < size-1)
                   str += ", ";
           }
       }
      
       str += "]";
       return str;
   }
  
   // method to return the number of elements of the queue
   public int size()
   {
       return size;
   }

}

//end of LinkList.java

// LinkListTester.java

public class LinkListTester {
  
   public static void main(String[] args) {

       // create a list of size 10
       LinkList list = new LinkList(10);
      
       // insert 5 elements at the front
       for(int i=1;i<=5;i++)
           list.addFirst(i);

       // insert 5 elements at the end
       for(int i=6;i<=10;i++)
           list.addLast(i);
      
       // display the list
       System.out.println("List: "+list); // [5, 4, 3, 2, 1, 6, 7, 8, 9, 10]
       System.out.println("Size: "+list.size()); // 10
      
       // try to add to a full list
       try
       {
           System.out.println("Adding to full list:");
           list.addLast(11);
       }catch(IllegalStateException e)
       {
           System.out.println(e.getMessage());
       }
      
       // loop to empty the list
       while(!list.isEmpty())
       {
           System.out.println("Element removed from first: "+list.removeFirst());
           System.out.println("Element removed from last: "+list.removeLast());
       }
      
       // try to remove from an empty list
       try
       {
           System.out.println("Removing from an empty list:");
           list.removeLast();
       }catch(IllegalStateException e)
       {
           System.out.println(e.getMessage());
       }
      
       System.out.println("Size: "+list.size());
       System.out.println("List: "+list);
   }

}

//end of LinkListTester.java

Output: