Each linked list node must have three fields (instead of the two in a normal lin
ID: 3889597 • Letter: E
Question
Each linked list node must have three fields (instead of the two in a normal linked list node): the object being stored, its key, and the next reference.
The nodes in the linked list are kept in order of increasing key value. For example, the object with key "abc" must be stored in a node that is before any node with key "xyz". Keys will be unique. Keys are compared using the String.compareToIgnoreCase method of the class String. This method returns 0 if the two strings are equal, a negative number if this string is less than the argument, and a positive number otherwise.
You must implement three classes:
the KeyedNode class as a private class of OrderedLinkedList,
the OrderedLinkedList class, and
another class called AddressList that implements an address book similar to what might be found in your phone.
The AddressList is used for testing only.
The OrderedLinkedList class must provide at least the following methods:
A no-arguments constructor public OrderedLinkedList() class to create an empty ordered linked list.
int size(); Returns the number of elements in the linked list.
E add(String key, E value); If the list does not already contain the given key, the key and value are added to the linked list, and add returns null.
Otherwise, the existing object with the given key is replaced with the new object (and the new key), and add returns the old (removed) object.
Iterator iterator(); a standard iterator method, which gives an iterator that returns each of the elements in turn (do not implement the remove() method of the iterator).
String toString(); a standard toString method, which uses the iterator or a foreach loop to get all the elements in the iterator. The string representation of the orderered linked list should show all the elements as "(key1,element1),(key2,element2)..."
Adding an object to the linked list must add it at the correct position.
The address book class can provide a user interface that allows a user to:
add a (name, telephone number) pair into the address book. The name is used as the key. If the name replaces a pre-existing name, print an appropriate message.
search for a name in the address book, printing either the name and telephone number, or reporting that the name is not in the address book. This code should use the iterator.
display the contents of the entire address book, by calling addressBook.toString();
You should define a private inner class (in your address class) to store whatever values you want in your address book. The values should include names and telephone numbers, but may have more information, such as email addresses.
It will probably be a good idea for you to write a toString() method for this private inner class.
The details of the user interface are up to you. At the very least, you could print a prompt and have a user enter the command (one of the strings "add", "find", or "print"), then ask for the appropriate parameters for each. Or if you prefer, you can open a window to get the input from the user and report on the results.
Explanation / Answer
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An ordered linked list of E's where each node has a key that determines the ordering.
*/
public class OrderedLinkedList<E> implements Iterable<E> {
/**
* Instantiates a new ordered linked list.
*/
public OrderedLinkedList() {
}
/**
* Instantiates a new ordered linked list with null payload elements for keys passed in.
*
*/
public OrderedLinkedList(String... keys) {
for (String key : keys) {
this.add(key, null);
}
}
@Override
public String toString() {
StringBuffer result = new StringBuffer("(");
KeyedNode current = this.head;
while (current != null) {
result.append(current.key);
result.append(",");
current = current.next;
}
// if there are any elements in the list
if (current != this.head) {
// chop off the last char and put ")" in its place
result.setCharAt(result.length() - 1, ')');
} else {
result.append(")");
}
return result.toString();
}
/**
* A node of the ordered linked list.
*/
class KeyedNode {
/**
* The payload.
*/
E object;
/**
* The next node.
*/
KeyedNode next;
/**
* The ordering key.
*/
String key = null;
/**
* Instantiates a new keyed node.
*/
public KeyedNode(E object, String key) {
super();
this.object = object;
this.key = key;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return key;
}
}
/**
* The head of the list.
*/
KeyedNode head = null;
/**
* The number of elements in the list.
*/
int count = 0;
public int size() {
return count;
}
/**
* Adds the value E to the linked list.
*/
public E add(String insertionKey, E insertionValue) {
KeyedNode newNode = new KeyedNode(insertionValue, insertionKey);
E result = null; // the value to return
if (head == null) { // the list is empty
this.head = newNode; // set a new KeyedNode as the head
count++;
return null; // there is clearly no element being replaced
} else if (insertionKey.compareToIgnoreCase(this.head.key) <= 0) {
// insert at beginning of list
KeyedNode oldFirst = this.head;
this.head = newNode;
newNode.next = oldFirst;
} else { // insert after beginning of list
KeyedNode current = this.head;
// advance head while there is a next element and the insertion key
// is "bigger or equal" to the key of the next element
while (current.next != null && insertionKey.compareToIgnoreCase(current.next.key) > 0) {
assert current.next.key != null;
current = current.next;
}
// set the newNode to point to the element after the insertion point
newNode.next = current.next;
// set the node before the insertion point to point to the new node
current.next = newNode;
}
// see if the node after the newly inserted one has the same key
if (newNode.next != null && newNode.next.key.compareToIgnoreCase(insertionKey) == 0) {
// return the value of the duplicate
result = newNode.next.object;
// set the newly inserted node to point to whatever comes after the duplicate
newNode.next = newNode.next.next;
} else {
count++;
}
return result;
}
public E find(String key) {
KeyedNode current = head;
while (current != null) {
if (current.key.equalsIgnoreCase(key)) {
return current.object;
}
current = current.next;
}
return null;
}
public E get(int position) {
KeyedNode current = head;
for (int i = 0; current != null; i++) {
if (i == position)
return current.object;
current = current.next;
}
return null;
}
class OrderedLinkedListIterator implements Iterator<E> {
private KeyedNode currentNode = head;
public boolean hasNext() {
return (currentNode != null);
}
public E next() {
if (hasNext()) {
E value = currentNode.object;
currentNode = currentNode.next;
return value;
} else {
throw new NoSuchElementException();
}
}
public void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<E> iterator() {
return new OrderedLinkedListIterator();
}
}
--------------------------------------------------------------------------------------
OrderedLinkedListTest.java
-------------------------------------------------------
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
public class OrderedLinkedListTest {
@Before
public void setUp() throws Exception {
}
@Test
public void testEmptyList() {
OrderedLinkedList<Object> list = new OrderedLinkedList<Object>(
);
assertNull(list.get(0));
}
@Test
public void testInsertingIntoEmptyList() {
OrderedLinkedList<String> list = new OrderedLinkedList<String>();
list.add("tony", "tonyValue");
assertTrue(list.get(0).equals("tonyValue"));
}
@Test
public void testInsertingAtBeginningOfList() {
OrderedLinkedList<Object> list = new OrderedLinkedList<Object>();
list.add("paul", "paulValue");
list.add("norris", "norrisValue");
list.add("marion", "marionValue");
list.add("linda", "lindaValue");
assertTrue(list.get(0).equals("lindaValue"));
assertTrue(list.get(1).equals("marionValue"));
assertTrue(list.get(2).equals("norrisValue"));
assertTrue(list.get(3).equals("paulValue"));
}
@Test
public void testInsertingAfterBeginningOfList() {
OrderedLinkedList<Object> list = new OrderedLinkedList<Object>();
list.add("norris", "norrisValue");
list.add("paul", "paulValue");
assertTrue(list.get(0).equals("norrisValue"));
assertTrue(list.get(1).equals("paulValue"));
}
@Test
public void testInsertingDupilcates() {
OrderedLinkedList<String> list = new OrderedLinkedList<String>();
list.add("joe", "joeValue");
list.add("john", "johnOriginal");
list.add("leo", "leoOriginal");
list.add("leo", "leoReplacement");
list.add("tyler", "tylerValue");
list.add("john", "johnReplacement");
assertTrue(list.get(0).equals("joeValue"));
assertTrue(list.get(1).equals("johnReplacement"));
assertTrue(list.get(2).equals("leoReplacement"));
assertTrue(list.get(3).equals("tylerValue"));
}
@Test
public void testFind() {
OrderedLinkedList<String> list = new OrderedLinkedList<String>();
list.add("paul", "paulValue");
list.add("norris", "norrisValue");
list.add("marion", "marionValue");
list.add("linda", "lindaValue");
assertTrue(list.find("paul").equals("paulValue"));
assertTrue(list.find("linda").equals("lindaValue"));
assertNull(list.find("jerry"));
}
@Test
public void testGet() {
OrderedLinkedList<String> list = new OrderedLinkedList<String>();
list.add("paul", "paulValue");
list.add("norris", "norrisValue");
list.add("marion", "marionValue");
list.add("linda", "lindaValue");
assertTrue(list.get(0).equals("lindaValue"));
assertTrue(list.get(3).equals("paulValue"));
}
@Test
public void testSize() {
OrderedLinkedList<String> list = new OrderedLinkedList<String>();
assertEquals(0, list.size());
list.add("joe", "joeValue");
assertEquals(1, list.size());
list.add("john", "johnOriginal");
assertEquals(2, list.size());
list.add("leo", "leoOriginal");
assertEquals(3, list.size());
list.add("leo", "leoReplacement");
assertEquals(3, list.size());
list.add("tyler", "tylerValue");
assertEquals(4, list.size());
list.add("john", "johnReplacement");
assertEquals(4, list.size());
}
}
------------------------------------------------------------------------------------
AddressBook.java
------------------------------------------------
import java.util.Scanner;
public class AddressBook {
class AddressBookEntry{
String name;
String telNumber;
public AddressBookEntry(String name, String telNumber) {
super();
this.name = name;
this.telNumber = telNumber;
}
@Override
public String toString() {
return "(" + name + ", " + telNumber + ")";
}
}
OrderedLinkedList<AddressBookEntry> entries = new OrderedLinkedList<AddressBookEntry>();
public static void main(String[] args) {
AddressBook addressBook = new AddressBook();
System.out.println("Starting program, address book is empty. ");
Scanner scan = new Scanner(System.in);
boolean quit = false;
while (!quit) {
System.out.print("enter one of: add, find, print, quit: ");
String command = scan.nextLine();
if(command.equals("add")){
System.out.println(" you chose the add option");
addressBook.addEntry(scan);
System.out.println("The address book has " + addressBook.entries.size()
+ " " + ((addressBook.entries.size() == 1)? "entry" : "entries")
+ " ");
} else if (command.equals("find")){
System.out.println(" you chose the find option");
addressBook.findEntry(scan);
} else if (command.equals("print")){
System.out.println(" you chose the print option");
addressBook.print(scan);
} else if (command.equals("quit")){
System.out.println("Quitting...");
quit = true;
}
else {
System.out.println("That's not a valid option!!! ");
}
}
}
private void addEntry(Scanner scan){
System.out.print("enter name to add: ");
String name = scan.nextLine();
System.out.print("enter telephone number for '" + name + "': ");
String telNumber = scan.nextLine();
System.out.println("'" + name + "' added to telephone book, with number "
+ " " + telNumber);
entries.add(name, new AddressBookEntry(name, telNumber));
}
private void findEntry(Scanner scan){
System.out.print("--enter name to find.");
String name = scan.nextLine();
AddressBookEntry entry = entries.find(name);
if(entry != null) {
System.out.println("Entry found!");
System.out.println("name: " + entry.name);
System.out.println("tel number: " + entry.telNumber + " ");
}
}
private void print(Scanner scan){
System.out.println("--------------------------");
System.out.println("---Address Book Entries---");
System.out.println("--------------------------" + " ");
for(AddressBookEntry entry : entries){
System.out.println(entry.toString());
}
System.out.println("--------------------------" + " ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.