Using the Insertion Sort algorithm on a linked list

dudeface

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

Mark44

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.