Using the Insertion Sort algorithm on a linked list

In summary, a user is seeking help with implementing the insertion sort algorithm on a linked list in Java. They have tried various approaches but have not been successful and are seeking guidance on their current attempt. They provide the code they have written for the insertion sort method and the LList class they have defined.
  • #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
 
Physics news on Phys.org
  • #2
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.


dudeface said:

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
Code:
  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
 

1. How does the Insertion Sort algorithm work on a linked list?

The Insertion Sort algorithm works by iterating through the linked list and comparing each element with the elements that come before it. If the element is smaller than the previous element, it is moved to the correct position in the list. This process is repeated until the entire list is sorted in ascending order.

2. What is the time complexity of using the Insertion Sort algorithm on a linked list?

The time complexity of Insertion Sort on a linked list is O(n^2), where n is the number of elements in the list. This is because in the worst case scenario, the algorithm will have to compare each element with all the elements that come before it, resulting in a nested loop.

3. Can the Insertion Sort algorithm be used on a doubly linked list?

Yes, the Insertion Sort algorithm can be used on a doubly linked list. The only difference is that instead of swapping elements, the pointers of the nodes will need to be adjusted to maintain the proper order.

4. What are the advantages of using the Insertion Sort algorithm on a linked list?

One advantage of using Insertion Sort on a linked list is that it does not require any additional memory space, as the sorting is done in-place. It is also efficient for sorting small lists and lists that are almost sorted already. Additionally, the algorithm is stable, meaning that the relative order of elements with equal values will not be changed.

5. Are there any drawbacks to using the Insertion Sort algorithm on a linked list?

One drawback of using Insertion Sort on a linked list is its time complexity, which can be inefficient for large lists. Additionally, if the list is in descending order, the algorithm will take longer to sort compared to other sorting algorithms, as each element will need to be moved to the beginning of the list. It is also not suitable for sorting lists with a large number of elements that are in random order.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
11K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
5K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
9K
  • Engineering and Comp Sci Homework Help
Replies
0
Views
3K
Back
Top