# Insertion Sort with Linked List, Comparing strings

• 12-03-2012, 01:06 AM
mxcnrawker
Insertion Sort with Linked List, Comparing strings
I am having a little trouble trying trying to get my insertion sort algorithm to work, I wrote one a few weeks ago with objects using arrays as an input. Now we are working with linked list and trying to use the same analogy, not seem to be working. I tried different ways of working it out and no sign of progress.Any hints or help on this would be really appreciated.

Here is my code:

Code:

```class LinkedListOperations {         // Creating a Node class that will store and reference elements in the list.         private class Node         {                 // List of local fields in the Node class.                 String value;                 Node next;                                 // Creating a constructor taht will initialize the elements in the beginning.                 Node(String val, Node n)                 {                         value = val;                         next = n;                 }                                 // Creaitng a no-args constructor that will intialize elements at the head and tail of the list.                 Node(String val)                 {                         // Calls the first constructor.                         this(val, null);                 }         }                 // List of local fields inthe LinkedListOperations class         private Node head;         private Node tail;                 // Creating a no-args constructor for the LinkedListOperations class         public LinkedListOperations()         {                 head = null;                 tail = null;         }                 // Creating a boolean method that will ensure the list is empty.         public boolean isEmpty()         {                 return head ==  null;         }                 // Creating a method that will determine the size of the list.         // @return: the size of the list         public int size()         {                 // List of local variables in the size method.                 int count = 0;                 Node p = head;                                 // Creating a while loop that will step through all elements in the list.                 while (p != null)                 {                         count++;                         p = p.next;                 }                                 // Returns the number of elements in the list.                 return count;         }                 // Creating a method that will add elements to the head and tail of the list.         public void add(String elmt)         {                 // Adds the first element in the list.                 if (isEmpty())                 {                         head = new Node(elmt);                         tail = head;                 }                         else                         {                                 // Adds the element to the end of the list.                                 tail.next = new Node(elmt);                                 tail = tail.next;                                }         }                 // Creating a method that will add elements in any element in the list.         // @param: position of the element         // @param: element value         // @return: adds elements into list;         public void addAtIndex(int index, String elmt)         {                 // If the list is not big enough, sends an error to the user.                 if (index < 0 || index > size())                 {                         String message = String.valueOf(index);                         throw new IndexOutOfBoundsException(message);                 }                                 // Considers the case if the elemnts are zero.                 if (index == 0)                 {                         // Adds the element at the head.                         head = new Node(elmt, head);                                                 // Makes the last element the first one.                         if (tail == null)                         {                                 tail = head;                         }                                                 return;                 }                                 // Considers the case if the element is in the middle of the list.                 Node pred = head;                                 // Creating a loop that will check through the previous elements.                 for (int k = 1; k <= index - 1; k++)                 {                         pred = pred.next;                 }                                 // Adds in the element at the desired location.                 pred.next = new Node(elmt, pred.next);                                 // Makes sure there are no elements at the end hanging.                 if (pred.next.next == null)                 {                         tail = pred.next;                 }         }                 // Creating a toString method that will display the elements in the list.         // @return: oringinal list of Strings         public String toString()         {                 // Creating the StringBuilder class.                 StringBuilder strBuilder = new StringBuilder();                                 // Creating a reference to the head of the list.                 Node p = head;                                 // Creating a loop that will step through each element in the list.                 while (p != null)                 {                         strBuilder.append(p.value + " ");                         p = p.next;                 }                                 // Returns the list of Strings.                 return strBuilder.toString();         }                 // Creating a method that will remove an element in the list.         // @param: the location of the element         public String remove(int index)         {                 // Ensures that the list contains elements, sends an error message                 if (index < 0 || index > size())                 {                         String message = String.valueOf(index);                         throw new IndexOutOfBoundsException(message);                 }                                 // Creating a reference of the element that is oing to be return.                 String element;                                 // Removes the first element of the array.                 if (index == 0)                 {                         element = head.value;                         head = head.next;                                                 // Nulls the tail if the head is null                         if (head == null)                         {                                 tail = null;                         }                 }                         else                         {                                 // Creates a reference to the head.                                 Node pred = head;                                                                 // Removes the elements in the middle of the list.                                 for (int k = 1; k <= index - 1; k++)                                 {                                         pred = pred.next;                                 }                                                                 // Stores the element found to be returned.                                 element = pred.next.value;                                                                 // Re-routes the link the element being removed.                                 pred.next = pred.next.next;                                                                 // Checks if the pred is the last element.                                 if (pred.next == null)                                 {                                         tail = pred;                                 }                         }                                 // Returns the element found.                 return element;         }                 // Creating a boolean method that will ensure the element has been removed.         public boolean remove(String elmt)         {                 // Checks to make sure that elements are not out of bounds.                 if (isEmpty())                 {                         return false;                 }                                 // Checks to see if the first element has been removed.                 if (elmt.equals(head.value))                 {                         head = head.next;                                                 if (head == null)                         {                                 tail = null;                         }                                                 return true;                 }                                 // Creates a new reference to the head.                 Node pred = head;                                 // Finds the previous element has been removed.                 while (pred.next != null && !pred.next.value.equals(elmt))                 {                         pred = pred.next;                 }                                 // From the result above, eithe null or is the value                 if (pred.next == null)                 {                         return false;                 }                                 // Makes the next element the value.                 pred.next = pred.next.next;                                                 // Checks if the previous one is the last.                 if (pred.next == null)                 {                         tail = pred;                 }                                 return true;         }                 // Creaitng a method that will sort the items in the list.         public Node sortList()         {                 // List of local variables in the sortList method.                 Node unsortedNode;                 Node sortedList = null;                 int scan;                                 // Creating a loop that will go through the whole list.                 for (int index = 1; index < size(); index++)                 {                         // Redirects the unsorteNode variable to the second element in the list.                         unsortedNode = head.next;                                                 // Redriects the scan variable to index.                         scan = index;                                                 // Creating a loop that will go thorught the list and swap values.                         while (scan > 0 && head.value.compareTo(unsortedNode.value) > 0)                         {                                 sortedList = new Node(unsortedNode.value, head);                                 head = head.next;                                 unsortedNode = unsortedNode.next;                                 scan--;                         }                                                 // Switches the values in its correct position.                         head.next = unsortedNode;                 }                                 // Returns the sorted list.                 return sortedList;         }                 // Creating a method that will reverse the order of the list         public Node reverseList()         {                 // Creates a new refernce of the first elements.                 Node p;                 tail = head;                 head = null;                                 // Creating a loop that will adds the elements into the new list.                 while (tail != null)                 {                         p = tail;                         tail = tail.next;                         p.next = head;                         head = p;                 }                                 // Returns the head of the new list.                 return head;         } }```

Thanks again for the support
• 12-03-2012, 12:03 PM
Tolls
Re: Insertion Sort with Linked List, Comparing strings
What does "not working" mean?
• 12-03-2012, 01:02 PM
mxcnrawker
Re: Insertion Sort with Linked List, Comparing strings
No worries, I got it to work earlier, just had to look at it in a different perspective. Thanks!