Adding an element in a sorted LinkedList

Question

I have a LinkedList of ListElement objects, and I would like to create a recursive method that adds new nodes while still preserving the sorted order of the list.

Right now I have:

public static ListElement InsertList(ListElement head, ListElement newelem) {

    if (head == null) {
        head = newelem;
        head.next = null;
    } 
    else if (head.next == null) {
        newelem.next = null;
        head.next = newelem;
    }
    else if (head.value < newelem.value) {
        newelem.next = head;
        head = newelem;
    }
    else if (head.value >= newelem.value) {
        head = head.next;
        return InsertList(head, newelem);
    }
    return head;
}

And I am calling it multiple times with the code:

ListElement head = null;
ListElement elem;

// this block of code is repeated multiple times with values of 3, 8, 20, and 15
elem - new ListElement();
elem.value = 6;
head = InsertList( head, elem );

The output is as follows:

This output is correct for the first three lines, but after that it all goes weird. Can anyone please improve my algorithm? I feel like the InsertList method could be shortened a lot more. Thanks!

I see 2 problems with it as is: 1) I think you need to reverse your first 2 elseifs since your not covering the case where head.next is null, but newelem.value is greater than head.value. 2) in you're final else if you shouldn't reassign the head. — DMulligan
– DMulligan, Commented Apr 11, 2013 at 3:10

Zim-Zam O'Pootertoot · Accepted Answer · 2013-04-11 03:09:48Z

1

The head = head.next statement in your fourth conditional block is destroying the head element. I believe this should instead be

else if(head.value >= newelem.value) {
    head.next = InsertList(head.next, newelem);
}

answered Apr 11, 2013 at 3:09

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

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

Comments

Vaibhav Desai · Accepted Answer · 2013-04-11 03:15:35Z

1

When you try to insert 15, you enter the 4th condition:

// 20 > 15
else if (head.value >= newelem.value)

which in turn calls InsertList but passes 8 as the head node and thus enters the 3rd condition:

// 8 < 15
else if (head.value < newelem.value)

Here, you say

newelem.next = head;

which sets 15 -> next = 8

and then you say,

head = newelem;

which sets head = 15.

Do you see the problem? Use @Zim-Zam O'Pootertoot answer to fix your bug.

answered Apr 11, 2013 at 3:15

Vaibhav Desai

2,7381 gold badge18 silver badges16 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 12:05:42Z

0

Thanks for all the help and answers guys!
I found another post similar to mine and one of the answers on there seemed to work for me.
Here is the link for anyone who wishes to see: https://stackoverflow.com/a/15936744/1470257

edited May 23, 2017 at 12:05

CommunityBot

11 silver badge

answered Apr 11, 2013 at 3:15

yiwei

4,2209 gold badges39 silver badges58 bronze badges

Collectives™ on Stack Overflow

Adding an element in a sorted LinkedList

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related