For a general overview of pointers, read the first sections of Notes N20 from Math 10.
For a general overview of pointers in C++, read the last sections of Notes N20 from Math 10. (For a general overview of pointers in Fortran-90/95, read Notes: Fortran Pointers.
In C/C++, the asterisk operator * is used in conjunction with identifiers to indicate a pointer variable which is deferenced. (More explanation in a minute.)
(cf. F&T, p 389)
In general, one defines a record variable type (in C++, either as a struct or a class). For example,
class node
{ public:
int info;
node * next;
};
Note the use of the * between node and next in
the second field of the class definition of the node.
This indicates that next (by itself)
is actually a "pointer" to a node. Or (alternatively),
that *next is the node itself.
Then, after defining the new type, one declares variables of that type, for example,
node *p, *q, *r;
In this case, p, q, and r are all pointer
variables (without the *). WITH the *, they refer to the
structure they point to, in this case, a node. Thus
p
is a pointer to a node, that is, it is a variable which can
store an address of a node data-structure.
HOWEVER,
*p
is the (beginning of the) node which the variable p actually
points to.
After declaration of p, q, and r, the ONLY thing that has been allocated is the space for the pointer variables, which could point to node or could remain unused. THE NODES THEMSELVES HAVE NOT BEEN ALLOCATED.
(Cf. F&T, p 315)
In C++, to create the space for an actual node one needs to invoke the function new which takes the datatype as a quasi-argument as follows:
p = new node;
This allocates space from memory for the data structure we have
defined as a node and link p to that memory
space so that p now does, in fact, point to an
actual node.
Now p remains the pointer to a node, but the node itself is *p and we can assign values to its components by using the standard dot operator for records, such as:
(*p).info = 5;
(*p).next = NULL;
One usually replaces the *, () and . with the right arrow operator,
e.g.,
p->info = 5;
p->next = NULL;
(Cf. F&T, p. 317)
When nodes are no longer needed, one can release the memory for reuse byusing the library function/operator delete which takes a pointer to a node as the quasi-argument. Thus if p points to a node no longer needed, then
delete p;
will deallocate the memory used by the node and make it available for
reuse. The pointer variable Practical case: Suppose you implement a queue as a linked list, rather than with an array. After removing (i.e., dequeuing) an element from the queue, you should dispose of the node, so the space (now no longer neede by the queue) can be re-used by the program.
Problem: If one doesn't de-allocate (dispose of) the node space, one may lose a pointer to the node and not be able to use it or dispose of it!
node * genlist(int n)
{ node * p;
p = new node;
if (n>1)
p->next = genlist(n-1);
else
p->next = NULL;
p->info = n; //n is the unique number
//stored in each node after its creation
return(p);
}
Example B (Cf. DCS 6.3.3, p 58-9): Printing a List
void printlist(node * list)
{ node * temp;
temp = list;
do
{ cout << temp->info << " " ;
temp = temp->next;}
while (!(temp == NULL));
}
// FILE: test5.cxx
#include<iostream.h>
struct node {
int data;
node * next;
};
printlist(node * point)
{ node * temp;
temp = point;
do
{ cout << temp->data << " " ;
temp = temp->next;}
while (!(temp == NULL));
cout << "end of list" << endl;
}
main ()
{
node *p, *q, *r;
int temp;
//create space for node and let p point to that space
p = new node;
//now store appropriate values in both sections
p->next = NULL;
p->data = 1 ;
printlist(p);
//copy the data section of the node p points to
temp = p->data;
cout << temp << endl;
//create space for new and let q point to that space
q = new node;
//link the node p points to to this new node
p->next = q;
//now store appropriate values in both sections
q->data = 2;
q->next = NULL;
printlist(p);
//try again
r = new node;
q->next = r;
r->next = NULL;
r->data = 3;
printlist(p);
cout << "that's all folks!" << endl;
}
The output:
1 end of list 1 1 2 end of list 1 2 3 end of list that's all folks!
void insafter(node * p, int x)
{ node * q;
if (p == NULL) {
cout << "void insertion\n";
exit(1); }
else {
q = new node;
q->info = x;
q->next = p->next;
p->next = q; }
}
NOTE There is a similar function in F&T called
InsertAfter (pg 391). This is written as a member function
of the class Node and the major difference is that
it is given the pointer to a node containing information and so
does not need to create the node.
To insert 5 into a node after node P using the function given above, one would write:
insafter(P,5);
Using the functions in F&T, one would write:
temp = new Node<int>(5);
P->InsertAfter(temp);
void insend(node * list, int x)
{ node *p, *q;
p = new node;
p->info = x;
p->next = NULL;
if (list == NULL)
list = p;
else {
q = list;
while (q->next != NULL)
q = q->next;
q->next = p;}
}
void delafter(node * p, int & x)
{ node *q;
if (p == NULL) // NULL list
{ cout << "void deletion");
exit(1);
}
else
if (p->next == NULL) // 1 node list
{ cout << "void deletion\n");
exit(1);
}
else
{ q = p->next;
x = q->info;
p->next = q->next;
delete q;
}
}
NOTE There is a similar function in F&T called
DeleteAfter (pg 392). This is written as a member function
of the class Node and the major difference is that
it is a function which returns a pointer to the deleted node
rather than merely the contents of the deleted node.
node * search(node * list, int x)
{ node *p;
for (p = list; p != NULL; p = p->next)
if (p->info == x)
return p;
return NULL; // if x is not in the list
}
NOTE: This looks slightly different from the Pascal
version in DCS, due to the ability to use a return
statement in C/C++ and the power of the for loop in
C/C++.
The following routine, called find is a modification of search and return TWO pointers: p pointing to the node containing the desired element x, and prev pointing to the node BEFORE the node p points to. Knowledge of prev would be necessary if one want (for example) to delete the node containing x after locating it.
void find(node * list, int x, node* & p, node* & prev)
{ prev = list;
for (p = list; p != NULL; p = p->next)
if (p->info != x)
prev = p;
else
break;
}
NOTE: It is necessary to have both the * and the &
operators for the parameters p and prev. The
* indicates that each parameter is a pointer variable, and the
& indicates that the value can be changed.
This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 6 April 1999.