By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,084 Members | 1,969 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,084 IT Pros & Developers. It's quick & easy.

Linked list declaration

P: n/a
Something I don't really understand.

In http://maxnoy.com/interviews.html, Insert and Delete for linked list
are defined as:

int Insert(node **head, int data)

and

int Delete(node** head, int deleteMe)

I thought linked-list is always defined as something like struct node
*head. Why the author defined the linked-list as pointer to pointer?
And in the next question he defines head in Split() as node *head. This
is really confusing me

Sep 19 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a
Wo*********@gmail.com wrote:
Something I don't really understand.

In http://maxnoy.com/interviews.html, Insert and Delete for linked list
are defined as:

int Insert(node **head, int data)
If you have a node *head; and want to delete the first node,
you need to change that pointer (to e.g. point to the next node).

Passing 'head' to a delete function, it can't change that pointer
only what it points to. So for the delete function to change that
pointer you must pass the address of that pointer.
and

int Delete(node** head, int deleteMe)

I thought linked-list is always defined as something like struct node
*head. Why the author defined the linked-list as pointer to pointer?
And in the next question he defines head in Split() as node *head. This
is really confusing me
Likely the Split function doesn't need to change the pointers of the caller,
just what the nodes points to.
Sep 19 '06 #2

P: n/a


Wo*********@gmail.com wrote:
Something I don't really understand.

In http://maxnoy.com/interviews.html, Insert and Delete for linked list
are defined as:

int Insert(node **head, int data)

and

int Delete(node** head, int deleteMe)

I thought linked-list is always defined as something like struct node
*head. Why the author defined the linked-list as pointer to pointer?
And in the next question he defines head in Split() as node *head. This
is really confusing me
Passing *head will pass pointer by value..Anty changes inside function
will not be reflected in claiing function
>
Sep 19 '06 #3

P: n/a

Wo*********@gmail.com wrote:
Something I don't really understand.

In http://maxnoy.com/interviews.html, Insert and Delete for linked list
are defined as:

int Insert(node **head, int data)

and

int Delete(node** head, int deleteMe)

I thought linked-list is always defined as something like struct node
*head. Why the author defined the linked-list as pointer to pointer?
And in the next question he defines head in Split() as node *head. This
is really confusing me
This is something which confused me too as a newbie coder, but once you
understand it, it's like achieving zen, it really is a very beautiful
part of the C language =)

When you call a function, the arguments are only *copies* of the
originals. So if function1 has a pointer, node *myhead, in it, then
what myhead really is is a very small chunk, call it chunk1, of memory
in which is stored an address to some other chunk of memory. If you
pass myhead to function2, this actually creates a NEW very small chunk
of memory, call it chunk2, copies the contents of chunk1 into chunk2,
and sends chunk2 to function2. At this point, function2 can go totally
crazy with chunk2, writing whatever crazy stuff it wants there, but
when we return to function1, the address in chunk1 will not have
changed. But suppose you have another function, function3, and you
*want* it to change the contents of chunk1 (as is the case with a list
insertion function). Then what you do is pass &myhead, the *address*
of chunk1. This creates a new small chunk, chunk3, on which is written
the address to chunk1, and passes that to function3. Now function3
knows where chunk1 is located, and therefore has the power to edit it.
Whereas function2 couldn't edit chunk1 if it wanted -- it doesn't know
where chunk1 is located!

Sep 19 '06 #4

P: n/a
"Nils O. Selåsdal" wrote:
Wo*********@gmail.com wrote:
>Something I don't really understand.

In http://maxnoy.com/interviews.html, Insert and Delete for
linked list are defined as:

int Insert(node **head, int data)

If you have a node *head; and want to delete the first node,
you need to change that pointer (to e.g. point to the next node).

Passing 'head' to a delete function, it can't change that pointer
only what it points to. So for the delete function to change that
pointer you must pass the address of that pointer.
It is simpler to define:

node *insert(node *list, int datum)

and then use it as

node *list = NULL /* i.e. empty */

...
while (something) list = insert(list, somedata);

which will normally result in inserting data at the head of a
list. It is a simple matter to reverse the list later, if
desirable. That way the implementation of insert can be:

node *insert(node *list, int datum)
{
node *temp;

if (NULL == (temp = malloc(sizeof *temp))
temp = list;
else {
temp->next = list;
temp->data = datum;
}
return temp
}

and there are no initialization effects to worry about.

--
"The most amazing achievement of the computer software industry
is its continuing cancellation of the steady and staggering
gains made by the computer hardware industry..." - Petroski

--
Posted via a free Usenet account from http://www.teranews.com

Sep 21 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.