1

I am learning linked list operations and have a question related to parameter passing.

Question 1: I am creating a simple linked list with three values 1->2->3. And am trying to print it. Below is my code. I am creating a node "first" in my main and am passing it to the method "createlinkedlist". I am using a pointer "head" and updating it within the method. But I see that the values of "head" are retained correctly outside the method "createlinkedlist". I dont understand how this is happening. I was thinking I should use referencial parameter passing like

void createLinkedList(struct node * & head) or void createLinkedList(struct node ** head)

instead of 

void createLinkedList(struct node * head)

to get the correct values reflected outside the function. What am I missing here? Why am I able to see the correct values inside the printList method? 

 struct node
{
    int data;
    struct node * next;

};

void createLinkedList(struct node * head)
{

    struct node * second = (node *)malloc(sizeof(node));
    struct node * third = (node *)malloc(sizeof(node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

}

void printList(struct node * first)
{
struct node * current = first;
while(current)
{
printf("%d",current->data);
current = current->next;
}
}
void main()
{
    struct node * first = (node *)(malloc(sizeof(node)));
    createLinkedList(first);
    printList(first);
}

Question 2: I am using the same program as above , but adding a push function

void push(struct node *& first, int data)
{
    struct node * newnode = (node*)malloc(sizeof(node));
    newnode->data = data;
    newnode->next = first;
    first = newnode;
}

Now I see that unless I use a "&" for the first parameter in the push(), I am not able to see the updations in the printList method. It makes sense to me because we usually need to use a referncial parameter to make the local function changes seen outside the function. So if the list expects a referencial parameter here, why does it behave differently in the question 1 case.? Pls. let me know.

Improve this question
2
  • * and & cancel out. It essentially means [struct node head] Commented Mar 7, 2011 at 20:48
  • 1
    @Ravi: I don't think that is the case for a declaration. Commented Mar 7, 2011 at 20:54

3 Answers 3

Reset to default
2

Regarding Question 1)

You are not changing the pointer head in your createLinkedList method; you are changing the contents of the node that head points to. So of course you see that change after having called createLinkedList.

Regarding Question 2)

In the second case, you are actually adding a new node and you need to change the head pointer to point to the new head of the linked list, whereas in the first case, you keep the head of the list stable and add new nodes to the tail of the list. So you don't need to get the new address of the head of the list back to the caller, since the address of the head didn't change.

I would also create a node constructor function:

struct node * make_node(int data)
{
  struct node * tmp = (node *)malloc(sizeof(node));
  if (!tmp) {
    /* error handling for malloc failure */
  }
  tmp->next = NULL;
  tmp->data = data;
  return tmp;
}

And another point:

If I were you, if I wrote a push function that added nodes to the head of the list, I would return the new head of the list explicitly:

struct node * push(const struct node * head, int data) {
   struct node * fresh = make_node(data)
   fresh->next = head;
   return fresh;
}

Calling this like so:

 struct node * head = make_node(1);
 head = push(head, 2);

This is easier to understand than figuring out that push(head, 1) changes the head. But it's a question of style.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Yeah, I agree with you JeSuisse that is much easier to understand, than having to deal with ref. parameters, but most of the books and links I see on linked list are implementing it with ref. parameters. So that made me thinking if that was much efficient way of doing it , in terms of memory and space utilization and performance.
Regarding question 1. My understanding after doing some research on that is that, "first" and "head" are just copies which point to the same memory location. So when I modify either one of them , the changes should be reflected onto the other.
Reg. References vs. return value: Actually references are a bit more efficient, because the compiler won't have to copy the return value into the head variable, but that's on the order of a couple machine instructions, which are negligible.
Reg. first and head: Yes, they are two pointer variables, both containing the same memory location. So even though first and head are two separate variables, that's irrelevant because they're pointing to the same thing, the node structure. Don't give up on pointers, they're immensly important! And BTW, references are just pointers in disguise.
Oh, and about space efficiency of reference passing: This isn't relevant, either, as the return value is usually stored in a machine register, so it doesn't take up any memory (and even if it did, it would only be 4 bytes). The main reason to do it over a reference argument instead of a return value is because to some programmers, it looks nicer/cleaner. As I said, a question of style. My take on it is to be as clear as possible as to what your code does, so I avoid changing a variable I pass into a function by reference if I can achieve the same result by a function return.
1

Change

struct node * first = (node *)(malloc(sizeof(node)));
struct node * second = (node *)(malloc(sizeof(node)));
struct node * third = (node *)(malloc(sizeof(node)));

parts to

struct node * first = (struct node *)(malloc(sizeof(struct node)));
struct node * second = (struct node *)(malloc(sizeof(struct node)));
struct node * third = (struct node *)(malloc(sizeof(struct node)));

. Since you initialized "node" without "typedef", "struct" needs to written before usage of "node" every time.

Improve this answer

Comments

0

Since you're talking about references I'll assume you're using C++.

You would want to pass in struct node *& head if you're going to modify the pointer to head, but in your example you want to only modify the head node itself, and not the pointer to it, which is why you simply pass a pointer to it to let you look up the address. When you dereference the pointer via head->... you are looking up the location of head in memory and then moving to its data or next field. Alternatively, you could pass in the head as a reference: struct node & head, and modify things like head.data directly.

Your push needs to have either a reference to the first pointer (struct node *& first), or a pointer to the "first" pointer (struct node **first) so that you can actually modify the pointer itself. This is what's happening on the line:

first = newnode;

Alternatively, if you used struct node **first, you would do:

*first = newnode;

Both cases here for push are modifying a pointer to a struct node, as opposed to modifying a struct node itself.

Improve this answer

1 Comment

Thks much guys. it helps a lot! i thk I am getting it now.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.