Register to reply

Using the Insertion Sort algorithm on a linked list

by dudeface
Tags: insertion sort, java, linked lists
Share this thread:
dudeface
#1
May22-11, 08:58 AM
P: 1
1. The problem statement, all variables and given/known data
Hi there, I wish this wasn't my first post but unfortunately, it is. I will try to contribute later in the semester when my workload is less.

On to the topic, the problem is I have to implement the insertion sort algorithm on a linked list. I have the algorithm for Java (the language we have been taught) that works for an array. Yet for some reason I am having incredible difficulty translating it to a linked list.

I have tried many different styles of implementing this (for example traversing the list iteratively vs recursively) but have gotten frustrated and decided to start from scratch.
Once again I have gotten stuck, so could anyone tell me if I'm even going in the right direction?

Here is my most recent attempt at a solution
public void sort(LList list){
int i, j = 1;
Node toAdd = null;
Node temp = null;
Node curr=null;
for (i = 2; i <= list.length; i++)
{
temp = list.getNodeAt (i-1);
curr = list.getNodeAt (i);
if (curr.data < temp.data)
{
list.remove (i);
while (j <= i)
{
toAdd = list.getNodeAt(j);
if (curr.data <= list.getNodeAt(j).data)
list.add (j-1, curr.data);
list.display (list.firstNode);
System.out.println ();
j++;
}
}
}
}

It extends a class called LList that I have defined as follows:
public class LList//implements ListInterface
{
public Node firstNode; // reference to first node
public int length; // number of entries in list
public LList ()
{
clear ();
} // end default constructor


public final void clear ()
{
firstNode = null;
length = 0;
} // end clear


public boolean add (int newEntry)
{
Node newNode = new Node (newEntry);
if (isEmpty ())
firstNode = newNode;
else // add to end of nonempty list
{
Node lastNode = getNodeAt (length);
lastNode.next = newNode; // make last node reference new node
} // end if
length++;
return true;
} // end add


public boolean add (int newPosition, int newEntry)
{
boolean isSuccessful = true;
if ((newPosition >= 1) && (newPosition <= length + 1))
{
Node newNode = new Node (newEntry);
if (isEmpty () || (newPosition == 1)) // case 1
{
newNode.next = firstNode;
firstNode = newNode;
}
else // case 2: list is not empty
// and newPosition > 1
{
Node nodeBefore = getNodeAt (newPosition - 1);
Node nodeAfter = nodeBefore.next;
newNode.next = nodeAfter;
nodeBefore.next = newNode;
} // end if
length++;
}
else
isSuccessful = false;
return isSuccessful;
} // end add


public void display (Node firstNode)
{
Node currentNode = firstNode;
while (currentNode != null)
{
System.out.println (currentNode.data);
currentNode = currentNode.next;
} // end while
} // end display


public boolean isEmpty ()
{
boolean result;
if (length == 0)
{
assert firstNode == null;
result = true;
}
else
{
assert firstNode != null;
result = false;
} // end if
return result;
} // end isEmpty



public boolean replace (int givenPosition, int newEntry)
{
boolean isSuccessful = true;
if ((givenPosition >= 1) && (givenPosition <= length))
{
assert !isEmpty ();
Node desiredNode = getNodeAt (givenPosition);
desiredNode.data = newEntry;
}
else
isSuccessful = false;
return isSuccessful;
} // end replace


public int getEntry (int givenPosition)
{
int result = 0; // result to return
if ((givenPosition >= 1) && (givenPosition <= length))
{
assert !isEmpty ();
result = getNodeAt (givenPosition).data;
} // end if
return result;
} // end getEntry


public int remove (int givenPosition)
{
int result; // return value
if ((givenPosition >= 1) && (givenPosition <= length))
{
assert !isEmpty ();
if (givenPosition == 1) // case 1: remove first entry
{
result = firstNode.data; // save entry to be removed
firstNode = firstNode.next;
}
else // case 2: givenPosition > 1
{
Node nodeBefore = getNodeAt (givenPosition - 1);
Node nodeintoRemove = nodeBefore.next;
Node nodeAfter = nodeintoRemove.next;
nodeBefore.next = nodeAfter; // disconnect the node to be removed
result = nodeintoRemove.data; // save entry to be removed
} // end if
length--;
} // end if


return result = 0; // return removed entry, or
// null if operation fails
} // end remove


public boolean isFull () // should ALWAYS return false
{
return false;
}


public boolean contains (int anEntry)
{
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null))
{
if (anEntry == currentNode.data)
found = true;
else
currentNode = currentNode.next;
} // end while
return found;
} // end contains


/** intask: Returns a reference to the node at a given position.
* Precondition: List is not empty; 1 <= givenPosition <= length. */
public Node getNodeAt (int givenPosition)
{
assert (!isEmpty () && (1 <= givenPosition) && (givenPosition <= length));
Node currentNode = firstNode;
// traverse the list to locate the desired node
for (int counter = 1 ; counter < givenPosition ; counter++)
currentNode = currentNode.next;
assert currentNode != null;
return currentNode;
} // end getNodeAt

public class Node
{
public int data; // entry in list
public Node next; // link to next node
public Node (int dataPortion)
{
data = dataPortion;
next = null;
} // end constructor


public Node (int dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor


public int getData ()
{
return data;
} // end getData


public void setData (int newData)
{
data = newData;
} // end setData


public Node getNextNode ()
{
return next;
} // end getNextNode

public void setNextNode (Node nextNode)
{
next = nextNode;
} // end setNextNode

public int compareTo (int obj)
{
int nodeComp;
if (this.data == obj)
nodeComp = 0;
else if (this.data < obj)
nodeComp = -1;
else
nodeComp = 1;

return nodeComp;
}
} // end Node
}

Sorry for the lengthy post and thanks for any help,
Dudeface
Phys.Org News Partner Science news on Phys.org
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice
Mark44
#2
May22-11, 01:23 PM
Mentor
P: 21,215
Welcome to Physics Forums!

If you include code in your post, put a [ code ] tag at the start of your code, and a [ /code ] tag at the end (but without the extra spaces). These are HTML tags that preserve your indentation, which makes your code easier to read. I've done that for your code.

Please provide some details about how and where you are stuck. Does your code compile without error? If not, provide us with the compiler error messages. If your code compiles but doesn't run correctly, tell us what it's doing that it shouldn't, or that it's not doing that it should, and any other information that you think might be helpful.

Many of us can look through code and figure out why it isn't working, but that's not the best use of our time.


Quote Quote by dudeface View Post
1. The problem statement, all variables and given/known data
Hi there, I wish this wasn't my first post but unfortunately, it is. I will try to contribute later in the semester when my workload is less.

On to the topic, the problem is I have to implement the insertion sort algorithm on a linked list. I have the algorithm for Java (the language we have been taught) that works for an array. Yet for some reason I am having incredible difficulty translating it to a linked list.

I have tried many different styles of implementing this (for example traversing the list iteratively vs recursively) but have gotten frustrated and decided to start from scratch.
Once again I have gotten stuck, so could anyone tell me if I'm even going in the right direction?

Here is my most recent attempt at a solution
  public void sort(LList list){
    int i, j = 1;
    Node toAdd = null;
    Node temp = null;
    Node curr=null;
    for (i = 2; i <= list.length; i++)
    {
      temp = list.getNodeAt (i-1);
      curr = list.getNodeAt (i);
      if (curr.data < temp.data)
      {
        list.remove (i);
        while (j <= i)
        {
          toAdd = list.getNodeAt(j);
          if (curr.data <= list.getNodeAt(j).data)
            list.add (j-1, curr.data);
          list.display (list.firstNode);
          System.out.println ();
          j++;
        }
      }
    }
  }

It extends a class called LList that I have defined as follows:
public class LList//implements ListInterface 
{
  public Node firstNode; // reference to first node
  public int length;     // number of entries in list
  public LList ()
  {
    clear ();
  } // end default constructor
  
  
  public final void clear ()
  {
    firstNode = null;
    length = 0;
  } // end clear
  
  
  public boolean add (int newEntry)
  {
    Node newNode = new Node (newEntry);
    if (isEmpty ())
      firstNode = newNode;
    else // add to end of nonempty list
    {
      Node lastNode = getNodeAt (length);
      lastNode.next = newNode; // make last node reference new node
    } // end if
    length++;
    return true;
  } // end add
  
  
  public boolean add (int newPosition, int newEntry)
  {
    boolean isSuccessful = true;
    if ((newPosition >= 1) && (newPosition <= length + 1))
    {
      Node newNode = new Node (newEntry);
      if (isEmpty () || (newPosition == 1)) // case 1
      {
        newNode.next = firstNode;
        firstNode = newNode;
      }
      else // case 2: list is not empty
        // and newPosition > 1
      {
        Node nodeBefore = getNodeAt (newPosition - 1);
        Node nodeAfter = nodeBefore.next;
        newNode.next = nodeAfter;
        nodeBefore.next = newNode;
      } // end if
      length++;
    }
    else
      isSuccessful = false;
    return isSuccessful;
  } // end add
  
  
  public void display (Node firstNode)
  {
    Node currentNode = firstNode;
    while (currentNode != null)
    {
      System.out.println (currentNode.data);
      currentNode = currentNode.next;
    } // end while
  } // end display
  
  
  public boolean isEmpty ()
  {
    boolean result;
    if (length == 0)
    {
      assert firstNode == null;
      result = true;
    }
    else
    {
      assert firstNode != null;
      result = false;
    } // end if
    return result;
  } // end isEmpty
  
  
  
  public boolean replace (int givenPosition, int newEntry)
  {
    boolean isSuccessful = true;
    if ((givenPosition >= 1) && (givenPosition <= length))
    {
      assert !isEmpty ();
      Node desiredNode = getNodeAt (givenPosition);
      desiredNode.data = newEntry;
    }
    else
      isSuccessful = false;
    return isSuccessful;
  } // end replace
  
  
  public int getEntry (int givenPosition)
  {
    int result = 0; // result to return
    if ((givenPosition >= 1) && (givenPosition <= length))
    {
      assert !isEmpty ();
      result = getNodeAt (givenPosition).data;
    } // end if
    return result;
  } // end getEntry
  
  
  public int remove (int givenPosition)
  {
    int result; // return value
    if ((givenPosition >= 1) && (givenPosition <= length))
    {
      assert !isEmpty ();
      if (givenPosition == 1) // case 1: remove first entry
      {
        result = firstNode.data; // save entry to be removed
        firstNode = firstNode.next;
      }
      else // case 2: givenPosition > 1
      {
        Node nodeBefore = getNodeAt (givenPosition - 1);
        Node nodeintoRemove = nodeBefore.next;
        Node nodeAfter = nodeintoRemove.next;
        nodeBefore.next = nodeAfter; // disconnect the node to be removed
        result = nodeintoRemove.data; // save entry to be removed
      } // end if
      length--;
    } // end if
    
    
    return result = 0; // return removed entry, or
    // null if operation fails
  } // end remove
  
  
  public boolean isFull ()  // should ALWAYS return false
  {
    return false;
  }
  
  
  public boolean contains (int anEntry)
  {
    boolean found = false;
    Node currentNode = firstNode;
    while (!found && (currentNode != null))
    {
      if (anEntry == currentNode.data)
        found = true;
      else
        currentNode = currentNode.next;
    } // end while
    return found;
  } // end contains
  
  
  /** intask: Returns a reference to the node at a given position.
    * Precondition: List is not empty; 1 <= givenPosition <= length. */
  public Node getNodeAt (int givenPosition)
  {
    assert (!isEmpty () && (1 <= givenPosition) && (givenPosition <= length));
    Node currentNode = firstNode;
    // traverse the list to locate the desired node
    for (int counter = 1 ; counter < givenPosition ; counter++)
      currentNode = currentNode.next;
    assert currentNode != null;
    return currentNode;
  } // end getNodeAt
  
  public class Node
  {
    public int data; // entry in list
    public Node next; // link to next node
    public Node (int dataPortion)
    {
      data = dataPortion;
      next = null;
    } // end constructor
    
    
    public Node (int dataPortion, Node nextNode)
    {
      data = dataPortion;
      next = nextNode;
    } // end constructor
    
    
    public int getData ()
    {
      return data;
    } // end getData
    
    
    public void setData (int newData)
    {
      data = newData;
    } // end setData
    
    
    public Node getNextNode ()
    {
      return next;
    } // end getNextNode
    
    public void setNextNode (Node nextNode)
    {
      next = nextNode;
    } // end setNextNode
    
    public int compareTo (int obj)
    {
      int nodeComp;
      if (this.data == obj)
        nodeComp = 0;
      else if (this.data < obj)
        nodeComp = -1;
      else
        nodeComp = 1;
      
      return nodeComp;
    }
  } // end Node
}
Sorry for the lengthy post and thanks for any help,
Dudeface


Register to reply

Related Discussions
What's wrong with my sorted linked list algorithm? (Java) Programming & Computer Science 6
Linked list Programming & Computer Science 12
Quicksort/Insertion sort combo Engineering, Comp Sci, & Technology Homework 0
Linked List Programming & Computer Science 9
Linked list help! Programming & Computer Science 1