Using the Insertion Sort algorithm on a linked list

  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
     
  2. jcsd
  3. Mark44

    Staff: Mentor

    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.


     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?