Linked list declaration

[WongMingYin]

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

[Nils O. Selåsdal]

Wo*********@gma il.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.

[shyam]

Wo*********@gma il.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

>

[Snis Pilbor]

Wo*********@gma il.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!

[CBFalconer]

"Nils O. Selåsdal" wrote:

Wo*********@gma il.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