446,260 Members | 1,309 Online
Need help? Post your question and get tips & solutions from a community of 446,260 IT Pros & Developers. It's quick & easy.

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

 P: n/a 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 Mar 10 '07 #1
9 Replies

 P: n/a 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. Mar 10 '07 #2

 P: n/a 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 Mar 10 '07 #3

 P: n/a On Mar 10, 3:48 pm, John Harrison 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 #include 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"); } } ************************************************** ************** Mar 10 '07 #4

 P: n/a On Mar 10, 4:44 pm, "william" #include 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? Mar 10 '07 #5

 P: n/a 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. Mar 10 '07 #6

 P: n/a > > 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 Mar 10 '07 #7

 P: n/a 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 Mar 10 '07 #8

 P: n/a On Mar 10, 5:00 pm, Ian Collins

 P: n/a On Mar 10, 5:09 pm, Kai-Uwe Bux