Linked List, pointer manipulation

Question

I am attaching below the code of head_insert to insert a new node at the head of a linked list. The function is called with head_insert(head).

I am not sure about the syntax of the first argument of the function, I was expecting NodePtr instead since it is already a pointer, see below.

Why the code uses NodePtr &head and not NodePtr head only as head is already a pointer?

void head_insert(NodePtr & head, int the_number)
{
  NodePtr temp_ptr;
  temp_ptr=new Node;
  temp_ptr->data=the_number;
  temp_ptr->link=head;
  head=temp_ptr;
}


struct Node
{
  int data;
  Node *link;
};

typedef Node* NodePtr;

why the code uses "NodePtr &head" and not "NodePtr head" only as head is already a pointer? — sara McKnight, Feb 18 '13 at 07:52
Don't tag questions with both [c] and [c++]. While C++ understands C code, what is considered good style in C is rarely good style in C++. — Jan Hudec, Feb 18 '13 at 07:52
@saraMcKnight: That should have been an edit, not a comment. — Jan Hudec, Feb 18 '13 at 07:53
but even if u pass per value, head will be changed as head holds an address of the head node — sara McKnight, Feb 18 '13 at 07:54
@saraMcKnight Yes, but what the function changes is that address itself, not the content stored at the address. This is only possible using a reference (or a pointer to pointer). — jogojapan, Feb 18 '13 at 07:56
@saraMcKnight: Pointer allows you to change the object it points to, but to change where the pointer points you need a reference (or pointer) to it. — Jan Hudec, Feb 18 '13 at 07:56

score 4 · Answer 1 · answered Feb 18 '13 at 07:52

4

why the code uses "NodePtr &head" and not "NodePtr head" only as head is already a pointer?

The reason is that it needs any changes that the function makes to head to be visible to the caller.

If head were passed by value (NodePtr head) rather than by reference (NodePtr& head) this wouldn't be the case: when the function would assign temp_ptr to head, this change wouldn't propagate back to the caller. Passing head by reference addresses this.

answered Feb 18 '13 at 07:52

NPE

486,780
108
951
1,012

but even if u pass per value, head will be changed as head holds an address of the head node – sara McKnight Feb 18 '13 at 07:56

score 0 · Answer 2 · answered Feb 18 '13 at 07:54

0

Your typedef is a little confusing at first glance. In C, you should pass a struct Node ** head argument and assign its value to the newly created node : *head = temp_ptr;. Here is what it would look like :

void head_insert(struct Node **head, int the number)
{
    struct Node *new_head = NULL;
    // Alloc memory for new_head, etc..
    new_head->data = the_number;
    new_head->link = *head;
    *head = new_head;
}

Thus, to make the assignment *head = new_head, you need to have a pointer to your list head which is also a pointer. Otherwise, the update performed in the function would remain local. In your code, you take a reference to a pointer, which has merely the same effect than passing a "double" pointer.

answered Feb 18 '13 at 07:54

Rerito

5,886
21
47

but if i used instead head_insert(struct Node *head,...) – sara McKnight Feb 18 '13 at 08:12
If you did that, the `head = new_head` would not affect `head` outside the function. – Rerito Feb 18 '13 at 08:17
It seems you are not aware of the stack behaviour. You should take a look at this SO question : http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap – Rerito Feb 18 '13 at 08:25
Briefly, the memory for the arguments of your function is on the _stack_, this makes them __LOCAL__ to a function call. That said, if you modify the address pointed by your `struct Node *head` argument, it will modify the value on the corresponding stack area which is only related to the _current_ function call. Consequently, when you exit the function, you lose the assignment. Hence the need for `struct Node **head` (or a C++ reference). – Rerito Feb 18 '13 at 08:28
Thanks Rerito...i get it now. any good textbook your recommend for further reading – sara McKnight Feb 18 '13 at 10:01
@saraMcKnight : Since you seem more interested in C++, check out the following SO question : http://tinyurl.com/so-cxxbooks Then, when you feel comfortable with C++ (and C), you can also dig in the system. A study of the Linux Kernel will bring you useful knowledge of how your program interacts with an OS – Rerito Feb 18 '13 at 10:26

Linked List, pointer manipulation

2 Answers2