- #1
dudeface
- 1
- 0
Homework Statement
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