By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,260 Members | 1,309 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
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 <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");
}

}
************************************************** **************
Mar 10 '07 #4

P: n/a
On Mar 10, 4:44 pm, "william" <william.m...@gmail.comwrote:
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");
}

}

************************************************** **************
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 <ian-n...@hotmail.comwrote:
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.

Mar 10 '07 #9

P: n/a
On Mar 10, 5:09 pm, Kai-Uwe Bux <jkherci...@gmx.netwrote:
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

Mar 10 '07 #10

This discussion thread is closed

Replies have been disabled for this discussion.