Provide the specification for the List ADT on the List interface. For this you w
ID: 640066 • Letter: P
Question
Provide the specification for the List ADT on the List interface. For this you will have to describe the pre- and pos-conditions for the remaining methods. You may use english in your descriptions, though you may want to consider using Java boolean expressions to make the specifications clearer and unambiguous. Make sure to write the specs as Javadoc comments.
Extend the List interface with the following methods:
Object[] toArray(): returns an array with all the elements in the list.
String toString(): generates a string representation of the list that has the following format: (key,item) -- (key,item) -- (key,item) -- ...
Implement all the methods in every list class.
public interface List,V> {
public abstract boolean add(K key,V value);
public abstract V remove(K key);
public abstract V remove(int n);
public abstract V remove();
public abstract V lookup(K key);
public abstract int size();
public abstract V get(int n);
}
Explanation / Answer
Necessary steps to implement the List interface:
In order to Implement the List interface, first create a class called ListClass that can initialize and retrieve the key and the value.
Next, create an implementation class say MyList that will implement the List interface.
The MyList class contains all the implementation code of the List interface.
Here is the code as follows:
Program code:
//List interface
public interface List<K,V>
{
//abstract methods
public abstract boolean add(K key,V value);
public abstract V remove(K key);
public abstract V remove(int n);
public abstract V remove();
public abstract V lookup(K key);
public abstract int size();
public abstract V get(int n);
public abstract Object[] toArray();
public abstract String toString();
}
//ListClass that can access the key and value
public class ListClass<K , V>
{
//instance variables
private K key;
private V value;
//constructor
public ListClass(K key, V value)
{
this.key = key;
this.value = value;
}
//getKey method that returns the key
public K getKey()
{
return key;
}
//getValue method that returns the value
public V getValue()
{
return value;
}
//setValue method sets the value
public void setValue(V value)
{
this.value = value;
}
}
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
//MyList class that implements all the methods of
//the List interface
public class MyList<K, V> implements List<K, V>
{
//declare the instance variables
private int size;
private int DEFAULT_CAPACITY = 20;
@SuppressWarnings("unchecked")
//create a array of ListClass
private ListClass<K, V>[] values = new ListClass[DEFAULT_CAPACITY];
//lookup method takes a key as parameter
//looks up in the array for the parameter and
//returns the value.
public V lookup(K key)
{
for (int i = 0; i < size; i++)
{
if (values[i] != null) {
if (values[i].getKey().equals(key))
{
return values[i].getValue();
}
}
}
return null;
}
//add method that takes a key and value and looks for the
//key in the array if exist sets the value and
//returns a value true
public boolean add(K key, V value)
{
boolean insert = true;
for (int i = 0; i < size; i++)
{
if (values[i].getKey().equals(key))
{
values[i].setValue(value);
insert = false;
}
}
return insert;
}
//addElement method that takes key and value
//as parameters and checks for the whether the key matches or not
//by calling the boolean add method
//if the add method return true, then it add the key and value to
//array;
public void addElements(K key, V value)
{
if(add(key, value))
{
ensureCapacity();
values[size++] = new ListClass<K, V>(key, value);
}
}
//ensureCapacity method checks for the size
//if the size is not sufficient it increments the size
private void ensureCapacity()
{
if (size == values.length)
{
int newSize = values.length * 2;
values = Arrays.copyOf(values, newSize);
}
}
//size method returns the size value
public int size()
{
return size;
}
//remove method, removes the value depending on the
//key and returns the V value and decrements the
//size and reduces the array
public V remove(K key)
{
V tempValue=null;
for (int i = 0; i < size; i++)
{
if (values[i].getKey().equals(key))
{
tempValue=values[i].getValue();
values[i] = null;
size--;
condenseArray(i);
}
}
return tempValue;
}
//remove method, removes the value depending on the
//index and returns the V value and decrements the
//size and reduces the array
public V remove(int index)
{
V tempValue=null;
for (int i = 0; i < size; i++)
{
if (i==index)
{
tempValue=values[i].getValue();
values[i] = null;
size--;
condenseArray(i);
}
}
return tempValue;
}
public V remove()
{
return null;
}
//condenseArray method depending on the
//removing of element, the elements adjusted in the array
private void condenseArray(int start)
{
for (int i = start; i < size; i++)
{
values[i] = values[i + 1];
}
}
//get method depending on the index value
//returns the value present at the index.
public V get(int n)
{
V tempValue=null;
for (int i = 0; i < size; i++)
{
if (i==n)
{
tempValue=values[i].getValue();
}
}
return tempValue;
}
//toString method, returns a string depending on the
//output format
public String toString()
{
String s="";
for(int i=0; i<size; i++)
{
if(i==size-1)
s+="("+values[i].getKey()+","+values[i].getValue()+")";
else
s+="("+values[i].getKey()+","+values[i].getValue()+")--";
}
return s;
}
@Override
public Object[] toArray()
{
// TODO Auto-generated method stub
return values;
}
}
//ListDemo is an implementation class of the MyList
public class ListDemo
{
//main method
public static void main(String args[])
{
//Create an object to the MyList class
MyList<String, Integer> list = new MyList<String, Integer>();
//by using addElements method add the elements to the list
list.addElements("Lars", 1);
list.addElements("Kav", 2);
list.addElements("Lar", 3);
list.addElements("Brute",4);
list.addElements("Omar", 5);
//print the array
System.out.println(list.toString());
//remove an element by key
System.out.println(" Remove an element by key and the value removed is: "+list.remove("Omar"));
//print the list
System.out.println("The list after removing an element: "+list.toString());
//remove an element by index
System.out.println(" Remove an element by index and the value removed is: "+list.remove(3));
//print the list
System.out.println("The list after removing an element: "+list.toString());
}
}
------------------------------------------------------------------------------------------------------------------
Sample output:
(Lars,1)--(Kav,2)--(Lar,3)--(Brute,4)--(Omar,5)
Remove an element by key and the value removed is: 5
The list after removing an element:
(Lars,1)--(Kav,2)--(Lar,3)--(Brute,4)
Remove an element by index and the value removed is: 4
The list after removing an element:
(Lars,1)--(Kav,2)--(Lar,3)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.