The following list classes (SimpleBoundedList<K, V>, SimpleLinkedList<K, V>, and
ID: 3827924 • 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
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;
public SimpleBoundedList(int bound) {
values = new Object[bound];
}
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;
}
public V remove(K key) {
return null;
}
public V lookup(K key) {
return null;
}
public V remove(int n) {
return null;
}
public int size() {
return 0;
}
public V get(int n) {
return null;
}
public V remove() {
return null;
}
public Object[] toArray() {
return null;
}
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];
// 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() {
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();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.