Question: I need help with the following Java code. Implement all missing methods of SortedLinkedDictionary.java . You are allowed to throw UnsupportedOperationException from remove methods of
I need help with the following Java code.
Implement all missing methods of SortedLinkedDictionary.java . You are allowed to throw UnsupportedOperationException from remove methods of both iterators.
/**
*An interface for a dictionary with distinct search keys.
*/
import java.util.Iterator;
public interface DictionaryInterface
{
/**
* Adds a new entry to this dictionary. If the given search key already exists
* in the dictionary, replaces the corresponding value.
*
* @param key
* An object search key of the new entry.
* @param value
* An object associated with the search key.
* @return Either null if the new entry was added to the dictionary or the
* value that was associated with key if that value was replaced.
*/
public V add(K key, V value);
/**
* Removes a specific entry from this dictionary.
*
* @param key
* An object search key of the entry to be removed.
* @return Either the value that was associated with the search key or null if
* no such object exists.
*/
public V remove(K key);
/**
* Retrieves from this dictionary the value associated with a given search key.
*
* @param key
* An object search key of the entry to be retrieved.
* @return Either the value that is associated with the search key or null if
* no such object exists.
*/
public V getValue(K key);
/**
* Sees whether a specific entry is in this dictionary.
*
* @param key
* An object search key of the desired entry.
* @return True if key is associated with an entry in the dictionary.
*/
public boolean contains(K key);
/**
* Creates an iterator that traverses all search keys in this dictionary.
*
* @return An iterator that provides sequential access to the search keys in
* the dictionary.
*/
public Iterator
/**
* Creates an iterator that traverses all values in this dictionary.
*
* @return An iterator that provides sequential access to the values in this
* dictionary.
*/
public Iterator
/**
* Sees whether this dictionary is empty.
*
* @return True if the dictionary is empty.
*/
public boolean isEmpty();
/**
* Gets the size of this dictionary.
*
* @return The number of entries (key-value pairs) currently in the dictionary.
*/
public int getSize();
/** Removes all entries from this dictionary. */
public void clear();
} // end DictionaryInterface
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* A class that implements a dictionary by using a sorted linked chain. The
* dictionary has distinct search keys.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public class SortedLinkedDictionary
{
private Node firstNode; // Reference to first node of chain
private int numberOfEntries;
public SortedLinkedDictionary()
{
initializeDataFields();
} // end default constructor
public V add(K key, V value)
{
V result = null;
// Search chain until you either find a node containing key
// or locate where it should be
Node currentNode = firstNode;
Node nodeBefore = null;
while ((currentNode != null) && (key.compareTo(currentNode.getKey()) > 0))
{
nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
if ((currentNode != null) && key.equals(currentNode.getKey()))
{
// Key in dictionary; replace corresponding value
result = currentNode.getValue(); // Get old value
currentNode.setValue(value); // Replace value
} else // Key not in dictionary; add new node in proper order
{
// Assumes key and value are not null
Node newNode = new Node(key, value); // Create new node
if (nodeBefore == null)
{ // Add at beginning (includes empty dictionary)
newNode.setNextNode(firstNode);
firstNode = newNode;
} else // Add elsewhere in non-empty list
{
newNode.setNextNode(currentNode); // currentNode is after new node
nodeBefore.setNextNode(newNode); // nodeBefore is before new node
} // end if
numberOfEntries++; // Increase length for both cases
} // end if
return result;
} // end add
/*
* < Implementations of other methods in DictionaryInterface. > . . .
*/
private class Node
{
private K key;
private V value;
private Node next;
/*
* < Constructors and the methods getKey, getValue, setValue, getNextNode, and
* setNextNode are here. There is no setKey. > . . .
*/
} // end Node
//Since iterators implement Iterator, methods must be public
private class KeyIterator implements Iterator
{
private Node nextNode;
private KeyIterator() { nextNode = firstNode; } // end default constructor
public boolean hasNext() { return nextNode != null; } // end hasNext
public K next()
{
K result;
if (hasNext())
{
result = nextNode.getKey();
nextNode = nextNode.getNextNode();
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end KeyIterator
} // end SortedLinkedDictionary
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help