LinkBack URL
About LinkBacks
Having trouble writing insert method for Ordered LinkList.
We are supposed to write an insert method for an ordered link list. I'm working on the method and have most of it written in my OrderedLL class. However, I can't seem to understand how to deal with case 3b. Any help is appreciated!
public class OrderedLL extends UnorderedLinkedList{ public OrderedLL(){ super(); } public OrderedLL(OrderedLL list){ super(list); } public boolean search(DataElement searchItem){ LinkedListNode pointer = new LinkedListNode(); pointer = first; boolean foundData = false; while(pointer != null && !foundData){ if(pointer.info.equals(searchItem) == true || pointer.info.compareTo(searchItem) == 1){ foundData = true; } else{ pointer = pointer.link; } } return foundData; } public boolean insert(DataElement insertItem){ LinkedListNode pointer = new LinkedListNode(); pointer = first; boolean inserted = false; boolean smallest = false; boolean largest = false; while(pointer!=null){ if(pointer.info.compareTo(insertItem) == 1){ smallest = true; break; } else{ pointer = pointer.link; } } while(pointer!=null){ if(pointer.info.compareTo(back()) == -1){ largest = true; pointer = null; } else{ pointer = pointer.link; } } pointer = first; //resets pointer back to default first if(count == 0){ insertFirst(insertItem); inserted = true; } else if(count!= 0 && smallest == true){ insertFirst(insertItem); inserted = true; } else if(count!= 0 && pointer.info.compareTo(insertItem) == -1){ if(largest == true){ insertLast(insertItem); inserted = true; } else{ } } } } }
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 || pointer.info.compareTo(searchItem) == 1){ 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--; } } } } } }
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); }
This is what the powerpoint says...
Approach We first find the place where the new item is supposed to go and then insert it in the list. We use the search algorithm go past the item value to be inserted. We need a current pointer to point to the current node and a previous pointer that points to the node just before current. We have three cases to consider: Case 1 The list is initially empty. The node containing the new item is the only item in the list and thus the first in the list. Use insertFirst method. Case 2 The list is not empty and the new item is smaller than the smallest item in the list. The new item goes at the beginning of the list. Use insertFirst method. Case 3 The list is not empty and the item to be inserted is larger than the first item in the list. The item is to be inserted somewhere in the list. We need to consider two sub cases. Case 3a New item is larger than all items in the list. Then new item is inserted at end of list. Current pointer is null and previous pointer point to last node. Insert after previous, or use insertLast method. Case 3b New item is to be inserted somewhere in the middle of the list. That is insert new item between previous and current pointers.
I feel like I've gotten most of it, but I don't understand how to deal with case 3b?
Reply With Quote
Related threads:
Originally Posted by jps
