Linked List problem

This is a discussion on Linked List problem within the C Programming forums, part of the General Programming Boards category; Here is a basic program for insertion at the beginning of a LL. Code: void insert( node **head, int item) ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Location
    Kolkata
    Posts
    20

    Linked List problem

    Here is a basic program for insertion at the beginning of a LL.

    Code:
     void insert( node **head, int item)
    {
    node *ptr;
    ptr=(node *) malloc(sizeof(node));
    ptr->info= item;
    if( *head == NULL)
    ptr->next = NULL;
    else
    ->ptr->next = *head;
    *head = ptr;
    }
    I have a fair idea of double pointers. Please will you tell me what exactly is the need of using a double pointer to head here in this code? node * head would have sufficed I believe.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    Consider this line:
    Code:
    *head = ptr;
    suppose head was a node* instead of a node**. How would you rewrite the above line to reflect this, and then what would happen (or not happen)?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2013
    Location
    Kolkata
    Posts
    20
    What does a *node_name hold? Since a node is a structure of multiple data types, what does *node_name fetch? I know int *c, *c would fetch the integer stored at address pointed to by c.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    So you have a pointer named ptr, right. Now imagine you did this:

    node **head = &ptr;

    Now *head == ptr. Does this help? It should make sense to you that a pointer is also stored in a location with a memory address.

  5. #5
    Registered User
    Join Date
    Jan 2013
    Location
    Kolkata
    Posts
    20
    Why exactly do we need double pointers as arguments here? Can't the same be achieved without it? Eg. instead of what you suggested,

    node * head = &ptr;
    head== ptr;

    works the same way, or don't they? Please explain.

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Why don't you run it to found out yourself what is happening?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    Why exactly do we need double pointers as arguments here?
    A pointer is declared by naming the thing it points to followed by an asterisk (*). If the pointer points to a pointer then the type of that is a "double pointer".

    If you tried to compile:

    node *head = &ptr;

    you should get at least a warning. The location being assigned and the object being assigned are not the same type.

  8. #8
    Registered User
    Join Date
    Nov 2011
    Location
    Saratoga, California, USA
    Posts
    334
    Quote Originally Posted by Prateek Sarkar View Post
    Please will you tell me what exactly is the need of using a double pointer to head here in this code? node * head would have sufficed I believe.
    'node * head' would not suffice. You are modifying 'head' within your insert() function, so as with everything you wish to modify directly from within a function, you need a pointer to it. Since it exists as 'node *head' back in main() or wherever, it's address will be passed as a double pointer to node.

    If you were inserting the node at the tail, it would be a different story, but you are inserting at the head and therefore your entry point into the linked list must be modified. Imagine if it weren't.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Prateek Sarkar View Post
    Why exactly do we need double pointers as arguments here? Can't the same be achieved without it?
    No.

    Are you familar with pass-by-value vs pass-by-pointer? One reason you pass by pointer is if you want to modify the value, as modifying the argument when passed by value has no effect outside of the function.
    Now consider what happens if the thing you want to modify is itself a pointer... You have to pass that pointer by pointer! I.e. double-pointer.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Ultraviolence Connoisseur
    Join Date
    Mar 2004
    Posts
    524
    It's called a pointer-to-pointer not a "double pointer" which implies pointing to 2 places at once and is impossible in C. Also that name makes it more clear the function in this case

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Yes indeed. I should have tried to correct the use of terminology rather than using what term the poster was familar with.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jan 2013
    Location
    Kolkata
    Posts
    20
    Thanks a lot everyone.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with my linked list.
    By Hitiro in forum C++ Programming
    Replies: 0
    Last Post: 08-31-2011, 10:23 AM
  2. Problem in Linked List
    By hqt in forum C Programming
    Replies: 1
    Last Post: 08-15-2011, 06:16 AM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. syntax linked list problem & struct problem
    By beely in forum C Programming
    Replies: 5
    Last Post: 11-11-2002, 09:14 AM
  5. Linked List problem
    By unregistered in forum C Programming
    Replies: 65
    Last Post: 04-16-2002, 11:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21