Need some help with Linked Lists;

Question

I have a simple question in understanding the pointers and struct definitions in the linked list code.

1)

typedef struct node { struct node* next; int val; }node;

here if I use two "node" when i initialize node *head; which node I am referring to?

2) Here I use an int val in the struct. If I use a void* instead of int is there any thing thats going to change ?

3)Also if I pass to a function

reverse(node* head) { node* temp = head; or node* temp = *head; //what is the difference between the two }

I am sorry if these are silly question I am new to c language.

Thanks & Regards, Brett

I expect these are homework questions, as (2) and (3) seem not to be something randomly thought of. You may want to show code for how you would use the list, or initialize it, for (1) and then explain what you think for each answer and then you are getting help with your thinking, rather than being given answers. — James Black
– James Black, Commented Aug 8, 2010 at 2:08

AndersK · Accepted Answer · 2010-08-08 02:38:32Z

<1> in C you need to specify struct node for structs

 struct node { ... } node;

the last 'node' is variable of type struct node e.g.

node.val = 1;

and not a type.

if you want to use 'node' as a type you need to write

typedef struct node { .. } node;

<2> if you use void* you will need a mechanism to handle what the pointers point to e.g. if void* points to an integer you need keep the integer either on the stack or the heap.

node n; int value = 1; n.val = &value; // pointing to a single integer on stack int values[]={1,2,3}; n.val = values; // pointing to an array of integers on stack void* ptr = malloc(sizeof(int)); n.val = ptr; // pointing to a single (uninit) integer allocated on heap int* ptrval = (int*)ptr; // setting an int ptr to the same memory loc. *ptrval = value; // ptrval now points to same as n.val does

<3> reverse(node* head) head is a pointer to your list, *head is the content of what the pointer points to (first node below)

head->[node next]->[node next]->[node next]

EDIT: rephrased and edited. EDITx2: apparently the question got edited and a typedef was added so the question was altered.

so *head contains address of the node next ? Also I am referring to these two nodes. I want to know how typedef plays with second node removed. struct node {<--- } node; <--
head points to the first node in your list. head contains (as well as the first node contains since it points there) the pointer 'next' that points to the next node
the struct node {} node is not a typedef, if you want a typedef you need to write typedef struct node { } node; then you can use node as a type, in your original question 'node' is not a type (C89)
I saw in many implementations using typedef struct node{}; without using second node. What is the use of using second node. (not necessarily "node" it can be any name)
@brett IIRC some compilers allow this as a short form to save some typing for devs to avoid writing the same name twice (note that you are not actually introducing a type, just a synonym).

Ritwik Bose · Accepted Answer · 2010-08-08 02:26:19Z

*head is the dereference of the pointer : ie the actual place in memory that is pointed to by the pointer head...

Think of head as a coat hanger and *head as the coat itself, if that helps.

ie:

struct * coat c; //this is a coat hanger, not a coat .... struct coat k = *c;//this is the coat itself, not a coat hanger

This is not a complete answer because I suspect homework. I just want to try and point you in the right direction.

R Samuel Klatchko · Accepted Answer · 2010-08-08 02:50:09Z

For #1:

In C, struct's have a separate name space. So if you wrote:

struct foo { ... };

You then have to use struct foo to reference the type. If you tried just foo after the above definition, the compiler would give an error as it doesn't know anything about that unqualified name.

A typedef gives a type an alternate name. A typedef name does not need to be qualified, so once you do:

typedef struct foo foo;

You can now use an unqualified foo to reference the type. Since it's just an alternate name, you can now use struct foo and foo interchangeably.

For #2.

It's possible that if you changed val to a void * it could change the size of the entire structure. Whether that makes a difference will depend on how you've written the rest of your code.

@Samuel typedef struct foo{...}foo1; now do need to use foo1 or foo? why ?
@brett - when you have typedef struct foo{...}foo1; you can write either struct foo ... or foo1 ..., the two are equivalent.

Collectives™ on Stack Overflow

Need some help with Linked Lists;

3 Answers 3

5 Comments

1 Comment

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

2 Comments

Related