Results 1 to 3 of 3
  1. #1
    mxcnrawker is offline Member
    Join Date
    Apr 2012
    Location
    San Jose Ca
    Posts
    16
    Rep Power
    0

    Default 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:

    Java 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

  2. #2
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Insertion Sort with Linked List, Comparing strings

    What does "not working" mean?
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  3. #3
    mxcnrawker is offline Member
    Join Date
    Apr 2012
    Location
    San Jose Ca
    Posts
    16
    Rep Power
    0

    Default 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!

Similar Threads

  1. Replies: 0
    Last Post: 09-25-2012, 04:07 AM
  2. linked list quick sort null pointer exception
    By cherrychives in forum New To Java
    Replies: 6
    Last Post: 05-14-2012, 08:09 AM
  3. Insertion Sort for linked list help?
    By bubtub24 in forum New To Java
    Replies: 3
    Last Post: 11-28-2010, 06:21 AM
  4. [SOLVED] Insertion Sort in Linked List
    By taylorp in forum New To Java
    Replies: 10
    Last Post: 03-27-2009, 12:34 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •