new
and delete
point
object and a pointer, p
, that points to it, we
could write:
point* p = new point;
To delete the point
that p
points to, you
use the usual delete
statement, except without the
square brackets.
delete p;
->
->
operator. The pointer goes on the left, the
name of the data member goes on the right. For example:
point* ptr = new point;
ptr->x = 0;
ptr->y = 0;
new
, so you always have to know how many objects you want to
store ahead of time.
int
s that data would be an int
, in a
linked list of string
s that data would be a string
,
etc)
LIST
" in the picture. From there you simply
follow the links (arrows) from one piece of data to the next.
The last node in a linked list does not have a link to a "next" node - we
usually show its next-field with a slash to indicate that.
Node
.
int
s
in our list, then a Node
will consist of a int
,
which we might call "data".
Node
- i.e. we need a member of type Node*
.
struct Node
{
int data;
Node* next;
};
next
field of the last element in the
list is set to the value NULL
(which is just defined to be
0) to indicate that it's not pointing to anything. In particular, consider the
following code:
if( 0 == NULL )
cout << "equal" << endl;
else
cout << "not equal" << endl;
The program will output equal
. We often call NULL
a "null
pointer".
Now, we might have a variable of type Node* called
LIST :
Initially LIST points to NULL, which means the list contains no nodes.
|
LIST
then points to the first node in our linked
list of integers. Our list might look something like this:
cout << LIST->data;
which says "print the data
field of the
Node
pointed to by LIST
". You can
simply follow that in the picture, it prints out 87.
LIST
, which points to the first
node in the list, we need a pointer to the second node in the list. Then we
could write:
cout << (pointer to the second node)->data;
Now, if you look back at the picture, you see that there is a
pointer to the second node in the list, it is the
next
field from the first node in the list, i.e.
LIST->next
is a pointer to the second node in the
list. So, to print out the second node in the list you write:
cout << (LIST->next)->data; // Drag your mouse and see if the answer matches your guessActually you don't need the parentheses, because the
->
is left associative.
cout << LIST->next->next->data;
On the other hand, this way lies madness! It's usually better to
simply make a temporary pointer that points to what you want, and
move that pointer through the list. For example:
Node* ptr = LIST; // Set ptr to point to first node
ptr = ptr->next; // Set ptr to point to second node
ptr = ptr->next; // Set ptr to point to third node
cout << ptr->data;
Node
data
and next
fields
LIST
to point to it, since it's supposed to be the
new "first node in the list".
Initially we have: | |
| |
| |
| |
| |
At the end we have: |
val
to the
front of a
linked list LIST
, the same sequence of steps will
do the job:
Node* temp = new Node;
temp->data = val;
temp->next = LIST;
LIST = temp;
LIST
is empty.
add2front()
functionadd2front()
val
that's supposed to be the data
for the new
node.
LIST
pointer, then the function better take the pointer to the
front of the list by reference!
Therefore, the prototype of the function should be as follows:
void add2front(int val, Node*& LIST); // Drag your mouse for the answer and verify your guess.
add2front()
add2front
in Here; it is an example program that reads ints
from the user and stores them in a linked list using the
add2front
function.
data
fields of
the nodes in a linked list are pretty much irrelevant to the
problem of how to manipulate a list. Therefore, we're going
to concentrate on basic linked list manipulations, which
provide us with a wealth of interesting problems. These
typically boil down to functions you'd like to define, like: