Object-Oriented Data Structures using Java, 4th edition Nell Dale, Daniel T. Joyce, Chip Weems Chapter 5 Exercise 31

Create a new collection class named SortedLinkedCollection that implements a collection using a sorted linked list. include a tostring method as described in exercise 30a. Include a test driver application that demonstrates your class works correctly.

package ch05.collections; import support.LLNode; public class LinkedCollection implements CollectionInterface { protected LLNode collection;// reference to the front of this collection protected int numElements = 0; // number of elements in this collection // set by find method protected boolean found; // true if element found, else false protected LLNode location; // node containing element, if found protected LLNode previous; // node preceding location public LinkedCollection() { numElements = 0; collection = null; } public boolean add(T element) // Adds element to this collection. { LLNode newNode = new LLNode(element); newNode.setLink(collection); collection = newNode; numElements++; return true; } protected void find(T target) // Searches collection for an occurence of an element e such that // e.equals(target). If successful, sets instance variables // found to true, location to node containing e, and previous // to the node that links to location. If not successful, sets // found to false. { location = collection; found = false; while (location != null) { if (location.getInfo().equals(target)) // if they match { found = true; return; } else { previous = location; location = location.getLink(); } } } public int size() // Returns the number of elements on this collection. { return numElements; } public boolean contains (T target) // Returns true if this collection contains an element e such that // e.equals(target); otherwise, returns false. { find(target); return found; } public boolean remove (T target) // Removes an element e from this collection such that e.equals(target) // and returns true; if no such element exists, returns false. { find(target); if (found) { if (collection == location) collection = collection.getLink(); // remove first node else previous.setLink(location.getLink()); // remove node at location numElements--; } return found; } public T get(T target) // Returns an element e from this collection such that e.equals(target); // if no such element exists, returns null. { find(target); if (found) return location.getInfo(); else return null; } public boolean isEmpty() // Returns true if this collection is empty; otherwise, returns false. { return (numElements == 0); } public boolean isFull() // Returns true if this collection is full; otherwise, returns false. { return false; // Linked implementation is never full } }

************************************************************************************************

package ch05.collections;

public interface CollectionInterface { boolean add(T element); // Attempts to add element to this collection. // Returns true if successful, false otherwise.

T get(T target); // Returns an element e from this collection such that e.equals(target). // If no such e exists, returns null.

boolean contains(T target); // Returns true if this collection contains an element e such that // e.equals(target); otherwise returns false.

boolean remove (T target); // Removes an element e from this collection such that e.equals(target) // and returns true. If no such e exists, returns false.

boolean isFull(); // Returns true if this collection is full; otherwise, returns false.

boolean isEmpty(); // Returns true if this collection is empty; otherwise, returns false. int size(); // Returns the number of elements in this collection. }

**********************************************************************************************************************************8

package support;

public class LLNode { protected LLNode link; protected T info; public LLNode(T info) { this.info = info; link = null; } public void setInfo(T info){ this.info = info;} public T getInfo(){ return info; } public void setLink(LLNode link){this.link = link;} public LLNode getLink(){ return link;} }