Re: Question about usage of pointer in trees, linked list (The double indirection)
On Mar 10, 3:48 pm, John Harrison <john_androni...@hotmail.com> 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");
}
}
****************************************************************