Topics to Cover

Pointers to a single struct object

Until now, we've used pointers to point to arrays of objects, rather than individual objects. It turns out that pointers to individual objects are very important in a wide range of circumstances.

new and delete

You can allocate a single object of a given type by just leaving the square brackets off the new statement. For example, to create a single 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 ->

In order to access a data-member of a struct from a pointer, one can use the dereference operator *.
Using dereference operator * Using operator -> (recommended) 

point* ptr = new point;
(*ptr).x = 0;
(*ptr).y = 0;
 

point* ptr = new point;
ptr->x = 0;
ptr->y = 0;
However, there is a more convenient way; that is, we can also use the -> operator. The two code chunks above are equivalent.

Linked List Intro

One big reason to have a pointer to a single object is "linked lists", which we'll be studying extensively in the next several lessons. Up to this point we've used arrays to store a sequential collection of objects.

Limitations of arrays

Arrays are great, but they have a few limitations that cause us some headaches.
  1. The size of an array is fixed from the moment it is allocated with new, so you always have to know how many objects you want to store ahead of time.
  2. Inserting an element to the front of an array or somewhere in the middle is a big job - first you need extra "room" in the array, and second you need to move everything else in the array back an element, which is a lot of work.
Linked lists are an alternative to arrays that avoids these limitations.

Node of a linked list

A linked list consists of "nodes", each of which contains The following picture shows a linked list storing the numbers 87, 42, 53, 4.

You absolutely have to keep this kind of picture in mind if you want to program with linked lists!

Representing a node in C++

To realize this picture in C++ code, we see that we have to manipulate "nodes". 

struct Node
{
  int data;
  Node* next;
};

NULL pointer

By convention, the 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".

Manipulating a linked list in your program

Remember that we manipulate an array in our programs by manipulating a pointer variable that points to the array. Similarly, we manipulate a linked list by manipulating a pointer to the first node in the list.

1. Empty list

Now, we might have a variable of type Node* called LIST: 

Node* LIST = NULL;
Initially LIST points to NULL, which means the list contains no nodes. 		 

2. Data have been added

Suppose that data have been added; we will talk about how to do this soon. The variable LIST then points to the first node in our linked list of integers. Our list might look something like this:

3. Printing out the first integer

We could print out the first integer in our list with the statement 
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.

4. Printing out the second integer

Now, to print out the second integer in the list, we'd like to say the same thing, except instead of 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 guess
Actually you don't need the parentheses, because the -> is left associative.

5. Printing out the third integer

To print out the third element of the list you could write: 

cout << LIST->next->next->data;

Adding a Node

Adding a Node to the front of a list is a pretty straightforward thing:
  1. You create a new Node
  2. Set it's data and next fields
  3. set LIST to point to it, since it's supposed to be the new "first node in the list".

Mandatory Practice Problem

For each code below, draw a diagram accordingly.
Initially we have:
Node* temp = new Node;
diagram
temp->data = 8;
diagram
temp->next = LIST;
diagram
LIST = temp;
diagram
At the end we have:

Conclusion

Whenever you want to add a new value 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;

The same code works for an empty list too!

When speaking of lists, it's really handy to have the concept of an empty list, i.e. a list of zero nodes.

Recall: Representing an empty list

Recall that in our programs, we represent an empty list by a null pointer, i.e. with a pointer whose value is NULL.

The same code works!

The sequence of steps we used to add a new element to the front of a list works perfectly well even when the list is empty. In the example below,
  • LIST is empty.
  • The exact same sequnce of steps we used above will add the new value 3 to the "front" of the list.
Initially we have:
Node* temp = new Node;
temp->data = 3;
temp->next = LIST;
LIST = temp;
At the end we have:

add2front() function

At this point, we should have the idea that, since we have a fixed sequence of steps that add a new element to the front of a list, we might want to make a function!

Wrong version

Based on the above discussion, you might be tempted to write the following:

 // WARNING! THIS VERSION DOESN'T WORK!!
void add2front(int val, Node* oldlist) 
{
  Node* temp = new Node;            // Make a new node
  temp->data = val;                 // Set the node’s value field
  temp->next = oldlist;             // Set the node’s next to the beginning of the oldlist
  oldlist = temp;                   // Set the beginning of the list to our new node
}

So what’s the problem? Well everything here is correct except for the last step, where we want to “set the beginning of the list to our new node”. The issue is that in C, function arguments are a copy of the original using pass by value.

In this case, the oldlist argument itself is just a copy of the original LIST pointer that might be inside our main. So changing the value of oldlist on the last line of the function just changes the copied pointer, not the original pointer inside main or wherever this function was called from!

Correct version

We will solve the problem by using the return value from the function, as a way of passing the pointer to the newly-created node back to the place where this function was called, like so: 
// correct version: returns a pointer to the new list
Node* add2front(int val, Node* oldlist)
{
  Node* temp = new Node;		
  temp->data = val;			
  temp->next = oldlist; 		
  return temp;				// return the new list!
}

Using add2front()

Now in your program you have to use this return value! Typically, if you have your linked list defined as

Node* LIST;

inside main, then you would write

LIST = add2front(3, LIST);

to add a new node with value 3 to the front of LIST. Notice that the pointer variable LIST shows up in two places in that line of code - once as the argument to the function (the “old list”), and once as the left hand side getting the new front of the list assigned to it. This is a very common pattern in functions that manipulate linked lists, so learn to love it!

Armed with thie add2front function, the very tedious example above of making a linked list with 4 numbers can be done much, much more simply:

Node* LIST = NULL;
LIST = add2front(4, LIST);
LIST = add2front(53, LIST);
LIST = add2front(42, LIST);
LIST = add2front(87, LIST);

Which results in the picture on the right:

Notice: we added the elements to the list in reverse order from how they ended up! Since we are always adding to the front of the list, the last thing we add has to be the first thing in the list.

Sample code

Check out Here; it is an example program that reads ints from the user and stores them in a linked list using the add2front function.

Practice Problems?

The type of object stored in the 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: I don't want to post solutions to these right now, since we'll be looking at these in labs.