The following list classes (SimpleBoundedList<K, V>, SimpleLinkedList<K, V>, and
ID: 3828147 • Letter: T
Question
The following list classes (SimpleBoundedList<K, V>, SimpleLinkedList<K, V>, and UnboundedList<K, V>) have methods inhereted from the interface List<K,V>. Complete the implementation of the methods in these classes so that they behave accordingly(ie. SimpleLinkedList behaves as a linked list should etc.). Must use the generics and do not use HashMap util. Any of these lists should be able to be used later in a program that creates a registry of names and ID numbers.
List.java
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();
}
SimpleBoundedList.java (
import java.util.*;
public class SimpleBoundedList<K, V> implements List<K, V> {
private class Entry {
protected K key;
protected V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
protected Object[] values;
private int start = 0;
private int nextEmpty = 0;
/**
*
*/
@SuppressWarnings("unchecked")
public SimpleBoundedList(int bound) {
values = new Object[bound];
}
@Override
public boolean add(K key, V value) {
boolean modify = false;
int nextIndex = nextEmpty;
if (((nextEmpty + 1) % values.length) != start) {
nextEmpty = (nextEmpty + 1) % values.length;
modify = true;
} else if (values[nextEmpty] == null) {
modify = true;
}
if (modify)
values[nextIndex] = new Entry(key, value);
return modify;
}
@Override
public V remove(K key) {
// TODO Auto-generated method stub
return null;
}
@Override
public V lookup(K key) {
return null;
}
@Override
public V remove(int n) {
// TODO Auto-generated method stub
return null;
}
@Override
public int size() {
return 0;
}
@Override
public V get(int n) {
return null;
}
@Override
public V remove() {
// TODO Auto-generated method stub
return null;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
return null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(Object en: values) {
Entry entry = (Entry) en;
sb.append(" Name : " + entry.key
+ " ID : " + entry.value);
}
return sb.toString();
}
}
UnboundedList.java
public class UnboundedList<K,V> extends SimpleBoundedList<K,V> {
public UnboundedList(int bound) {
super(bound);
}
@Override
public boolean add(K key, V value) {
ensureCapacity();
super.add(key, value);
return true;
}
private void ensureCapacity() {
if (this.size() == this.values.length) {
Object[] newArray = new Object[values.length * 2];
// TODO: This code potentially creates
// a gap in the list. Please fix if possible.
for (int i = 0; i < values.length; ++i) {
newArray[i] = values[i];
}
this.values = newArray;
}
}
}
SimpleLinkedList.java
public class SimpleLinkedList<K, V> implements List<K, V> {
private Node head = null;
@Override
public boolean add(K key, V value) {
if (head == null) { // List is empty
Node nn = new Node(key, value);
head = nn;
} else {
Node node = head;
while (node.next != null) {
node = node.next;
}
node.next = new Node(key, value);
}
return true;
}
@Override
public V remove(K key) {
// TODO Auto-generated method stub
return null;
}
@Override
public V remove(int n) {
// TODO Auto-generated method stub
return null;
}
@Override
public V remove() {
// TODO Auto-generated method stub
return null;
}
@Override
public V lookup(K key) {
// TODO Auto-generated method stub
return null;
}
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public V get(int n) {
return null;
}
private class Node {
protected K key;
protected V value;
protected Node next;
Node(K k, V v) {
key = k;
value = v;
next = null;
}
}
@Override
public Object[] toArray() {
return null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = head;
while (node != null) {
sb.append("(" + node.key + "," + node.value + ") -- ");
node = node.next;
}
return sb.toString();
}
}
Explanation / Answer
Hi,
Please see the classes below.
Please comment for any queries.
Thanks
List.java
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();
}
SimpleBoundedList.java
public class SimpleBoundedList<K extends Comparable<K>,V> implements List<K, V> {
protected Object[] values;
protected int start = 0;
protected int nextEmpty = 0;
/**
*
*/
public SimpleBoundedList(int bound) {
values = new Object[bound];
}
/**
* To add and antry with a key and value
* @param key
* @param value
* @return
*/
public boolean add(K key, V value) {
boolean modify = false;
int nextIndex = nextEmpty;
if (((nextEmpty + 1) % values.length) != start) {
nextEmpty = (nextEmpty + 1) % values.length;
modify = true;
} else if (values[nextEmpty] == null) {
modify = true;
}
if (modify)
values[nextIndex] = new Entry<K,V>(key,value);
return modify;
}
/**
* to remove an entry with a key
* @param key
* @return
*/
public V remove(K key) {
V deletedV = null;
for (int i = 0; i < values.length; i++) {
if (((Entry<K, V>) values[i]).key.compareTo(key) == 0) {
if (values[start] == values[i]
&& values[start] != values[nextEmpty]) {
start = (start + 1) % values.length;
} else if (values[nextEmpty] == values[i]
&& values[start] != values[nextEmpty]) {
nextEmpty = (nextEmpty - 1) % values.length;
}
deletedV = ((Entry<K,V>) values[i]).value;
values[i] = null;
}
shiftList();
}
return deletedV;
}
/**
* To shift
*/
private void shiftList() {
Object[] tempList = new Object[values.length];
for(int i = 0; i < values.length; i++) {
if(tempList[i] != null) {
tempList[i] = values[i];
}else {
values[i] = values[(i) % values.length];
}
}
}
/**
* To lookup for an entry with a key
* @param key
* @return
*/
public V lookup(K key) {
V value = null;
for (int i = 0; i < values.length; i++) {
if (((Entry<K, V>) values[i]).key.compareTo(key) == 0) {
value = ((Entry<K,V>) values[i]).value;
}
}
return value;
}
/**
* To remove an entry at index
* @param n
* @return
*/
public V remove(int n) {
V deletedV = (V) values[n];
values[(start + n) % values.length] = null;
if (values[start] == null && start != nextEmpty) {
start = (start + 1) % values.length;
} else if (values[nextEmpty] == null && start != nextEmpty) {
nextEmpty = (nextEmpty - 1) % values.length;
}
shiftList();
return deletedV;
}
/**
* To get the list size
* @return
*/
public int size() {
return Math.abs(start - nextEmpty) + 1;
}
/**
* To get an entry at index n
* @param n
* @return
*/
public V get(int n) {
return ((Entry<K, V>) values[(start + n) % values.length]).value;
}
/**
* To remove na entry fromthe list
* @return
*/
public V remove() {
V deletedV = (V) values[(start) % values.length];
values[(start) % values.length] = null;
if(start != nextEmpty) {
start = (start + 1) % values.length;
}
shiftList();
return deletedV;
}
/**
* Class Entry
* @author
*
* @param <K>
* @param <V>
*/
private class Entry<K, V> {
protected K key;
protected V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
@Override
public Object[] toArray() {
int currentSize = size();
Object[] arrayList = new Object[currentSize];
if(start == nextEmpty && values[start] == null)
return null;
else
{
int currentIndex = start;
for(int i = 0; i < currentSize; ++i)
{
arrayList[i] = ((Entry)values[currentIndex]).value;
currentIndex = (currentIndex + 1) % values.length;
}
return arrayList;
}
}
/* This method generates a String containing each value in the list. If the
* list is empty it will @return {@code null}.
*/
@SuppressWarnings("unchecked")
public String toString()
{
String s = "";
int currentSize = size();
int currentIndex = start;
for(int i = 1; i < currentSize; ++i)
{
s = s + "(" + ((Entry)values[currentIndex]).key + "," + ((Entry)values[currentIndex]).value + ") -- ";
currentIndex++;
}
return s;
}
}
UnboundedList.java
public class UnboundedList<K extends Comparable<K>,V> extends SimpleBoundedList<K,V> {
public UnboundedList(int bound) {
super(bound);
}
@Override
public boolean add(K key, V value) {
ensureCapacity();
super.add(key, value);
return true;
}
private void ensureCapacity()
{
if (this.size() == this.values.length)
{
Object[] newArray = new Object[values.length * 2];
int currentValue = start;
for (int i = 0; i < values.length; ++i)
{
newArray[i] = values[currentValue];
currentValue = (currentValue + 1) % values.length;
}
start = 0;
nextEmpty = (values.length - 1);
this.values = newArray;
}
}
}
SimpleLinkedList.java
public class SimpleLinkedList<K, V> implements List<K, V> {
private Node head = null;
private Node tail = null;
public SimpleLinkedList()
{
head = null;
tail = null;
}
@Override
public boolean add(K key, V value) {
if (head == null) { // List is empty
Node nn = new Node(key, value);
head = nn;
} else {
Node node = head;
while (node.next != null) {
node = node.next;
}
node.next = new Node(key, value);
}
return true;
}
@Override
public V remove(K key) {
Node currentNode = head;
while(currentNode != null)
{
if(((Node)currentNode.next.value).key == key)
{
Node removed = currentNode.next;
currentNode.next = currentNode.next.next;
return ((Node)(removed.value)).value;
}
currentNode = currentNode.next;
}
return null;
}
@Override
public V remove(int n) {
if (head == null)
return null;
else
{
int intitalPos = 0;
for( Node currentNode = head; currentNode != null; currentNode = currentNode.next, intitalPos += 1 )
{
if ( intitalPos == n)
{
Node removed = head;
head = head.next;
return ((Node)removed.value).value;
}
}
return null;
}
}
@Override
public V remove() {
if(head == null)
return null;
else if(head == tail) {
Node removed = head;
head = null;
tail = null;
return ((Node)removed.value).value;
}
else {
Node removed = head;
head = head.next;
return ((Node)removed.value).value;
}
}
@Override
public V lookup(K key) {
if (head == null)
return null;
Node currentNode = head;
while(currentNode != null)
{
if(((Node)currentNode.next.value).key == key)
{
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
}
@Override
public int size() {
int size = 0;
Node currentNode = head;
while(currentNode.next != null)
{
currentNode = currentNode.next;
size++;
}
return size;
}
@Override
public V get(int n) {
if (head == null)
return null;
else
{
int intitalPos = 0;
for( Node currentNode = head; currentNode != null; currentNode = currentNode.next, intitalPos += 1 )
{
if ( intitalPos == n)
{
return currentNode.value;
}
}
return null;
}
}
private class Node {
protected K key;
protected V value;
protected Node next;
Node(K k, V v) {
key = k;
value = v;
next = null;
}
}
@Override
public Object[] toArray() {
int currentSize = size();
int index = 0;
if(head == null)
return null;
else
{
Object[] arrayList = new Object[currentSize];
for(Node currentNode = head; currentNode != null; currentNode = currentNode.next)
{
arrayList[index] = ((Node)currentNode.next.value).value;
index++;
}
return arrayList;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = head;
while (node != null) {
sb.append("(" + node.key + "," + node.value + ") -- ");
node = node.next;
}
return sb.toString();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.