JAVA

Implement the LinkedSortedList 1. The list must implement the ListInterface and meet all the specifications 2. The list must also ensure that T is a type that extends Comparable add(T element) will insert the element in the appropriate place to preserve an ascending order of the data find(T element) the private method is defined and used to help during removal, while not contained in the interface, it should be implemented all methods should be implemented, no default stub code should be included.

Comment code appropriately and give a short explanation of your add/remove/find algorithms

Include a comprehensive tester that includes a variety of scenarios. While exhaustive testing is not required (testing that includes all possible outcomes), comprehensive exploratory testing is.

LinkedUnsortedList Class

package ch06.lists;

import support.LLNode;

public class LinkedUnsortedList> implements ListInterface {

LLNode list; LLNode current; int numberOfElements;

public LinkedUnsortedList() { numberOfElements = 0; list = null; current = null; }

@Override public int size() { // TODO Auto-generated method stub return numberOfElements; }

@Override public void add(T element) { // TODO Auto-generated method stub LLNode newNode = new LLNode(element); newNode.setLink(list); list = newNode; numberOfElements++; }

@Override public boolean contains(T element) { // TODO Auto-generated method stub return (find(element) != null); }

@Override public boolean remove(T element) { // TODO Auto-generated method stub

LLNode loc = find(element);

if (loc != null) { if (loc.getInfo().compareTo(element) == 0) { list = loc.getLink(); loc.setLink(null); } else { LLNode temp = loc.getLink(); loc.setLink(loc.getLink().getLink()); temp.setLink(null); }

numberOfElements--; return true; }

return false; }

@Override public T get(T element) { // TODO Auto-generated method stub LLNode loc = find(element);

if (loc != null) { if (loc.getInfo().compareTo(element) == 0) return loc.getInfo(); else return loc.getLink().getInfo(); }

return null; }

@Override public void reset() { // TODO Auto-generated method stub current = list;

}

@Override public T getNext() { // TODO Auto-generated method stub T returnedInfo; if (current == null) return null;

returnedInfo = current.getInfo(); // move but first check if last node if (current.getLink() == null) reset(); else current = current.getLink();

System.out.println("Info to return: " + returnedInfo); return returnedInfo; }

public LLNode find(T element) {

//this implementation aims to find the previous node LLNode loc; loc = list;

while (loc != null) { // check if it's the first node if (loc.getInfo().compareTo(element) == 0) return loc; if (loc.getLink() != null) if (loc.getLink().getInfo().compareTo(element) == 0) return loc; loc = loc.getLink();

}

return loc; }

}

List Interface

package ch06.lists;

public interface ListInterface {

public int size(); public void add(T element); public boolean contains(T element); public boolean remove(T element); public T get(T element); public String toString(); public void reset(); public T getNext();

}

LLNode Class

package support;

public class LLNode {

private LLNode link; private T info;

public LLNode getLink() { return link; }

public void setLink(LLNode link) { this.link = link; }

public T getInfo() { return info; }

public void setInfo(T info) { this.info = info; }

public LLNode(T info) { this.info = info; this.link = null; }

}

List Tester Java

package ch06; import ch06.lists.*; import support.LLNode;

public class ListTester {

public static void main(String[] args) { // TODO Auto-generated method stub

// ArrayUnsortedList nameList = new ArrayUnsortedList(); LinkedUnsortedList nameList = new LinkedUnsortedList(); /* for (int i = 0; i < 15; i++) nameList.add("Anna"); */

nameList.add("Anna"); nameList.add("Zoe"); nameList.add("Brad");

System.out.println(nameList); nameList.add("Michael"); System.out.println(nameList); System.out.println("Size of list: " + nameList.size());

if (nameList.find("L") != null) System.out.println(nameList.find("L").getInfo());

System.out.println("Contains Zoe: " + nameList.contains("Zoe")); System.out.println("Contains Anna: " + nameList.contains("Anna")); System.out.println("Contains Michael: " + nameList.contains("Michael")); System.out.println("Contains Joe: " + nameList.contains("Joe"));

System.out.println("Get Zoe: " + nameList.get("Zoe")); System.out.println("Get Anna: " + nameList.get("Anna")); System.out.println("Get Michael: " + nameList.get("Michael")); System.out.println("Get Joe: " + nameList.get("Joe"));

nameList.reset(); System.out.println("Next name is [Michael]: " + nameList.getNext());

LLNode michael = nameList.find("Michael"); System.out.println("Michael's next node is: " + michael.getLink().getInfo());

System.out.println("Remove Michael"); nameList.remove("Michael"); System.out.println(nameList); System.out.println("Size of list: " + nameList.size());

nameList.reset(); System.out.println("Next name is [Brad]: " + nameList.getNext()); System.out.println("Next name is [Zoe]: " + nameList.getNext()); System.out.println("Next name is [Anna]: " + nameList.getNext()); System.out.println("Next name is [Brad]: " + nameList.getNext());

System.out.println("Michael's next node is: " + michael.getLink().getInfo()); System.exit(1);

System.out.println("Size of list: " + nameList.size());

System.out.println(nameList.get("Zoe"));

String foundName = nameList.get("Brad"); System.out.println(foundName);

System.out.println(nameList.get("Matthew"));

if (nameList.get("Justin") == null) System.out.println("Name not found");

if (!nameList.contains("Justin")) System.out.println("Name not found");

nameList.reset(); String nextName = nameList.getNext(); System.out.println("Next name is [Anna]: " + nextName); nextName = nameList.getNext(); System.out.println("Next name is [Brad]: " + nextName); nextName = nameList.getNext(); System.out.println("Next name is [Zoe]: " + nextName); nextName = nameList.getNext(); System.out.println("Next name is [??]: " + nextName); nextName = nameList.getNext(); nextName = nameList.getNext(); nextName = nameList.getNext(); nextName = nameList.getNext(); nextName = nameList.getNext(); nextName = nameList.getNext(); nextName = nameList.getNext(); }

}