is there a better way to optimise this?

I have written an in_order_list function, was just wondering if there is a better way to do it, mine seems to work fine through testing. It just looks a bit long, what do you think:

Code:

---

list_t
*insert_in_order (list_t *list, data_t value)
{
node_t *new, *curr, *prev;
       
new = (node_t *) malloc (sizeof (node_t));
       
new->next = NULL;
new->data = value;
       
curr = list->head;
if (curr == NULL)                /*We have the first entry*/
{
        list->foot = list-> head = new;
        return list;
}
        if (curr->data > value)
{
        new->next = curr;
        list->head = new;
        return list;       
}
else
        while (curr->next !=NULL)
        {
                if (curr->data < value)
                {
                prev = curr;
                curr = curr->next;
                }
                if (curr->data > value)
                {
                new->next = curr;
                prev->next = new;
                greturn list;
                }
        }
        curr->next = new;
        return list;       
}

---

> greturn list;
I think it doesn't compile, and is badly indented.

You're also casting the result of malloc in C - see the FAQ

> if (curr->data > value)
You should be able to combine this test with the while loop which follows, which also contains in effect the same condition.

If it was made to compile, it is buggy because inserting a data_t that is equal to another in the list and is not at the end, will cause an infinite loop.

You're spot on thinking it is a bit longer than it shoule be. If it is longer than 15 lines all up (including lines with just a curly bracket) then it is definitely too long.

Start by removing both "if (curr->data > value)" statements (keeping the body of the else part).

i changed it a bit and but im still confused about getting ascending order...

Code:

---

list_t
*insert_in_order (list_t *list, data_t value)
{
        node_t *new, *curr, *prev;
       
        new = (node_t *) malloc (sizeof (node_t));
       
        new->next = NULL;
        new->data = value;
       
        curr = list->head;
        if (curr == NULL)                /*We have the first entry*/
        {
                list->foot = list-> head = new;
                return list;
        }
        else
        {
                prev = curr;
                while (curr->next != NULL && curr->data > value)
                {
                        if (curr->data <= value)
                        {
                                new->next = prev->next;
                                prev->next = new;
                                return list;
                        }
                        else
                        {
                        prev = curr;
                        curr = curr->next;
                        }
                }
                new->next = curr->next;
                curr->next = new;
        }
       
        return list;       
}

---

While this statement is true
curr->data > value
this will always be false
curr->data <= value

So really, all you need inside this while loop are the two statements which advance through the list.


> curr->next = new;
This should be prev->next = new;

If you ever want to move this list-handling to C++ instead of C, you probably want to rename your "new" variable to some other name, as "new" is a keyword in C++.

In straight C, you shouldn't cast malloc - it hides problems with including stdlib.h.

As far as I can tell, new->next is ALWAYS set to something during te insertion, so new->next = NULL is not needed. (Except when list is empty).

I would move the "curr = list->head" down inside the "else" branch of the first if, and use "if(list->head == NULL)" to check if the list is empty. It won't change the code much, but it connects better with the code inside the if that uses list->head.

Not sure what "list->foot" does - if you are using it as "the end of the list", then you probably need to update it when you insert at the end of the list. If you aren't using it, remove it completely.

Is there a particular purpose to returning the list? are you calling using something like this?

Code:

---

list = insert_in_order (insert_in_order (memset(malloc(sizeof(list_t)), 0, sizeof(list_t)), value1), value2);

---

(I wouldn't want to debug that line, if it ever started going wrong!).

If you aren't using the return value, then make the function void - it simplifies the code for the compiler, which makes it faster (and that's what you asked for in the first place) - it may not make MUCH of a difference, but it forces the compiler to store list in a particular register, which may be better used for something else (or to shuffle what list is in to get to the right register at the return-point - again, unneccessarily if the function return value isn't being used).

--
Mats

what about when the case is for insert at the head when the value is smaller than the head, I dont understand how to write it so that this is looked after as well at the end case (value is larger than the end). Putting it into the middle is understood : new->next = prev->next; prev->next = new;

So, if we have a list where you want to insert before the head (because the value is less than head), the following (red) code will be run:

Code:

---

list_t
*insert_in_order (list_t *list, data_t value)
{
        node_t *new, *curr, *prev;
       
        new = (node_t *) malloc (sizeof (node_t));
       
        new->next = NULL;
        new->data = value;
       
        curr = list->head;
        if (curr == NULL)                /*We have the first entry*/
        {
                list->foot = list-> head = new;
                return list;
        }
        else
        {
                prev = curr;
                while (curr->next != NULL && curr->data > value)[/COLOR]
We do not enter the loop, because curr->data > value is false
                {
                        if (curr->data <= value)
                        {
                                new->next = prev->next;
                                prev->next = new;
                                return list;
                        }
                        else
                        {
                        prev = curr;
                        curr = curr->next;
                        }
                }
                new->next = curr->next;
                curr->next = new;
        }
       
        return list;
}

---

--
Mats

thank you guys firtsly, matsp, I will change the cast to malloc and try some of the changes you mentioned esp. the void changes, I am not using the function like you mentioned.

By the way, I think you need to update head to if you insert at the head of the list - otherwise head will point to somewhere after the first element - I may be wrong on that, but I don't think I'm wrong.

--
Mats

"We do not enter the loop, because curr->data > value is false" wouldn't this be true for the head (ascending order?)

so far i have

Code:

---

list_t
*insert_in_order (list_t *list, data_t value)
{
        node_t *new, *curr, *prev;
       
        new = malloc (sizeof (node_t));
       
        new->next = NULL;
        new->data = value;
       
        curr = list->head;
        if (curr == NULL)                /*We have the first entry*/
        {
                list->foot = list-> head = new;
                return list;
        }
        else
        {
                prev = curr;
                while (curr->next != NULL && curr->data < value)
                {
                        prev = curr;
                        curr = curr->next;
                }
               
                new->next = curr->next;
                prev->next = new;
        }
       
        return list;       
}

---

without success...
this list_t return for the function being run over a scanf loop

Quote:

---

Originally Posted by qubit67

"We do not enter the loop, because curr->data > value is false" wouldn't this be true for the head (ascending order?)

---

Yes, my point was more to the fact that if you have list->head is a separate variable to curr and new and prev, right?

So let's pretend that we do this (I've shortened your function name a bit):
list->head = NULL
insert(list, 7);
list->head was null, so we just set list->head = new;
list->head is now (say) 0x12345
insert(list, 5)
curr = list->head = 0x12345
curr->data = 7, 5 is less than 7, so we insert at the head of the list, but list->head isn't changed! [This is assuming the rest of the list insertion is correct].

So you will never find 5 in the list, because you start at list->head, which is 7.

If you start by verifying that your current code works for inserting values 10, 15, 20, 25, 22, 12, 35 or some such - print the entire list after each new value.

Then start looking at what happens if you insert 7, 5, 3 or such. I think you'll find that the list doesn't have those values - but if you print the list from prev inside your function, it WILL list the 7, 5 and 3 values. [Although I'm not 100% sure]

--
Mats

so after trying many different models, I found a solution though again, rather length. any improvements over it?

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int data_t;
typedef struct node node_t;

struct node
{
        data_t data;
        node_t *next;
} ;

typedef struct
{
        node_t *head;
        node_t *foot;
} list_t;

list_t
*make_empty_list(void) {
        list_t *list;
       
        list = malloc(sizeof(list_t));
        assert(list!=NULL);
       
        list->head = list->foot = NULL;
       
        return list;
}


list_t
*insert_in_order (list_t *list, data_t value)
{
        node_t *new, *curr, *prev;
       
        new = malloc (sizeof (node_t));
       
        new->next = NULL;
        new->data = value;
       
        if (list->head == NULL)                /*First in*/
        {
                list->foot = list->head = new;
                return list;
        }
        else
        {       
                if (value <= list->head->data) /*Smaller than the head, so insert there*/
                {
                        new->next = list->head;
                        list->head = new;
                        return list;
                }
                else
                {
                        if (value > list->foot->data)/*Larger than the foot so insert there*/
                        {
                                list->foot->next = new;
                                list->foot = new;
                                return list;
                        }       
                        else
                        {                                        /*we are somewhere between H & F, find the right place*/
                                prev = list->head;
                                curr = list->head->next;
               
                                while (curr->data < value)
                                {/*Move through list, stop when the curr node data is larger than value*/
                                        prev = curr;       
                                        curr = curr->next;
                                }
/*Now at the right spot in the body of the list, insert*/
                        new->next = curr;
                        prev->next = new;
                        return list;
                        }
                }
        }               
}

list_t
*read_into_list (void)
{
        list_t *list;
        int value;
       
        list = make_empty_list ();
       
        while ((scanf("&#37;d", &value)) != EOF)
        {
                list = insert_in_order (list, value);
        }
        return list;
       
}

void
print_list(list_t *list)
{
        node_t *ptr;
        ptr = list->head;
        while (ptr != NULL)
        {
                printf("%d ", ptr->data);
                ptr = ptr->next;
        }
}

void
free_list(list_t *list)
{
        node_t *curr, *prev;
        assert(list!=NULL);
        curr = list->head;
        while (curr) {
                prev = curr;
                curr = curr->next;
                free(prev);
        }
        free(list);
}

int
main (int argc, char **argv)
{
        list_t *list;
       
        list = read_into_list ();
       
        print_list (list);
        free_list (list);
       
        return 0;
}

---

Oh no it's just getting worse - I can't stand it any longer!
This is how to do it, the way you've defined things:

Code:

---

list_t* Insert(list_t *list, data_t value)
{
        node_t *prev = NULL, *curr = list->head, *ins = malloc(sizeof(node_t));
        while (curr != NULL)
        {
                if (value < curr->data) break;
                prev = curr;
                curr = curr->next;
        }
        if (prev == NULL)
                list->head = ins;
        else
                prev->next = ins;
        if (list->foot == NULL)
                list->foot = ins;
        ins->next = curr;
        ins->data = value;
        return list;
}

---