0

I have written below given piece of code to add elements with their keys in sorted order in linked List. but its not sorting them according to keys and are added in their insertion order only. Looks like, I have missed something.

public void insert(int key, int value)
{
    Link pcurrent = pfirst;
    Link newLink = new Link(key, value);
    if(pcurrent != null)
    {
        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            pcurrent = pcurrent.next;
        }
        Link temp = pcurrent.next ;
        pcurrent.next = newLink;
        newLink.next = temp;
    }
    else
    {
        newLink.next = pfirst;
        pfirst = newLink;
    }
    System.out.println("After inserting element in the linked List");
    display();
}
Improve this question
2
  • What have you done to debug this yourself? Commented Sep 14, 2014 at 3:09
  • @Code-Apprentice: did try to figure out, I was doubtful if it did enter in while loop at all, but it did. So, the only part that is wrong is next 3 lines after while loop. where I am trying to insert a new element. As per my level of understanding, I can not figure out how else the new node is supposed to be inserted between Commented Sep 14, 2014 at 3:13

3 Answers 3

Reset to default
1

Let's work through an example to see how to fix your code. Since the values aren't part of the algorithm, I will ignore them in the following discussion. First, assume we already have a list with the following keys:

5 -> 42 -> 69

Now let's analyze the call list.insert(53, x); which should insert a (key, value) pair as the third element in our list.

Start at the beginning of the list.

    Link pcurrent = pfirst;

Create a new node.

    Link newLink = new Link(key, value);

Make sure we are not at the end of the list.

    if(pcurrent != null)
    {

Step through the list to find the node where the new link should be inserted.Note that we must be very careful with this loop. It is very easy to have an off-by-one error here.

        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            pcurrent = pcurrent.next;
        }

Note that we must be very careful with this loop. It is very easy to have an off-by-one error here. So let's analyze it more carefully.

In our exmple, pcurrent.key starts with a value of 5 which is less than the 53 we are inserting. Also, pcurrent.next is not null. So we move to the next link which has a key of 42. This is still less than 53 and pcurrent.next is still not null. So we move to the next link again. Now pcurrent.next is 69. This isn't less or equal to 53, so the loop terminates.

        Link temp = pcurrent.next ;
        pcurrent.next = newLink;
        newLink.next = temp;

Now we insert after the 69. Ooops! We are off by one. So our loop is incorrect.

To fix this we will need another Link variable, call it previous. Then you can insert after previous and everything should be fine.

    Link pcurrent = pfirst;
    Link previous = null;    // Add this declaration

    Link newLink = new Link(key, value);
    if(pcurrent != null)
    {
        while(pcurrent.key <= newLink.key && pcurrent.next != null)
        {
            previous = pcurrent;     // Update previous
            pcurrent = pcurrent.next;
        }

        // insert newLink between previous and next
        previous.next = newLink;
        newLink.next = current;
    }

You should also perform a similar analysis for inserting to an empty list and inserting to the beginning of a list. Note that a debugger can help you with this analysis by showing you exactly what your code is doing. Just be sure that you know what you expect to happen. If you are ever surprised by what your debugger shows, then you know there's a problem.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you for catching that err, I have tried adding adding to beginning of the linked List and to an empty list as well.Actually, I intend to do it in SinglyLinked list, so previous is not really an option for me, is it really not possible to achieve the same only with current variables we have? Let's say, 1 off error is fixed, but that still does not answer why does the newlink is not in its sorted pposition at all and go directly in the insertion order in the linkedlist
@GurupratapSaini I think you misunderstand. I'm not suggesting making a double-linked list. I'm suggesting that your insert() method keep track of two links as you search for the location to insert the new node: the previous link as well as the current one. This is absolutely required to implement this correctly.
@GurupratapSaini "Let's say, 1 off error is fixed, but that still does not answer why does the newlink is not in its sorted pposition at all" Yes it does. The off-by-one error is exactly why the newLink is not inserted into its sorted position.
@Code-Apprentive Thanks a ton for making this noob understand. I am real slow with DS. :)
@GurupratapSaini We all start somewhere. I strongly suggest that you learn how to use the debugger in your IDE. I will help you understand what your code is actually doing so that you can find out what is wrong with it.
|
0

you need to update pFirst inside first if also if element is being inserted in the begining of the linked list

Suppose your initial Link was (10, 5) and second linked you are trying to insert is (12, 6) Then according to your code pFirst will be L(10, 5)

and in second update, your linked list will look like L(10, 5) -> L(12, 6)

and then if you add L(9, 6) it will become L(10, 5) -> L(9, 6) -> L(12, 6)

 while(pcurrent.key <= newLink.key && pcurrent.next != null)
    {
        pcurrent = pcurrent.next;
    }

There are two scenarios in which your code will exit from above
1. pcurrent.next != null, then in that case what you have done next is cool.
2. Or either newLink.key > pcurrent.key, in this case newLink should come before pCurrent, which means you need to know previous element as well

Your code should look like this 

  Link previous = pFirst;
  while(pcurrent.key <= newLink.key && pcurrent.next != null)
    {
       previous = pCurrent; 
       pcurrent = pcurrent.next;
    }
    if( pcurrent.next == null){
        Link temp = pcurrent.next ;
        pcurrent.next = newLink;
        newLink.next = temp;
    }
    else{
        // Also check if previous == pcurrent 
        // then this element will go at beginning as this is the smallest one
        if(pCurrent == previous){
            newLink.next = previous;
            pFirst = newLink;
        }
        else{
          Link temp = previous.next ;
          previous.next = newLink;
          newLink.next = temp;
        }
     }
Improve this answer

1 Comment

Okay, but what about the rest? why is it not inserting at rest of the appropriate positions?
0

As suggested by @code-apprentice : It was exactly, mess because of off by 1 error. Here is the solution that fixed it, hope that helps !

Singly Linked List in Java to add elements sorted according to keys and to find and delete an element from the linked List

Thanks

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.