please complete the size function . I have the LinkedListST class below: public
ID: 3752141 • Letter: P
Question
please complete the size function. I have the LinkedListST class below:
public class LinkedListST<Key extends Comparable<Key>, Value extends Comparable<Value>> {
private Node first; // the linked list of key-value pairs
// a helper linked list data type
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty symbol table.
*/
public LinkedListST() {
first = null;
}
/**
* get
*
* Returns the value associated with the given key in this symbol table.
*/
public Value get(Key key) {
if (key == null) throw new NullPointerException("argument to get() is null");
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key))
return x.val;
}
return null;
}
/**
* put
*
* Inserts the specified key-value pair into the symbol table, overwriting the old
* value with the new value if the symbol table already contains the specified key.
* Deletes the specified key (and its associated value) from this symbol table
* if the specified value is null.
*/
public void put(Key key, Value val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
first = new Node(key, val, first);
}
/**
* delete *
* Removes the specified key and its associated value from this symbol table
* (if the key is in this symbol table).
*/
public void delete(Key key) {
if (key == null) throw new NullPointerException("argument to delete() is null");
first = delete(first, key);
}
/* delete helper function
* delete key in linked list beginning at Node x
* warning: function call stack too large if table is large
*
*/
private Node delete(Node x, Key key) {
if (x == null) return null;
if (key.equals(x.key)) {
return x.next;
}
x.next = delete(x.next, key);
return x;
}
public Iterable<Key> keys() {
Queue<Key> theKeys = new Queue<Key>();
for ( Node temp = first; temp != null; temp=temp.next) {
theKeys.enqueue(temp.key);
}
return theKeys;
}
/* you should not modify anything above this line */
/**
* size
* size returns the number of key-value pairs in the symbol table.
* it returns 0 if the symbol table is empty.
*/
public int size () {
return -1; // ToDo 1 fix this
}
Explanation / Answer
public class LinkedListST { private Node first; // the linked list of key-value pairs // a helper linked list data type private class Node { private Key key; private Value val; private Node next; public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } } /** * Initializes an empty symbol table. */ public LinkedListST() { first = null; } /** * get ** Returns the value associated with the given key in this symbol table. */ public Value get(Key key) { if (key == null) throw new NullPointerException("argument to get() is null"); for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; } /** * put *
* Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is null. */ public void put(Key key, Value val) { if (key == null) throw new NullPointerException("first argument to put() is null"); if (val == null) { delete(key); return; } for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); } /** * delete * * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). */ public void delete(Key key) { if (key == null) throw new NullPointerException("argument to delete() is null"); first = delete(first, key); } /* delete helper function * delete key in linked list beginning at Node x * warning: function call stack too large if table is large * */ private Node delete(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { return x.next; } x.next = delete(x.next, key); return x; } public Iterable keys() { Queue theKeys = new Queue(); for (Node temp = first; temp != null; temp = temp.next) { theKeys.enqueue(temp.key); } return theKeys; } /* you should not modify anything above this line */ /** * size * size returns the number of key-value pairs in the symbol table. * it returns 0 if the symbol table is empty. */ public int size() { int count = 0; Node temp = first; while (temp != null) { count++; temp = temp.next; } return count; } }
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.