LinkBack URL
About LinkBacks
What is the difference between ordered and unordered linked list and how to implement unordered linked list to get ordered set?
Last week we had an assignment to create an Unordered Link List using an abstract class. However, now the teacher wants us to implement an Ordered Link List using an interface but I'm not quite sure what I'm supposed to be doing or the difference.
This is my code from last week.
public abstract class DataElement{ public abstract boolean equals(DataElement otherElement); public abstract int compareTo(DataElement otherElement); public abstract void makeCopy(DataElement otherElement); public abstract DataElement getCopy(); }
public class IntElement extends DataElement { protected int number; public IntElement() { number = 0; } public IntElement(int num) { number = num; } public IntElement(IntElement obj) { this.number = obj.getNum(); } public void setNum(int num) { number = num; } public int getNum() { return number; } public boolean equals(DataElement obj) { if (obj == null) return false; if (getClass() != obj.getClass()) return false; IntElement temp = (IntElement)obj; return (number == temp.number); } public int compareTo(DataElement obj) { IntElement temp = (IntElement)obj; if (number < temp.number) return -1; else if (number > temp.number) return 1; else return 0; } public void makeCopy(DataElement obj) { IntElement temp = (IntElement)obj; number = temp.number; } public DataElement getCopy() { DataElement temp = new IntElement(number); return temp; } }
public abstract class LinkedList{ protected class LinkedListNode{ // inner class node definition protected DataElement info; protected LinkedListNode link; } protected LinkedListNode first; //variable to store the address of the first node of the list protected LinkedListNode last; // variable to store the address of the last node of the list protected int count; //variable to store the number of nodes in the list //default constructor //initializes the list to an empty state. //postcondition: first = null, last = null, count = 0 public LinkedList(){ first = null; // last = null; //empty list count = 0; // } //method to determine whether the list is empty //postcondition: returns true if the list is empty; false otherwise public boolean isEmptyList(){ return (count == 0); } //method to initialize the list to an empty state //postcondition: first = null, last = null, count = 0 public void initializeList(){ first = null; last = null; count = 0; } //method to output the data contained in each node public void print(){ if(count == 0){ System.out.println("Cannot print an empty list."); } else{ LinkedListNode pointer = new LinkedListNode(); pointer = first; while(pointer != null) System.out.println(pointer.info.toString() + " "); pointer=pointer.link; } System.out.println(); } //method to return the number of nodes in the list. //postcondition: the value of count is returned public int length(){ return count; } //method to return a reference of the object //containing the data of the first node of the list //precondition: the list must exist and must not be empty. //postcondition: the reference of the object that contains //the info of the first node is returned public DataElement front(){ return first.info.getCopy(); } //Method to return a reference of object containing //the data of the last node of the list. //Precondition: The list must exist and must not be empty. //Postcondition: The reference of the object that //contains the info of the last node //is returned. public DataElement back(){ return last.info.getCopy(); } //Method to insert newItem in the list. //Postcondition: first points to the new list // and newItem is inserted at the // beginning of the list. Also, // last points to the last node and // count is incremented by 1. public void insertFirst(DataElement newItem){ LinkedListNode newNode = new LinkedListNode(); newNode.info = newItem.getCopy(); newNode.link = first; first = newNode; if(last == null){ last = newNode; count++; } } //Method to insert newItem at the end of the list. //Postcondition: first points to the new list and //newItem is inserted at the end //of the list. Also, last points to //the last node and //count is incremented by 1. public void insertLast(DataElement newItem){ LinkedListNode newNode = new LinkedListNode(); newNode.info = newItem.getCopy(); newNode.link = null; if(first == null){ first = newNode; last = newNode; } else{ last.link = newNode; last = newNode; count++; } } //Method to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is found //in the list; false otherwise. public abstract boolean search(DataElement searchItem); //Method to delete deleteItem from the list. //Postcondition: If found, the node containing //deleteItem is deleted from the //list. Also first points to the first //node, last points to the last //node of the updated list, and count //is decremented by 1. public abstract void deleteNode(DataElement deleteItem); }
public abstract class LinkedList{ protected class LinkedListNode{ // inner class node definition protected DataElement info; protected LinkedListNode link; } protected LinkedListNode first; //variable to store the address of the first node of the list protected LinkedListNode last; // variable to store the address of the last node of the list protected int count; //variable to store the number of nodes in the list //default constructor //initializes the list to an empty state. //postcondition: first = null, last = null, count = 0 public LinkedList(){ first = null; // last = null; //empty list count = 0; // } public LinkedList(LinkedList list) { copy(list); } private void copy(LinkedList list) { LinkedListNode pointer; LinkedListNode newNode; if(list.first == null) { first = null; last = null; count = 0; } else { count = list.count; pointer = list.first; first = new LinkedListNode(); first.info = pointer.info.getCopy(); first.link = null; last = first; pointer = pointer.link; while(pointer != null) { newNode = new LinkedListNode(); newNode.info = pointer.info.getCopy(); newNode.link = null; last.link = newNode; last = newNode; pointer = pointer.link; } } } //method to determine whether the list is empty //postcondition: returns true if the list is empty; false otherwise public boolean isEmptyList(){ return (count == 0); } //method to initialize the list to an empty state //postcondition: first = null, last = null, count = 0 public void initializeList(){ first = null; last = null; count = 0; } //method to output the data contained in each node public void print(){ if(count == 0){ System.out.println("Cannot print an empty list."); } else{ LinkedListNode pointer = new LinkedListNode(); pointer = first; while(pointer != null){ System.out.println(pointer.info.toString()); pointer=pointer.link; } } } //method to return the number of nodes in the list. //postcondition: the value of count is returned public int length(){ return count; } //method to return a reference of the object //containing the data of the first node of the list //precondition: the list must exist and must not be empty. //postcondition: the reference of the object that contains //the info of the first node is returned public DataElement front(){ return first.info.getCopy(); } //Method to return a reference of object containing //the data of the last node of the list. //Precondition: The list must exist and must not be empty. //Postcondition: The reference of the object that //contains the info of the last node //is returned. public DataElement back(){ return last.info.getCopy(); } //Method to insert newItem in the list. //Postcondition: first points to the new list // and newItem is inserted at the // beginning of the list. Also, // last points to the last node and // count is incremented by 1. public void insertFirst(DataElement newItem){ LinkedListNode newNode = new LinkedListNode(); newNode.info = newItem.getCopy(); newNode.link = first; first = newNode; if(last == null){ last = newNode; count++; } } //Method to insert newItem at the end of the list. //Postcondition: first points to the new list and //newItem is inserted at the end //of the list. Also, last points to //the last node and //count is incremented by 1. public void insertLast(DataElement newItem){ LinkedListNode newNode = new LinkedListNode(); newNode.info = newItem.getCopy(); newNode.link = null; if(first == null){ first = newNode; last = newNode; } else{ last.link = newNode; last = newNode; count++; } } public void deleteFront() { if(first.link != null) { first = first.link; count--; } else { first = null; last = null; count = 0; } } public void deleteLast() { LinkedListNode pointer = first; if(pointer.link == null) { first = null; last = null; count = 0; } else { while(pointer.link.link != null) pointer = pointer.link; pointer.link = null; last = pointer; count--; } } public void splitMid(LinkedList list) { int stopPoint = list.count / 2; LinkedListNode pointer = null; pointer = list.first.link; for(int i = 0; i < stopPoint; i++) { pointer = pointer.link; } LinkedListNode secondFirst = pointer.link; pointer.link.link = null; } public double average(){ double sum=0; LinkedListNode pointer = new LinkedListNode(); pointer = first; while(first != null){ pointer = first; IntElement temp = (IntElement)pointer.info.getCopy(); sum = sum + temp.getNum(); first = pointer.link; } double average = (sum/59.0); return average; } public double stdDev(double avg){ double stdAvg = avg; double variance = 0; LinkedListNode pointer = new LinkedListNode(); while(first!= null){ pointer = first; IntElement temp = (IntElement)pointer.info.getCopy(); variance = (variance + ((temp.getNum() - stdAvg)*(temp.getNum() - stdAvg))); first = pointer.link; } return (Math.sqrt(variance/59)); } //Method to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is found //in the list; false otherwise. public abstract boolean search(DataElement searchItem); //Method to delete deleteItem from the list. //Postcondition: If found, the node containing //deleteItem is deleted from the //list. Also first points to the first //node, last points to the last //node of the updated list, and count //is decremented by 1. public abstract void deleteNode(DataElement deleteItem); }
public class UnorderedLinkedList extends LinkedList{ public UnorderedLinkedList(){ super(); } public UnorderedLinkedList(UnorderedLinkedList list){ super(list); } //Method to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is found //in the list; false otherwise. public boolean search(DataElement searchItem){ LinkedListNode pointer = new LinkedListNode(); pointer = first; boolean foundData = false; while(pointer != null && !foundData){ if(pointer.info.equals(searchItem) == true){ foundData = true; } else{ pointer = pointer.link; } } return foundData; } //Method to delete deleteItem from the list. //Postcondition: If found, the node containing //deleteItem is deleted from the //list. Also first points to the first //node, last points to the last //node of the updated list, and count //is decremented by 1. public void deleteNode(DataElement deleteItem){ if(count == 0) System.out.println("The list is empty."); else{ if(first.info.equals(deleteItem) == true) { if(first.link == null){ first = null; last = null; count = 0; } else{ first = first.link; count--; if(count == 1){ first.link = null; last = first; } } } else{ LinkedListNode pointer = new LinkedListNode(); pointer = first; while(pointer.info.equals(deleteItem) != true){ pointer = pointer.link; pointer.link = pointer.link.link; //inception if(pointer.link == null){ last = pointer; count--; } } } } } }
This is the main to test every method.
import java.util.Random; public class TestLinkedList{ public static void main(String[] args){ double sum = 0; UnorderedLinkedList list = new UnorderedLinkedList(); Random rand = new Random(); for(int i = 0; i<=59; i++){ int randomNum = rand.nextInt(100)+1; sum += randomNum; list.insertLast(new IntElement(randomNum)); } UnorderedLinkedList copyList = new UnorderedLinkedList(list); //a copy of the linked list to use for avg and std. deviation UnorderedLinkedList copyList2 = new UnorderedLinkedList(list); UnorderedLinkedList copyList3 = new UnorderedLinkedList(list); System.out.println("Printing the list."); list.print(); System.out.println("Deleting the first node."); list.deleteFront(); list.print(); System.out.println("Deleting the last node."); list.deleteLast(); list.print(); System.out.println("Inserting node into the front with a number of 68."); list.insertFirst(new IntElement(68)); list.print(); System.out.println("Inserting node into the back with a number of 75."); list.insertLast(new IntElement(75)); list.print(); System.out.println("Now splitting the list into to two equal lists."); list.splitMid(list); list.print(); System.out.println("The average of the list is: " + copyList.average()); double avg = copyList2.average(); System.out.println("The standard deviation is: " + copyList3.stdDev(avg)); } }
So this leads me to my question.... the teacher gave us these files.
public interface ListInterface { public int size(); // Returns the number of elements on this list. public void add(DataElement element); // Adds element to this list. public boolean remove (DataElement element); // Removes an element e from this list such that e.equals(element) // and returns true; if no such element exists, returns false. public boolean contains (DataElement element); // Returns true if this list contains an element e such that // e.equals(element); otherwise, returns false. public DataElement get(DataElement element); // Returns an element e from this list such that e.equals(element); // if no such element exists, returns null. public String toString(); // Returns a nicely formatted string that represents this list. //---------------------------------------------------------------------------- // The list has a special property called the current position - the position // of the next element to be accessed by getNext during an iteration through // the list. Only reset and getNext affect the current position. //---------------------------------------------------------------------------- public void reset(); // Initializes current position for an iteration through this list, // to the first element on this list. public DataElement getNext(); // Preconditions: The list is not empty // The list has been reset // The list has not been modified since the most recent reset // // Returns the element at the current position on this list. // If the current position is the last element, then it advances the value // of the current position to the first element; otherwise, it advances // the value of the current position to the next element. }
public class LLNode { private LLNode link; private DataElement info; public LLNode(DataElement info) { this.info = info; link = null; } public void setInfo(DataElement info) { this.info = info; } public DataElement getInfo() { return info; } public void setLink(LLNode link) { this.link = link; } public LLNode getLink() { return link; } }
public class RefUnsortedList implements ListInterface { protected int numElements; // number of elements in this list protected LLNode currentPos; // current position for iteration // 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 preceeding location protected LLNode list; // first node on the list public RefUnsortedList() { numElements = 0; list = null; currentPos = null; } public void add(DataElement element) // Adds element to this list at the front. { LLNode newNode = new LLNode(element); newNode.setLink(list); list = newNode; numElements++; } protected void find(DataElement target) // Searches list 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 = list; found = false; while (location != null) { if (location.getInfo().equals(target)) // if they match { found = true; return; } else { previous = location; // move to next node location = location.getLink(); } } } public int size() // Returns the number of elements on this list. { return numElements; } public boolean contains (DataElement element) // Returns true if this list contains an element e such that // e.equals(element); otherwise, returns false. { find(element); return found; } public boolean remove (DataElement element) // Removes an element e from this list such that e.equals(element) // and returns true; if no such element exists, returns false. { find(element); if (found) { if (list == location) list = list.getLink(); // remove first node else previous.setLink(location.getLink()); // remove node at location numElements--; } return found; } public DataElement get(DataElement element) // Returns an element e from this list such that e.equals(element); // if no such element exists, returns null. { find(element); if (found) return location.getInfo().getCopy() ; //we changed this else return null; } public String toString() // Returns a nicely formatted string that represents this list. { LLNode currNode = list; String listString = "List:\n"; while (currNode != null) { listString = listString + " " + currNode.getInfo() + "\n"; currNode = currNode.getLink(); } return listString; } public void reset() // Initializes current position for an iteration through this list, // to the first element on this list. { currentPos = list; } public DataElement getNext() // Preconditions: The list is not empty // The list has been reset // The list has not been modified since most recent reset // // Returns the element at the current position on this list. // If the current position is the last element, then it advances the value // of the current position to the first element; otherwise, it advances // the value of the current position to the next element. { DataElement next = currentPos.getInfo().getCopy(); if (currentPos.getLink() == null) currentPos = list; else currentPos = currentPos.getLink(); return next; } public void clear() { LLNode cur = list.getLink(); //point to second node LLNode prev = list; //point to first node while( cur != null ) { prev.setLink(null); prev = cur; cur = cur.getLink(); } list = null; numElements = 0; currentPos = null; } }//class RefUnsortedList
This is essentially the same thing I wrote, except...probably less sloppy. I still don't understand how we are supposed to implement or what is a ordered list? Would I have to make the RefUnsortedList an interface too, and then implement it into my ordered class? Need opinions, thank you!
edit: Should i even use the example from the teacher, or just keep continuing on mine? Couldn't I just keep using my abstract LinkedList class and just go deeper?
Reply With Quote
Related threads:
