LinkBack URL
About LinkBacks
[Linked List] Problems deleting items from a linked list
Hello all!
I am having a terrible time trying to figure out how to delete an item from a linked list. I understand that if it is the first item, then you need to get the link to the next item and then assign that to the node so that nothing is no longer pointing to the first item and thus ends up in the garbage. If it's in the middle, then the previous item will link to the item after the item to be deleted to once again be left for garbage. If it's the last then the previous item linking to it should be null and that the node pointing to the last item should now point to the previous one since it is indeed the last item. I cannot figure this out, I've drawn pictures and tried to conceive of possible solutions with no success. I need some help and direction -thanks!
My current results when deleting the item lies in sorting. I call out a for loop that sorts the randomly generated list of strings and then grabs that item for comparison once it finds the smallest it insert it first in a new linked list to be then referenced later. When i call the delete method, it runs but the results is not expected. The new linked list shows the lowest item (i.e. 66) but repeats it over and over again. Thus when the smallest method calls out, its not finding the next smallest, instead it find the smallest which is the first number it found in the first place but never deleted. Ultimately, this leads to the final conclusion that my delete method is not working like it should and its driving me mad trying to figure out. I understand something needs to change in the if statements, but what exactly.
PS: The items within the list are randomly generated integers that are parsed into string to be inserted into the linked list. Everything works fine except when i try and delete a list item.
Please find my code below:
UseStringLog.java
//---------------------------------------------------------------------------- // UseStringLog.java by Dale/Joyce/Weems Chapter 2 // updated by Lee // // Example of applying a brute force sorting routine to the ArrayStringLog //---------------------------------------------------------------------------- import ch2pt2.*; import java.util.Date; import java.util.Random; // add imports as directed by comments below public class UseStringLog { public static void main(String[] args) { final int LOG_SIZE = 10; final int NUM_SIZE = 100; System.out.println("Array: "); // increments the log size and random number size used in the driven method // by multiples of 10 System.out.println("Log Size: " + LOG_SIZE); System.out.println("Random Number Size: " + NUM_SIZE); System.out.println("Average Time: " + ((driven(LOG_SIZE, NUM_SIZE) + driven(LOG_SIZE, NUM_SIZE) + driven(LOG_SIZE, NUM_SIZE)) / 3)); } public static long driven(int numElements, int maxValue) { // declare and instantiate a sampleCopy and sampleSorted string logs StringLogInterface sampleCopy = new LinkedStringLog("Work Array"); StringLogInterface sampleSorted = new LinkedStringLog("Sort Array"); // declare some timing variables startClock and stopClock // don't forget to import java.util.Date prior to UseStringLog long startClock; long stopClock; // declare a variable named elapsedTime of type long // elapsedTime will hold the time differential in milliseconds long elapsedTime; // declare other variables // two String variables named min and rand // since a string log contains methods passing strings, // the int's will need to be converted String min; String rand; int temp; // declare three integer variables named numElements, minValue, and maxValue // set numElements and maxValue to 10000 // set minValue to 1 int minValue = 1; // declare a variable named random of type Random and instantiate it. Random random = new Random(); // Load the string log sample with 10000 random numbers ranging from 1-10000 // don't forget to import java.util.Random prior to UseStringLog for(int i = 0; i < numElements; i++) { rand = Integer.toString(random.nextInt(maxValue - minValue) - minValue + 1); sampleCopy.insert(rand); } // start the clock // instantiate the timer Date().getTime() for startClock startClock = new Date().getTime(); // insert a sorting method here to sort the array of numbers represented // Hint: 1. identify the smallest element in sampleCopy and assign it to min // 2. insert min into sampleSort // 3. delete min from sampleCopy // 4. repeat steps 1-3 until sampleCopy is empty for(int i = 0; i < numElements; i++) { min = sampleCopy.smallest(); sampleSorted.insert(min); sampleCopy.delete(min); } // stop the clock stopClock = new Date().getTime(); // print out the time it took to do the sort in milliseconds elapsedTime = stopClock - startClock; // print out the sample string log with the .toString method System.out.println(sampleCopy.toString()); // print out the sampleSort string log with the .toString method System.out.println(sampleSorted.toString()); return elapsedTime; } }
StringLogInterface.java
//---------------------------------------------------------------------- // StringLogInterface.java by Dale/Joyce/Weems Chapter 2 // // Interface for a class that implements a log of Strings. // A log "remembers" the elements placed into it. // // A log must have a "name". //---------------------------------------------------------------------- package ch2pt2; public interface StringLogInterface { // Precondition: This StringLog is not full. // // Places element into this StringLog. void insert(String element); // Returns true if this StringLog is full, otherwise returns false. boolean isFull(); // Returns the number of Strings in this StringLog. int size(); // Returns true if element is in this StringLog, // otherwise returns false. // Ignores case differences when doing string comparison. boolean contains(String element); // Makes this StringLog empty. void clear(); // Returns the name of this StringLog. String getName(); // Returns a nicely formatted string representing this StringLog. String toString(); /*----------------Newly adden------------------*/ // Returns true if this StringLog is empty, otherwise returns false. boolean isEmpty(); // Returns how many times element occurs in this StringLog. int howMany(String element); // Places element into this StringLog unless an // identical string (case insensitive match) // is already in this StringLog. // // Assumes StringLog not full if insertion required. public boolean uniqInsert(String element); // Deletes one occurence of element from this StringLog, // if possible, and returns true. Otherwise returns false. public boolean delete(String element); // Deletes all occurences of element from this StringLog, // if any, and returns the number of deletions. public int deleteAll(String element); // Precondition: this log contains at least one string // // Returns smallest element in this StringLog public String smallest(); }
LLStringNode.java
//---------------------------------------------------------------------------- // LLStringNode.java by Dale/Joyce/Weems Chapter 2 // // Implements String nodes for a Linked List. //---------------------------------------------------------------------------- package ch2pt2; public class LLStringNode { private String info; private LLStringNode link; public LLStringNode(String info) { this.info = info; link = null; } public void setInfo(String info) // Sets info string of this LLStringNode. { this.info = info; } public String getInfo() // Returns info string of this LLStringNode. { return info; } public void setLink(LLStringNode link) // Sets link of this LLStringNode. { this.link = link; } public LLStringNode getLink() // Returns link of this LLStringNode. { return link; } }
LinkedStringLog.java
//---------------------------------------------------------------------- // LinkedStringLog.java by Dale/Joyce/Weems Chapter 2 // // Implements StringLogInterface using a linked list // of LLStringNode to hold the log strings. //---------------------------------------------------------------------- package ch2pt2; public class LinkedStringLog implements StringLogInterface { protected LLStringNode log; // reference to first node of linked // list that holds the StringLog strings protected String name; // name of this StringLog public LinkedStringLog(String name) // Instantiates and returns a reference to an empty StringLog object // with name "name". { log = null; this.name = name; } public void insert(String element) // Precondition: This StringLog is not full. // // Places element into this StringLog. { LLStringNode newNode = new LLStringNode(element); newNode.setLink(log); log = newNode; } public boolean isFull() // Returns true if this StringLog is full, false otherwise. { return false; } public int size() // Returns the number of Strings in this StringLog. { int count = 0; LLStringNode node; node = log; while (node != null) { count++; node = node.getLink(); } return count; } public boolean contains(String element) // Returns true if element is in this StringLog, // otherwise returns false. // Ignores case difference when doing string comparison. { LLStringNode node; node = log; while (node != null) { if (element.equalsIgnoreCase(node.getInfo())) { return true; } else { node = node.getLink(); } } return false; } public void clear() // Makes this StringLog empty. { log = null; } public String getName() // Returns the name of this StringLog. { return name; } public String toString() // Returns a nicely formatted string representing this StringLog. { String logString = "Log: " + name + "\n\n"; LLStringNode node; node = log; int count = 0; while (node != null) { count++; logString = logString + count + ". " + node.getInfo() + "\n"; node = node.getLink(); } return logString; } /*-----------------HW3_Linked_List_application------------------------*/ public boolean isEmpty() { LLStringNode node = log; if(node == null) { return true; } else { return false; } } public int howMany(String element) { LLStringNode node = log; int count = 0; while(node != null) { if(element.equalsIgnoreCase(node.getInfo())) { count++; } node = node.getLink(); } return count; } public boolean uniqInsert(String element) { if(this.contains(element)) { return false; } else { this.insert(element); return true; } } public boolean delete(String element) { LLStringNode node = log; LLStringNode secondNode; if(element.equalsIgnoreCase(node.getInfo())) { log = node.getLink(); return true; } secondNode = node; node = node.getLink(); while(node != null) { if(element.equalsIgnoreCase(node.getInfo())) { secondNode.setLink(node.getLink()); return true; } node.getLink(); secondNode = node; } return false; } public int deleteAll(String element) { int count = 0; while(this.delete(element)) { count++; } return count; } public String smallest() { LLStringNode node = log; int smallest = Integer.parseInt(node.getInfo()); String small = node.getInfo(); node = node.getLink(); while(node != null) { int compareValue = Integer.parseInt(node.getInfo()); if(compareValue < smallest) { small = node.getInfo(); smallest = compareValue; } node = node.getLink(); } return small; } }
PS I revised my original delete method to see if a new way would work when deleting items, to no luck, it goes into an infinite loop.
Reply With Quote
Related threads:
