Question

******IN JAVA********

I need the following interface implemented accordingly. It is a linked list. The interface can be found below:

List.java

public interface List<T> extends Iterable<T> {
    /**
     * Insert an element at a specified location.
     * @param index
     * @param obj
     * @throws IndexOutOfBoundsException
     */
    public void add(int index, T obj);
    
    /**
     * Append an object to the end of the list.
     * @param obj
     */
    public boolean add(T obj);
    
    public void clear();
    public boolean contains(T obj);
    
    /**
     * If obj is in the list, return the 
     * index of the first occurrence.
     * Otherwise, return -1.
     * @param obj
     * @return 
     */
    public int indexOf(T obj);
    
    public boolean isEmpty();
    
    public int lastIndexOf(T obj);
    
    /**
     * Get and return the value stored at the index.
     * 
     * @param index
     * @return
     * @throws IndexOutOfBoundsException
     */
    public T get(int index);
        
    public T remove(int index);
    public boolean remove(T obj);
    
    /**
     * Update the value in the list at the specified index.
     * Return the old value
     * @throws IndexOutOfBoundsException
     * @param index
     * @param obj
     * @return 
     */
    public T set(int index, T obj);
    
    public int size();
    
    public Object[] toArray();
}

I also need the following driver modified so that it works with the implementation:

ListDriver.java

import java.util.Iterator;


public class ListDriver {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int i = 0;
        List<String> names = new AList<>(5);
        names.add("Alice");
        names.add("Bob");
        names.add("Carol");
        names.add(1, "Eve");
        names.add("Eve");
        for (String name : names)
            System.out.println((i++) + ":" + name);
        i=0;
        System.out.println("Size (should be 5): " + names.size());
        System.out.println("IndexOf(Eve) (should be 1): " + names.indexOf("Eve"));
        System.out.println("LastIndexOf(Eve) (should be 4): " + names.lastIndexOf("Eve"));
        System.out.println("Remove Eve (should be true):" + names.remove("Eve"));
        System.out.println("Size (should be 4): " + names.size());
        System.out.println("IndexOf(Eve) (should be 3): " + names.indexOf("Eve"));
        System.out.println("LastIndexOf(Eve) (should be 3): " + names.lastIndexOf("Eve"));
        for (String name : names)
            System.out.println((i++) + ":" + name);
        i=0;
        System.out.println("Remove Eve (should be true):" + names.remove("Eve"));
        System.out.println("Size (should be 3): " + names.size());
        System.out.println("IndexOf(Eve) (should be -1): " + names.indexOf("Eve"));
        System.out.println("LastIndexOf(Eve) (should be -1): " + names.lastIndexOf("Eve"));
        System.out.println("Size (should be 3): " + names.size());
        System.out.println("Remove 0 (should be Alice): " + names.remove(0));
        System.out.println("Size (should be 2): " + names.size());
        names.add(0, "Alice");
        names.add(1, "Eve");
        names.add("Eve");
        names.add(1, "Eve");
        names.add("Eve");
        names.add(1, "Eve");
        names.add(names.indexOf("Carol"), "Eve");
        names.add(0, "Eve");
        names.add("Eve");
        System.out.println("Size: " + names.size());
        for (String name : names)
            System.out.println((i++) + ":" + name);
        i=0;
        System.out.println("Remove all instances of Eve using iterator... ");
        Iterator<String> it = names.iterator();
        while(it.hasNext()) {
            if (it.next().equals("Eve"))
                it.remove();
        }
        for (String name : names)
            System.out.println((i++) + ":" + name);
        i=0;
        System.out.println("Testing clear");
        names.clear();
        System.out.println("Size (should be 0): " + names.size());
        
    }
    
}

Thanks in advance. Will upvote!

Answer 1

// List.java
public interface List<T> extends Iterable<T> {
  
   /**
* Insert an element at a specified location.
* @param index
* @param obj
* @throws IndexOutOfBoundsException
*/
public void add(int index, T obj);
  
/**
* Append an object to the end of the list.
* @param obj
*/
public boolean add(T obj);
  
public void clear();
public boolean contains(T obj);
  
/**
* If obj is in the list, return the
* index of the first occurrence.
* Otherwise, return -1.
* @param obj
* @return
*/
public int indexOf(T obj);
  
public boolean isEmpty();
  
public int lastIndexOf(T obj);
  
/**
* Get and return the value stored at the index.
*
* @param index
* @return
* @throws IndexOutOfBoundsException
*/
public T get(int index);
  
public T remove(int index);
public boolean remove(T obj);
  
/**
* Update the value in the list at the specified index.
* Return the old value
* @throws IndexOutOfBoundsException
* @param index
* @param obj
* @return
*/
public T set(int index, T obj);
  
public int size();
  
public Object[] toArray();

}

//end of List.java

// Node.java : Java class to represent the Node of the linked list
public class Node<T>
{
   private T data;
   private Node<T> next;
  
   public Node(T data)
   {
       this.data = data;
       this.next = null;
   }
  
   public void setData(T data)
   {
       this.data = data;
   }
  
   public void setNext(Node<T> next)
   {
       this.next = next;
   }
  
   public T getData()
   {
       return data;
   }
  
   public Node<T> getNext()
   {
       return next;
   }
}

//end of Node.java

// AList.java : Java program to implement the List as linked list
import java.util.Iterator;

public class AList<T> implements List<T>{
  
  
   private Node<T> head;
   private int size ;
  
   public AList(int d)
   {
       head = null;
       size = 0;
   }

   @Override
   public Iterator<T> iterator() {
       return new ListIterator();
   }

   @Override
   public void add(int index, T obj) {
       if(index >=0 && index <= size())
       {
           Node<T> node = new Node<T>(obj);
           if(index == size())
               add(obj);
           else if(index == 0)
           {
               node.setNext(head);
               head = node;
           }else
           {
               int i = 0;
               Node<T> curr = head;
              
               while(i < index-1)
               {
                   curr = curr.getNext();
                   i++;
               }
              
               node.setNext(curr.getNext());
               curr.setNext(node);
           }
           size++;
       }else
           throw new IndexOutOfBoundsException();
   }

   @Override
   public boolean add(T obj) {
       Node<T> node = new Node<T>(obj);
       if(head == null)
           head = node;
       else
       {
           Node<T> curr = head;
           while(curr.getNext() != null)
               curr = curr.getNext();
           curr.setNext(node);
       }
       size++;
       return true;
   }

   @Override
   public void clear() {
       head = null;
       size = 0;
   }

   @Override
   public boolean contains(T obj) {
       Node<T> curr = head;
      
       while(curr != null)
       {
           if(curr.getData().equals(obj))
               return true;
           curr = curr.getNext();
       }
      
       return false;
   }

   @Override
   public int indexOf(T obj) {
       int i=0;
       Node<T> curr = head;
       while(curr != null)
       {
           if(curr.getData().equals(obj))
               return i;
           curr = curr.getNext();
           i++;
       }
      
       return -1;
   }

   @Override
   public boolean isEmpty() {
       return(head == null);
   }

   @Override
   public int lastIndexOf(T obj) {
       int index = -1;
       int i=0;
      
       Node<T> curr = head;
      
       while(curr != null)
       {
           if(curr.getData().equals(obj))
               index = i;
           i++;
           curr = curr.getNext();
       }
      
       return index;
   }

   @Override
   public T get(int index) {
      
       if(index >=0 && index < size())
       {
           int i=0;
           Node<T> curr = head;
           while((curr != null) && (i < index))
           {
               curr = curr.getNext();
               i++;
           }
          
           return curr.getData();
       }else
           throw new IndexOutOfBoundsException();
   }

   @Override
   public T remove(int index) {
       if(index >=0 && index < size())
       {
           int i=0;
           Node<T> curr = head;
           Node<T> prev = null;
           while((curr != null) && (i < index))
           {
               prev = curr;
               curr = curr.getNext();
               i++;
           }
          
           if(prev == null)
               head = curr.getNext();
           else
               prev.setNext(curr.getNext());
           size--;
           return curr.getData();
       }else
           throw new IndexOutOfBoundsException();
   }

   @Override
   public boolean remove(T obj) {
       Node<T> curr = head;
       Node<T> prev = null;
      
       while(curr != null)
       {
           if(curr.getData().equals(obj))
           {
               if(prev == null)
                   head = curr.getNext();
               else
                   prev.setNext(curr.getNext());
               size--;
               return true;
           }
           prev = curr;
           curr = curr.getNext();
       }
       return false;
   }

   @Override
   public T set(int index, T obj) {
       if(index >=0 && index < size())
       {
           int i = 0;
           Node<T> curr = head;
          
           while((curr != null) && (i < index))
           {
               i++;
               curr = curr.getNext();
           }
          
           T elem = curr.getData();
           curr.setData(obj);
           return elem;
       }else
           throw new IndexOutOfBoundsException();
   }

   @Override
   public int size() {
       return size;
   }

   @Override
   public Object[] toArray() {
      
       if(size() > 0)
       {
           Object list[] = new Object[size()];
           Node<T> curr = head;
           int i=0;
           while(curr != null)
           {
               list[i] = curr.getData();
               i++;
               curr = curr.getNext();
           }
          
           return list;
       }
      
       return null;
   }

   private class ListIterator implements Iterator<T>
   {
      
       private Node<T> curr;
       private Node<T> prev;
      
       public ListIterator()
       {
           curr = null;
           prev = null;
       }
      
       @Override
       public boolean hasNext() {
           if(curr == null)
           {
               if(head == null)
                   return false;
               else
                   return true;
           }else
           {
               return(curr.getNext() != null);
           }
       }

       @Override
       public T next() {
           prev = curr;
           if(curr == null)
               curr = head;
           else
               curr = curr.getNext();
           return curr.getData();
       }
      
       public void remove()
       {
           if(prev != null)
           {
               prev.setNext(curr.getNext());
               curr = curr.getNext();
           }else
           {
               head = curr.getNext();
           }
           size--;
       }
      
   }
}
//end of AList.java

// ListDriver.java : Java program to implement AList class
import java.util.Iterator;

public class ListDriver {
  
   /**
* @param args the command line arguments
*/
public static void main(String[] args) {
int i = 0;
List<String> names = new AList<>(5);
names.add("Alice");
names.add("Bob");
names.add("Carol");
names.add(1, "Eve");
names.add("Eve");
for (String name : names)
System.out.println((i++) + ":" + name);
i=0;
System.out.println("Size (should be 5): " + names.size());
System.out.println("IndexOf(Eve) (should be 1): " + names.indexOf("Eve"));
System.out.println("LastIndexOf(Eve) (should be 4): " + names.lastIndexOf("Eve"));
System.out.println("Remove Eve (should be true):" + names.remove("Eve"));
System.out.println("Size (should be 4): " + names.size());
System.out.println("IndexOf(Eve) (should be 3): " + names.indexOf("Eve"));
System.out.println("LastIndexOf(Eve) (should be 3): " + names.lastIndexOf("Eve"));
for (String name : names)
System.out.println((i++) + ":" + name);
i=0;
System.out.println("Remove Eve (should be true):" + names.remove("Eve"));
System.out.println("Size (should be 3): " + names.size());
System.out.println("IndexOf(Eve) (should be -1): " + names.indexOf("Eve"));
System.out.println("LastIndexOf(Eve) (should be -1): " + names.lastIndexOf("Eve"));
System.out.println("Size (should be 3): " + names.size());
System.out.println("Remove 0 (should be Alice): " + names.remove(0));
System.out.println("Size (should be 2): " + names.size());
names.add(0, "Alice");
names.add(1, "Eve");
names.add("Eve");
names.add(1, "Eve");
names.add("Eve");
names.add(1, "Eve");
names.add(names.indexOf("Carol"), "Eve");
names.add(0, "Eve");
names.add("Eve");
System.out.println("Size: " + names.size());
for (String name : names)
System.out.println((i++) + ":" + name);
i=0;
System.out.println("Remove all instances of Eve using iterator... ");
Iterator<String> it = names.iterator();
while(it.hasNext()) {
if (it.next().equals("Eve"))
   it.remove();
}
for (String name : names)
System.out.println((i++) + ":" + name);
i=0;
System.out.println("Testing clear");
names.clear();
System.out.println("Size (should be 0): " + names.size());
  
}
}
//end of ListDriver.java

Output: