Linked List Issue

[gamehack]

Hello all again,

Sorry for troubling you with my problems. I've tried to implement
simple double linked lists, here's my structure:
struct DResult {
double val;
char* title;
struct DResult* next;
struct DResult* prev;
};

I also have a typedef for struct DResult to DResult.

Then I've written a function to append an element to the list with the
following declation:
int dresult_append(DResult* list, DResult* element);
Then I used a debugger to trace down the issue with the function, so
the this code fragment inside the function:
if(list == NULL) // empty list
{
list = element;

return 1;
}

The problem is that list is updated after the assignment but after the
function returns, it goes back to NULL. I'm quite puzzled. Do I have to
use a double pointer for the list like DResult** list and then update
*list ( which a pointer to a DResult)?

Regards

 

[Chris Smith]

int dresult_append(DResult* list, DResult* element);
Then I used a debugger to trace down the issue with the function, so
the this code fragment inside the function:
if(list == NULL) // empty list
{
list = element;

return 1;
}

The problem is that list is updated after the assignment but after the
function returns, it goes back to NULL. I'm quite puzzled.

C is pass by value. If you assign to a formal parameter, that
assignment has no effect outside of the function where it happens. For
this reason, it's generally considered poor form to assign to a formal
parameter in the first place.

Do I have to
use a double pointer for the list like DResult** list and then update
*list ( which a pointer to a DResult)?

Yes, that would certainly solve your problem.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[gamehack]

[snip]

this reason, it's generally considered poor form to assign to a formal
parameter in the first place.

What is the proper design for this kind of function? Should I use
another proper approach?

Thanks

 

[Chris Smith]

[snip]

this reason, it's generally considered poor form to assign to a formal
parameter in the first place.

What is the proper design for this kind of function? Should I use
another proper approach?

Because C is so widely used, there aren't a lot of guidelines that are
used throughout all of the C language. Passing a pointer-to-pointer
would be okay, as would returning the new list pointer. I would
intuitively prefer to return the new list pointer, but I've also seen a
reasonable case made for non-idempotent functions to use the return
value only for success/failure notification.

The reason not to assign directly to a formal parameter is just that it
doesn't work, for your definition of "work". Assigning to the thing
that a formal parameter points to, on the other hand, is fine and
actually very common.

 

[CBFalconer]

Sorry for troubling you with my problems. I've tried to implement
simple double linked lists, here's my structure:
struct DResult {
double val;
char* title;
struct DResult* next;
struct DResult* prev;
};

I also have a typedef for struct DResult to DResult.

Then I've written a function to append an element to the list with the
following declation:
int dresult_append(DResult* list, DResult* element);

There's your trouble. C passes by value, so to change a list you
have to alter something. You want:

struct DResult *appendto(struct DResult *list,
struct DResult *element);

called by something like

thelist = appendto(thelist, newelement);

and you better have some rules about the initial state, i.e. the
empty list.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

 

[Ben Bacarisse]

[snip]

this reason, it's generally considered poor form to assign to a formal
parameter in the first place.

What is the proper design for this kind of function? Should I use another
proper approach?

I'd suggest that there are two common solutions to this problem. The
fundamental issue is that the list is not properly represented by the
structure that hold a node's data. A list can be empty so the real
repsenetation of the list is a *pointer* to one of those structs (a
pointer which might then be NULL).

Option 1: Every list modifying function takes a list (i.e. a struct ptr)
as an arguments and returns a list as a result. Every call of the
function must then look something like this:

struct DResult *my_list;
....
my_list = list_append(my_list, 1.2);

Option 2: Define a new struct that holds (at least) the pointer to the
start of the list. You can do more with this method, because the
structure can hold extra information such as a pointer to last element
(for appending) or a count of the number of elements or whatever else
might help your design:

struct DResultList {
struct DResult *start;
struct DResult *end;
int n_elements;
};

All your list functions now take a pointer to a struct DResultList and
operate on it.

Option 1 makes it very simple to write short recusive list functions.
Option 2 is much more flexible but requires more complexity.

 

[gamehack]

[snip]

this reason, it's generally considered poor form to assign to a formal
parameter in the first place.

What is the proper design for this kind of function? Should I use another
proper approach?

I'd suggest that there are two common solutions to this problem. The
fundamental issue is that the list is not properly represented by the
structure that hold a node's data. A list can be empty so the real
repsenetation of the list is a *pointer* to one of those structs (a
pointer which might then be NULL).

That's what I've done.

Option 1: Every list modifying function takes a list (i.e. a struct ptr)
as an arguments and returns a list as a result. Every call of the
function must then look something like this:

struct DResult *my_list;
....
my_list = list_append(my_list, 1.2);

I'm not really a fan of this approach - I think the user(programmer
actually) should not be required to use this construct, it's much more
intuitive to provide just two parameters and don't care about the
result(with respect to the list and element variables).

Option 2: Define a new struct that holds (at least) the pointer to the
start of the list. You can do more with this method, because the
structure can hold extra information such as a pointer to last element
(for appending) or a count of the number of elements or whatever else
might help your design:

struct DResultList {
struct DResult *start;
struct DResult *end;
int n_elements;
};

All your list functions now take a pointer to a struct DResultList and
operate on it.

This is how I resolved my issue:

int dresult_append(DResult** list, DResult** element);

And in main.c I do something like:
DResult* list = NULL;
DResult* element = dresult_new();
where dresult_new() mallocs the structure and initialises all the
structure elements.

Option 1 makes it very simple to write short recusive list functions.
Option 2 is much more flexible but requires more complexity.

Thanks

 

[stathis gotsis]

This is how I resolved my issue:

int dresult_append(DResult** list, DResult** element);

Why is the second argument a double pointer? Is any modification necessary
for *element?

 

[Default User]

gamehack wrote:

Then I used a debugger to trace down the issue with the function, so
the this code fragment inside the function:
if(list == NULL) // empty list
{
list = element;

return 1;
}

The problem is that list is updated after the assignment but after the
function returns, it goes back to NULL. I'm quite puzzled. Do I have
to use a double pointer for the list like DResult** list and then
update *list ( which a pointer to a DResult)?

You received the answer already, but I'll also point out that this
issue is covered in the FAQ:

http://c-faq.com/ptrs/passptrinit.html


It's a good idea to run through that with your questions first.



Brian

 

[Ben Bacarisse]

[snip]
this reason, it's generally considered poor form to assign to a
formal parameter in the first place.


What is the proper design for this kind of function? Should I use
another proper approach?

I'd suggest that there are two common solutions to this problem.
<two linked-list options snipped>

This is how I resolved my issue:

int dresult_append(DResult** list, DResult** element);

I should have included this as option 3 (although it follows naturally
from my first paragrah). It is fine, of course, but not my favourite.

Having gone to the effort of passing a pointer to a mutable "thing" I
think it makes sense to make it a struct even if it has only one pointer
in it! At least you get the chance to grow it later if your
implementation requires it -- and you get another name: struct DResultList
which helps to distinguish between the nodes and the list itself.

BTW, it is best not to quote sigs (unless you want to talk about them).