Question about usage of pointer in trees, linked list (The double indirection)

Discussion in 'C++' started by william, Mar 10, 2007.

  1. william

    william Guest

    When implementing Linked list, stack, or trees, we always use pointers
    to 'link' the nodes.
    And every node is always defined as:
    struct node
    {
    type data; //data this node contains
    ...
    node * nPtr; //the next node's pointer
    }

    And we also define operations as insert, delete, etc. on the data
    structure.
    MY QUESTION IS:
    why we always pass node**(pointer to the pointer to the node) as
    argument to these operations? Why we can not just use the node *?

    Thank you!

    Ji
    william, Mar 10, 2007
    #1
    1. Advertising

  2. Re: Question about usage of pointer in trees, linked list (The doubleindirection)

    william wrote:
    > When implementing Linked list, stack, or trees, we always use pointers
    > to 'link' the nodes.
    > And every node is always defined as:
    > struct node
    > {
    > type data; //data this node contains
    > ...
    > node * nPtr; //the next node's pointer
    > }
    >
    > And we also define operations as insert, delete, etc. on the data
    > structure.
    > MY QUESTION IS:
    > why we always pass node**(pointer to the pointer to the node) as
    > argument to these operations? Why we can not just use the node *?
    >
    > Thank you!
    >
    > Ji
    >


    In a good implementation of a linked list, the nodes are completely
    hidden. You would never pass node* or node** to any operations.

    What you are looking at is a bad implementation of a linked list. I
    can't tell you why it uses node** or node* without seeing the code. It
    shouldn't use either.

    john
    John Harrison, Mar 10, 2007
    #2
    1. Advertising

  3. william

    Ian Collins Guest

    Re: Question about usage of pointer in trees, linked list (The doubleindirection)

    william wrote:
    > When implementing Linked list, stack, or trees, we always use pointers
    > to 'link' the nodes.
    > And every node is always defined as:
    > struct node
    > {
    > type data; //data this node contains
    > ...
    > node * nPtr; //the next node's pointer
    > }
    >
    > And we also define operations as insert, delete, etc. on the data
    > structure.
    > MY QUESTION IS:
    > why we always pass node**(pointer to the pointer to the node) as
    > argument to these operations? Why we can not just use the node *?
    >

    So the value of the pointer can be changed, as well as the value the
    pointer point to.

    --
    Ian Collins.
    Ian Collins, Mar 10, 2007
    #3
  4. william

    william Guest

    On Mar 10, 3:48 pm, John Harrison <> wrote:
    > william wrote:
    > > When implementing Linked list, stack, or trees, we always use pointers
    > > to 'link' the nodes.
    > > And every node is always defined as:
    > > struct node
    > > {
    > > type data; //data this node contains
    > > ...
    > > node * nPtr; //the next node's pointer
    > > }

    >
    > > And we also define operations as insert, delete, etc. on the data
    > > structure.
    > > MY QUESTION IS:
    > > why we always pass node**(pointer to the pointer to the node) as
    > > argument to these operations? Why we can not just use the node *?

    >
    > > Thank you!

    >
    > > Ji

    >
    > In a good implementation of a linked list, the nodes are completely
    > hidden. You would never pass node* or node** to any operations.


    What does it mean by nodes are completely hidden(as being refered to,
    nodes means the pointers to the actual struct block in memory, or the
    structs themselves?)
    >
    > What you are looking at is a bad implementation of a linked list. I
    > can't tell you why it uses node** or node* without seeing the code. It
    > shouldn't use either.
    >
    > john


    I paste the sample code below, which came from the book 'C how to
    program'. John, could you please offer me a good example of
    implementation of linked list? Thank you.

    **********************************************************************
    #include <stdio.h>
    #include <stdlib.h>

    struct listNode
    {
    char data;
    struct listNode *nextPtr;
    };

    typedef struct listNode ListNode;
    typedef ListNode *ListNodePtr;

    void insert(ListNodePtr *, char);
    char delete(ListNodePtr *, char);
    int isEmpty(ListNodePtr);
    void printList(ListNodePtr);
    void instructions(void);

    int main()
    {
    ListNodePtr startPtr=NULL;
    int choice;
    char item;

    instructions(); //display the menu;
    printf(">");
    scanf("%d",&choice);

    while(choice!=3)
    {
    switch (choice)
    {
    case 1:
    printf("Enter a character: ");
    scanf("\n%c",&item);
    insert(&startPtr,item);
    printList(startPtr);
    break;

    case 2:
    if(!isEmpty(startPtr))
    {
    printf("Enter character to be deleted: ");
    scanf("\n%c",&item);

    if(delete(&startPtr,item))
    {
    printf("%c deleted.\n",item);
    printList(startPtr);
    }
    else
    printf("%c not found.\n\n",item);
    }
    else
    printf("List is empty.\n\n");
    break;
    default:
    printf("Invalid choice.\n\n");
    instructions();
    break;
    }
    printf(">");
    scanf("%d",&choice);
    }
    printf("End of run.\n");
    return 0;
    }

    void instructions(void)
    {
    printf("Enter your choice:\n");
    printf("1 to insert an element into the list.\n"
    "2 to delete an element from the list.\n"
    "3 to exit the program.\n");
    }

    void insert(ListNodePtr *sPtr, char value)
    {
    ListNodePtr newPtr, previousPtr, currentPtr;

    newPtr=malloc(sizeof(ListNode));
    if(newPtr !=NULL)
    {
    newPtr->data=value;
    newPtr->nextPtr=NULL;

    //set the searching index(previousPtr and
    //currentPtr)to the start of the list.
    previousPtr=NULL;
    currentPtr=*sPtr;

    while(currentPtr !=NULL && value>currentPtr->data)
    {
    previousPtr=currentPtr;
    currentPtr=currentPtr->nextPtr;
    } //keep going

    if(previousPtr==NULL)
    {
    newPtr->nextPtr=*sPtr;
    *sPtr=newPtr;//insert the node at the beginning of the list
    }
    else
    {
    previousPtr->nextPtr=newPtr;
    newPtr->nextPtr=currentPtr;
    }
    }
    else
    {
    printf("%c not inserted. No memory available.\n",value);
    }
    }

    char delete(ListNodePtr *sPtr, char value)
    {
    ListNodePtr previousPtr,currentPtr,tempPtr;

    if (value==(*sPtr)->data)
    {
    tempPtr=*sPtr;
    *sPtr=(*sPtr)->nextPtr;
    free(tempPtr);
    return value;
    }
    else
    {
    previousPtr=*sPtr;
    currentPtr=(*sPtr)->nextPtr;//setup the cursor at the beginning

    //when the cursor didn't reach the tail and cursor didn't find the
    //specified value, the cursor keep going along the list
    while(currentPtr !=NULL && currentPtr->data !=value)
    {
    previousPtr=currentPtr;
    currentPtr=currentPtr->nextPtr;//move on to next node
    }

    if(currentPtr !=NULL)//if not reaching the tail
    {
    tempPtr=currentPtr;
    previousPtr->nextPtr=currentPtr->nextPtr;
    free(tempPtr);
    return value;
    }
    }
    return '\0';//return null char;
    }

    int isEmpty(ListNodePtr sPtr)
    {
    return sPtr==NULL;
    }

    void printList(ListNodePtr currentPtr)
    {
    if(currentPtr==NULL)
    {
    printf("List is Empty.\n\n");
    }
    else
    {
    printf("The list is:\n");
    while(currentPtr !=NULL)
    {
    printf("%c--> ",currentPtr->data);
    currentPtr=currentPtr->nextPtr;
    }
    printf("NULL\n\n");
    }

    }
    ****************************************************************
    william, Mar 10, 2007
    #4
  5. william

    william Guest

    On Mar 10, 4:44 pm, "william" <> wrote:
    > On Mar 10, 3:48 pm, John Harrison <> wrote:
    >
    >
    >
    > > william wrote:
    > > > When implementing Linked list, stack, or trees, we always use pointers
    > > > to 'link' the nodes.
    > > > And every node is always defined as:
    > > > struct node
    > > > {
    > > > type data; //data this node contains
    > > > ...
    > > > node * nPtr; //the next node's pointer
    > > > }

    >
    > > > And we also define operations as insert, delete, etc. on the data
    > > > structure.
    > > > MY QUESTION IS:
    > > > why we always pass node**(pointer to the pointer to the node) as
    > > > argument to these operations? Why we can not just use the node *?

    >
    > > > Thank you!

    >
    > > > Ji

    >
    > > In a good implementation of a linked list, the nodes are completely
    > > hidden. You would never pass node* or node** to any operations.

    >
    > What does it mean by nodes are completely hidden(as being refered to,
    > nodes means the pointers to the actual struct block in memory, or the
    > structs themselves?)
    >
    >
    >
    > > What you are looking at is a bad implementation of a linked list. I
    > > can't tell you why it uses node** or node* without seeing the code. It
    > > shouldn't use either.

    >
    > > john

    >
    > I paste the sample code below, which came from the book 'C how to
    > program'. John, could you please offer me a good example of
    > implementation of linked list? Thank you.
    >
    > **********************************************************************
    > #include <stdio.h>
    > #include <stdlib.h>
    >
    > struct listNode
    > {
    > char data;
    > struct listNode *nextPtr;
    >
    > };
    >
    > typedef struct listNode ListNode;
    > typedef ListNode *ListNodePtr;
    >
    > void insert(ListNodePtr *, char);
    > char delete(ListNodePtr *, char);
    > int isEmpty(ListNodePtr);
    > void printList(ListNodePtr);
    > void instructions(void);
    >
    > int main()
    > {
    > ListNodePtr startPtr=NULL;
    > int choice;
    > char item;
    >
    > instructions(); //display the menu;
    > printf(">");
    > scanf("%d",&choice);
    >
    > while(choice!=3)
    > {
    > switch (choice)
    > {
    > case 1:
    > printf("Enter a character: ");
    > scanf("\n%c",&item);
    > insert(&startPtr,item);
    > printList(startPtr);
    > break;
    >
    > case 2:
    > if(!isEmpty(startPtr))
    > {
    > printf("Enter character to be deleted: ");
    > scanf("\n%c",&item);
    >
    > if(delete(&startPtr,item))
    > {
    > printf("%c deleted.\n",item);
    > printList(startPtr);
    > }
    > else
    > printf("%c not found.\n\n",item);
    > }
    > else
    > printf("List is empty.\n\n");
    > break;
    > default:
    > printf("Invalid choice.\n\n");
    > instructions();
    > break;
    > }
    > printf(">");
    > scanf("%d",&choice);
    > }
    > printf("End of run.\n");
    > return 0;
    >
    > }
    >
    > void instructions(void)
    > {
    > printf("Enter your choice:\n");
    > printf("1 to insert an element into the list.\n"
    > "2 to delete an element from the list.\n"
    > "3 to exit the program.\n");
    >
    > }
    >
    > void insert(ListNodePtr *sPtr, char value)
    > {
    > ListNodePtr newPtr, previousPtr, currentPtr;
    >
    > newPtr=malloc(sizeof(ListNode));
    > if(newPtr !=NULL)
    > {
    > newPtr->data=value;
    > newPtr->nextPtr=NULL;
    >
    > //set the searching index(previousPtr and
    > //currentPtr)to the start of the list.
    > previousPtr=NULL;
    > currentPtr=*sPtr;
    >
    > while(currentPtr !=NULL && value>currentPtr->data)
    > {
    > previousPtr=currentPtr;
    > currentPtr=currentPtr->nextPtr;
    > } //keep going
    >
    > if(previousPtr==NULL)
    > {
    > newPtr->nextPtr=*sPtr;
    > *sPtr=newPtr;//insert the node at the beginning of the list
    > }
    > else
    > {
    > previousPtr->nextPtr=newPtr;
    > newPtr->nextPtr=currentPtr;
    > }
    > }
    > else
    > {
    > printf("%c not inserted. No memory available.\n",value);
    > }
    >
    > }
    >
    > char delete(ListNodePtr *sPtr, char value)
    > {
    > ListNodePtr previousPtr,currentPtr,tempPtr;
    >
    > if (value==(*sPtr)->data)
    > {
    > tempPtr=*sPtr;
    > *sPtr=(*sPtr)->nextPtr;
    > free(tempPtr);
    > return value;
    > }
    > else
    > {
    > previousPtr=*sPtr;
    > currentPtr=(*sPtr)->nextPtr;//setup the cursor at the beginning
    >
    > //when the cursor didn't reach the tail and cursor didn't find the
    > //specified value, the cursor keep going along the list
    > while(currentPtr !=NULL && currentPtr->data !=value)
    > {
    > previousPtr=currentPtr;
    > currentPtr=currentPtr->nextPtr;//move on to next node
    > }
    >
    > if(currentPtr !=NULL)//if not reaching the tail
    > {
    > tempPtr=currentPtr;
    > previousPtr->nextPtr=currentPtr->nextPtr;
    > free(tempPtr);
    > return value;
    > }
    > }
    > return '\0';//return null char;
    >
    > }
    >
    > int isEmpty(ListNodePtr sPtr)
    > {
    > return sPtr==NULL;
    >
    > }
    >
    > void printList(ListNodePtr currentPtr)
    > {
    > if(currentPtr==NULL)
    > {
    > printf("List is Empty.\n\n");
    > }
    > else
    > {
    > printf("The list is:\n");
    > while(currentPtr !=NULL)
    > {
    > printf("%c--> ",currentPtr->data);
    > currentPtr=currentPtr->nextPtr;
    > }
    > printf("NULL\n\n");
    > }
    >
    > }
    >
    > ****************************************************************


    Above is all the code.

    here is the segment that confuses me:

    in 'main':
    ListNodePtr startPtr=NULL;
    ....
    ....
    insert(&startPtr,item);
    ....
    And the prototype of 'insert' is:
    void insert(ListNodePtr *, char);
    // you can find the content in the code segment I posted just now.

    So, is there any CONVENTION that how programmers implement different
    data structure:
    LINKED LIST
    TREE
    QUEQUE
    STACK
    and define operations on those data structure?

    Where can I find a good resource talking about this?
    william, Mar 10, 2007
    #5
  6. william

    Ian Collins Guest

    Re: Question about usage of pointer in trees, linked list (The doubleindirection)

    william wrote:
    >
    > Above is all the code.
    >
    > here is the segment that confuses me:
    >
    > in 'main':
    > ListNodePtr startPtr=NULL;
    > ....
    > ....
    > insert(&startPtr,item);
    > ....
    > And the prototype of 'insert' is:
    > void insert(ListNodePtr *, char);


    What part of this confuses you? If insert didn't take the address of
    startPtr, how could it change it?

    --
    Ian Collins.
    Ian Collins, Mar 10, 2007
    #6
  7. william

    Kai-Uwe Bux Guest

    william wrote:
    [snip]
    > So, is there any CONVENTION that how programmers implement different
    > data structure:
    > LINKED LIST
    > TREE
    > QUEQUE
    > STACK
    > and define operations on those data structure?


    Yes, there is: you don't implement them yourself, you use the standard
    library instead. It provides (among other things):

    std::list
    std::queue
    std::stack

    and for problems involving search trees:

    std::set, std::multiset
    std::map, std::multimap


    > Where can I find a good resource talking about this?


    Any introduction to the standard library should cover the standard container
    classes and adaptors.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Mar 10, 2007
    #7
  8. Re: Question about usage of pointer in trees, linked list (The doubleindirection)

    >
    >
    > I paste the sample code below, which came from the book 'C how to
    > program'. John, could you please offer me a good example of
    > implementation of linked list? Thank you.


    I didn't realise you were programming in C. C and C++ are different
    languages, what is good in C not the same as what is good in C++.

    The code below is probably fine in C, but it wouldn't be good C++. In
    C++ it's much easier to seperate the interface from the implementation.

    If you haven't got your answer already (Ian has given you the answer)
    you should probably ask questions about this code on comp.lang.c, it's C
    not C++.

    john
    John Harrison, Mar 10, 2007
    #8
  9. william

    william Guest

    On Mar 10, 5:00 pm, Ian Collins <> wrote:
    > william wrote:
    >
    > > Above is all the code.

    >
    > > here is the segment that confuses me:

    >
    > > in 'main':
    > > ListNodePtr startPtr=NULL;
    > > ....
    > > ....
    > > insert(&startPtr,item);
    > > ....
    > > And the prototype of 'insert' is:
    > > void insert(ListNodePtr *, char);

    >
    > What part of this confuses you? If insert didn't take the address of
    > startPtr, how could it change it?
    >

    Thank you Ian, I understand it now. The whole structure is a
    pointer(to the starting struct), so we need to change it if we insert
    a new node at the beginning, right?
    > --
    > Ian Collins.
    william, Mar 10, 2007
    #9
  10. william

    william Guest

    On Mar 10, 5:09 pm, Kai-Uwe Bux <> wrote:
    > william wrote:
    >
    > [snip]
    >
    > > So, is there any CONVENTION that how programmers implement different
    > > data structure:
    > > LINKED LIST
    > > TREE
    > > QUEQUE
    > > STACK
    > > and define operations on those data structure?

    >
    > Yes, there is: you don't implement them yourself, you use the standard
    > library instead. It provides (among other things):
    >
    > std::list
    > std::queue
    > std::stack
    >
    > and for problems involving search trees:
    >
    > std::set, std::multiset
    > std::map, std::multimap
    >
    > > Where can I find a good resource talking about this?

    >
    > Any introduction to the standard library should cover the standard container
    > classes and adaptors.
    >
    > Best
    >
    > Kai-Uwe Bux


    Thank you for your reply! I got it.

    regards

    Ji
    william, Mar 10, 2007
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nobody
    Replies:
    5
    Views:
    3,235
    Nobody
    Nov 11, 2003
  2. Sydex
    Replies:
    12
    Views:
    6,475
    Victor Bazarov
    Feb 17, 2005
  3. fool
    Replies:
    14
    Views:
    502
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    665
    John Carson
    Oct 2, 2006
  5. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,411
    Dann Corbit
    Jan 8, 2010
Loading...

Share This Page