Understanding type functions with linked-list

Question

Good Morning/Evening everyone, I'd like to clarify in my head the following concept about linked list functions (In this case recursive).

Let's take the following program that eliminates the duplicates in a linked list recursively :

ElementoDiLista* deleteDuplicates(ElementoDiLista* head) { if (head == NULL) { return NULL; } if (head->next == NULL) { return head; } if (head->info == head->next->info) { ElementoDiLista *tmp; tmp = head->next; head->next = head->next->next; free(tmp); return deleteDuplicates(head); } else { head->next = deleteDuplicates(head->next); return head; } }

With the definition of my struct and list this way :

struct el {int info; struct el *next;}; typedef struct el ElementoDiLista; typedef ElementoDiLista *ListaDiElementi;

And then in the main i call the function this way :

Lista1 = deleteDuplicates(Lista1);

Where Lista1 is declared as follows : ElementoDiLista Lista1 = NULL

My question was, i was used to declare functions that are void or depends on single types (int,float ecc...) I'd like to clarify two things :

Why the function is declared as ElementoDiLista* deleteDuplicates(ElementoDiLista* head) because to me it is more intuitive this way ListaDiElementi deleteDuplicates (ListaDiElementi *head) but unfortunately,doesn't work.
It is not very clear to me why the function returns head or NULL values, but this is the reason i think why in the main Lista1 takes the value of the function, because the function modifies the list itself, am i right ?

I'm sorry if the questions are not very exciting i'm just trying very hard to understand list in general and are quite difficult, Any help or advise would be appreciated,

Thank you all anyway!

The function modifies the head of the list, so it needs to return the information to the caller somehow. NULL is returned on error. Is can be void deleteDuplicates(ElementoDiLista **head) where you modify the head pointer inside the function. You want to return the pointer, not the data. — KamilCuk
– KamilCuk, Commented Dec 2, 2018 at 11:34
ElementoDiLista *is equivalent to ListaDiElementi so you can use either of these declarations. — Paul Ogilvie
– Paul Ogilvie, Commented Dec 2, 2018 at 11:37
ElementoDiLista* deleteDuplicates(ElementoDiLista **head) works ? — jacopoburelli
– jacopoburelli, Commented Dec 2, 2018 at 11:38
Note: hiding pointes in typedefs is discouraged. So typedef ElementoDiLista *ListaDiElementi; is discouraged (because it is now unclear that it concerns a pointer). — Paul Ogilvie
– Paul Ogilvie, Commented Dec 2, 2018 at 11:40

Jorge Adriano Branco Aires · Accepted Answer · 2018-12-02 15:30:56Z

Why the function is declared as ElementoDiLista* deleteDuplicates(ElementoDiLista* head) because to me it is more intuitive this way ListaDiElementi deleteDuplicates (ListaDiElementi *head)

Starting with the argument, originally it is declared as,

ElementoDiLista* head

so it takes a pointer to the head element. This would have been equivalent (with a variable name change) to,

ListaDiElementi list

So we're passing as argument a "list", which is a pointer to the head. That pointer is not modified. To modify it indeed we'd need to use as you suggest,

ElementoDiLista** head

or equivalently and perhaps more readable,

ListaDiElementi* list

The question is therefore, "do we need to modify the pointer to the head"? Or in other words, does the original list pointer need to be modified? The answer is no.

If the list is null it will remain null. If the list is not null the head will remain the same. You won't remove the head, only the nodes that follow which hold the same value the head does.

It is not very clear to me why the function returns head or NULL values, but this is the reason i think why in the main Lista1 takes the value of the function, because the function modifies the list itself, am i right ?

Personally I don't like that the function returns a pointer to an element (i.e. a list). Also it appears to always return head, and to be implemented in a rather obfuscated manner.

Firstly regarding me not liking it. If you are changing the structure of an existing list, rather than creating a new one, you want your initial pointer to remain valid after the procedure. So you change that pointer (if you need to) rather than returning a new one. In this case it doesn't even change. So I would either have it void or return some exit code.

Secondly look at the code,

if (head == NULL) { return NULL;

It returned head since it is null.

if (head->next == NULL) { return head;

It returned head again.

if (head->info == head->next->info) { ElementoDiLista *tmp; tmp = head->next; head->next = head->next->next; free(tmp); return deleteDuplicates(head); }

It returns deleteDuplicates(head) and head is the original argument which hasn't changed. So if all other cases return head, so will this.

else { head->next = deleteDuplicates(head->next); return head; }

This too returns head (note head hasn't changed). So its return value is always the original argument head. So this is pointless.

Furthermore note that in the first two cases you do nothing, you just return a value that is useless.

if (head == NULL) { return NULL; } if (head->next == NULL) { return head; }

So if you do change your procedure to void this code disappears. You don't have to do anything if your list or its tail is null, since there are no duplicates.

Collectives™ on Stack Overflow

Understanding type functions with linked-list

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related