On Mar 10, 3:48 pm, John Harrison <john_androni.. .@hotmail.comwr ote:
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(ListNode Ptr *, char);
char delete(ListNode Ptr *, char);
int isEmpty(ListNod ePtr);
void printList(ListN odePtr);
void instructions(vo id);
int main()
{
ListNodePtr startPtr=NULL;
int choice;
char item;
instructions(); //display the menu;
printf(">");
scanf("%d",&cho ice);
while(choice!=3 )
{
switch (choice)
{
case 1:
printf("Enter a character: ");
scanf("\n%c",&i tem);
insert(&startPt r,item);
printList(start Ptr);
break;
case 2:
if(!isEmpty(sta rtPtr))
{
printf("Enter character to be deleted: ");
scanf("\n%c",&i tem);
if(delete(&star tPtr,item))
{
printf("%c deleted.\n",ite m);
printList(start Ptr);
}
else
printf("%c not found.\n\n",ite m);
}
else
printf("List is empty.\n\n");
break;
default:
printf("Invalid choice.\n\n");
instructions();
break;
}
printf(">");
scanf("%d",&cho ice);
}
printf("End of run.\n");
return 0;
}
void instructions(vo id)
{
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(ListNode Ptr *sPtr, char value)
{
ListNodePtr newPtr, previousPtr, currentPtr;
newPtr=malloc(s izeof(ListNode) );
if(newPtr !=NULL)
{
newPtr->data=value;
newPtr->nextPtr=NULL ;
//set the searching index(previousP tr and
//currentPtr)to the start of the list.
previousPtr=NUL L;
currentPtr=*sPt r;
while(currentPt r !=NULL && value>currentPt r->data)
{
previousPtr=cur rentPtr;
currentPtr=curr entPtr->nextPtr;
} //keep going
if(previousPtr= =NULL)
{
newPtr->nextPtr=*sPt r;
*sPtr=newPtr;//insert the node at the beginning of the list
}
else
{
previousPtr->nextPtr=newPtr ;
newPtr->nextPtr=curren tPtr;
}
}
else
{
printf("%c not inserted. No memory available.\n",v alue);
}
}
char delete(ListNode Ptr *sPtr, char value)
{
ListNodePtr previousPtr,cur rentPtr,tempPtr ;
if (value==(*sPtr)->data)
{
tempPtr=*sPtr;
*sPtr=(*sPtr)->nextPtr;
free(tempPtr);
return value;
}
else
{
previousPtr=*sP tr;
currentPtr=(*sP tr)->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(currentPt r !=NULL && currentPtr->data !=value)
{
previousPtr=cur rentPtr;
currentPtr=curr entPtr->nextPtr;//move on to next node
}
if(currentPtr !=NULL)//if not reaching the tail
{
tempPtr=current Ptr;
previousPtr->nextPtr=curren tPtr->nextPtr;
free(tempPtr);
return value;
}
}
return '\0';//return null char;
}
int isEmpty(ListNod ePtr sPtr)
{
return sPtr==NULL;
}
void printList(ListN odePtr currentPtr)
{
if(currentPtr== NULL)
{
printf("List is Empty.\n\n");
}
else
{
printf("The list is:\n");
while(currentPt r !=NULL)
{
printf("%c--",currentPt r->data);
currentPtr=curr entPtr->nextPtr;
}
printf("NULL\n\ n");
}
}
*************** *************** *************** *************** ****
