0

so, everything works through the first iteration (don't know if this is an appropriate term for linked lists, but we just learned arrays) but then it stops. I thought that telling it to continue until position.next != null and increasing the position after every iteration would work but I think I have coded something incorrectly / am not taking something into consideration. I would be greatly obliged if you can offer any advice!

I had one more question I wanted to ask...

I am also writing a method called insertionSort (using insertion sort to sort a linked list). Anyway, I know in an array, you copy the item into a temporary space and then insert it into the sorted list in its appropriate place. I am wondering how I create such a space as with bubble sort my temp. space was merely incorporated as the next node.

Thanks,
Hunter

public class LinkedList
   {
   	
      public Node head;
   
       public LinkedList(int length)
      {
         head = null;
      		
         for (int i = 0; i < length; i ++)
            insert(i);
      	
      }
   
       public LinkedList()
      {
         head = null;
      }
   
       public void clear()
      {
         head = null;
      }
   
       public void insert(int n)
      {
         Node current = new Node(n);
      
         current.next = head;
      
         head = current;
      }
   
       public void insert(Node n, int index)
      {
         Node previous, current;
      
         Node nnode = new Node(-10);
         nnode.next = head;
      
         previous = nnode;
         current = head;
      
         while (current != null && index > 0)
         {
            current = current.next;
            previous = previous.next;
            index --;
         }
      
         if (previous == nnode)
         {
            n.next = head;
            head = n;
         }
         else
         {
            previous.next = n;
            n.next = current;
         }
      }
   

       public void delete(int index)
      {
         int current;
         Node currentnode = head;
      
         for (current = index; current > 1; current --) 
            currentnode = currentnode.next;
      	
         if (currentnode == head)
            head = head.next;
         else
            currentnode.next = currentnode.next.next;
      }
   
       public Node getNode(int index)
      {
         Node nnode = new Node(-10);
         nnode.next = head;
      
         Node current = head;
         while(current.next != null && index > 0)
         {	current = current.next;
            index --;
         
         }
      	
         return current;
      }
   
       public int getVal(int index)
      {
         int current;
         Node currentnode = head;
      
         for (current = index; current > 0; current --) 
            currentnode = currentnode.next;
      	

         return currentnode.getVal();
      }
   
       public void print()
      {
         System.out.println();
      
         head.print();
      }
   
       private void swap(Node pa, Node a, Node pb, Node b)
      {
         Node temp = b.next;
         pa.next = b;
         if (a.next != b)
         {
            b.next = a.next;
            pb.next = a;
         }
         else
            b.next = a;
      	
         a.next = temp;
      }
   
       public void selectionSort()
      {
         Node current, a, previous, position;
         position = new Node(0);
         position.next = head;
         head = position;
      
         while (position.next  != null)
         {	
            current = previous = position.next;
            a = position.next;
            while(a != null)
            {
               if (a.getVal() < current.getVal())
               {
                  current = a;
                  while(previous.next != current)
                     previous = previous.next;
               }
               a = a.next;
            }
         
            if (current != previous)
            {
               Node t = position.next;
               swap(position, t, previous, current);
            }
            position = position.next;
         }
         head = head.next;
      }

      public void bubbleSort()
      {
         Node current, a, previous, position;
         position = new Node(0);
         position.next = head;
         head = position;
      
         while (position.next != null)
         {  current = position.next;
          previous = position;
            a = current.next;
            while(a != null)
            {
               if (a.getVal() < current.getVal())
               {
                  Node temp = a.next;
                  a.next = previous.next;
                  previous.next = current.next;
                  current.next = temp; 
						
	previous = a;
	a = temp;
               }
                else
                  {
	a = a.next;
                 current = current.next;
	previous = previous.next;
	}
							               
            }	
             position = position.next;
         }
         head = head.next;
      }
2
Contributors
1
Reply
6
Views
9 Years
Discussion Span
Last Post by cms271828
0

Its simple, I don't see the point for all that code, and I'm not sure why your class is called LinkedList, theres already a LinkedList in the java.util package.
I've just written the code below, might be a couple of bugs in it, I haven't tested it, but thats how I would do it.

import java.util.*;

public class BubbleSort
{
    public static void main(String[] args)
    {
         LinkedList items=new LinkedList();
         // add all Integer elements to items

         bubbleSort(items);
    }

    public void bubbleSort(LinkedList items)
    {
         for(int sort=1;sort<items.getSize();sort++)
         {
             singleSort(items);
         }
    }

    public void singleSort(LinkedList  items)
    {
        for(int item=0;item<items.getSize()-1;item++)
        {
             Integer left=(Integer)items.get(item);
             Integer right=(Integer)items.get(item+1);

            if(left.intValue() > right.intValue()) swap(items, item+1);
        }
    }

    public void swap(LinkedList items,int right_index)
    {
         Integer right=items.remove(right_index);
         items.add(right_index-1,right);
    }
}

In fact, there is a sort method available that you can use, I think you need to use comparator, or comparable, but from a developers view point, thats how you would sort a collection.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.