On Mar 10, 3:48 pm, John Harrison <john_androni...@hotmail.comwrote:
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");
}
}
************************************************** **************
