Linked List returns values in wrong order

Question

I have (tried) to write a LinkedList, However, when I loop over all the elements in a list, the items are yielded in a different order than they are inserted.

Say, I insert them this way:

slist_insert(list, "red");
slist_insert(list, "green");
slist_insert(list, "blue");
slist_insert(list, "yellow");
slist_insert(list, "pink");
slist_insert(list, "purple");
slist_insert(list, "beige");
slist_insert(list, "white");
slist_insert(list, "black");
slist_insert(list, "brown");
slist_insert(list, "fuchsia");
slist_insert(list, "aqua");
slist_insert(list, "magenta");

But in the Loop, this is yielded instead:

green
magenta
aqua
fuchsia
brown
black
white
beige
purple
pink
yellow
blue
red

I haven't done that before, mind you, so there's a very good chance this code is riddled with elemental mistakes related to algorithms of Linked Lists: http://codepad.org/Sl0WVeos

The code, as such, is working fine, but there are several things bugging me about it:

• Wrong order yielded (as explained above)
• Have to use macros (is there a nicer way to do this?)
• Even after a call to slist_destroy, there is still memory leaking, and I can't figure out where it's coming from

Help is truly appreciated!

Answer 1

about the wrong item order

your logic for slist_impl_insertl() is wrong.

let's follow your code:

stringlist_t* slist_impl_insertl(stringlist_t* list, const char* str, unsigned int len)
{
    stringlist_t* newnode;
    if(list == NULL) // if the list is empty
    {
        newnode = slist_createl(str, len); // create a new item
        list = newnode;                    // insert the new item at the start of the list
        return list;
    }
    else // if the list is not empty
    {
        if(list->next == NULL) // if it contains only one item
        {
            list = slist_insertb(list, str, len); // insert a new item at the front of the list
            return list;
        }
        else // if it contains more than one item
        {
            newnode = slist_createl(str, len);                // create a new node
            newnode->next = (struct stringlist_t*)list->next; // insert the new node just after the first item !?!.
            list->next = (struct stringlist_t*)newnode;
            return list;
        }
    }
    return list; /* not reached */
}

so, your insert procedure does not always insert the new node at the same place. it sometimes insert at the beginning, sometimes it insert at the second place. this explains why the items are yielded in the wrong order.

a trivial fix is to always insert the new node at the start of the list, then the items will be yielded in the reverse order. or you can iterate through the list until you reach the end (list->next == NULL), and insert the new item after this last item:

stringlist_t* slist_impl_insertl(stringlist_t* list, const char* str, unsigned int len)
{
    stringlist_t *iter;
    if(list == NULL)
    {
        list = slist_createl(str, len);
    }
    else
    {
        // find the last ist item
        iter = list; 
        while(iter->next!=NULL)
            iter = iter->next;
        // insert the new item at the end of the list
        iter->next = slist_createl(str,len);
    }
    return list;
}

about using macros

if the list is empty (list == NULL), your insert procedure will modify the list to make it the first item. the macro takes care of reassigning the modified list. if you don't want to use macros, then you have to pass the list argument as a pointer so that you can modify it directly in your insert procedure.

(the guy who wrote the code in the first place made it so that he can insert an item anywhere in the middle of the list without having to write specific procedures to do so)

here is a candidate implementation of slist_insert() without using a macro:

void slist_insert(stringlist_t** list, const char* str)
{
    *list = slist_impl_insertl(*list, str);
}

using this implementation, you have to change the way you insert items in the list:

slist_insert(&list, "red"); // note the use of '&'

about the memory leak

the destroy procedure is freeing the strings stored in each item, that's fine. but each item is also dynamically allocated, thus they also need to be freed ! you have to store temporarily store the list pointer, advance to the next item, then free the stored pointer, until you reach the end of the list.

void slist_destroy(stringlist_t* list)
{
    stringlist_t *temp;
    while(list != NULL)
    {
        // free the data contained in the current list item
        free(list->data);
        // save the pointer to the next item
        temp = slist_next(list);
        // free the current item
        free(list);
        // continue with the next item
        list = temp;
    }
}