Well before we can begin to answer that first we must understand dynamic memory allocation.

What is dynamic memory allocation?

In the C++ programming language we can request memory or RAM as either static and dynamic. Static memory is never changing - once it is requested it can not be used by any other program and it must be contiguous. Dynamic memory, on the other hand, opens a whole new world in memory allocation. Dynamic memory is granted at run-time but most importantly it no longer has to be contiguous. This is especially important when needing a large amount of RAM. It is not feasible to always know in advance how many records we will be entering for an array. This makes RAM allocation a big problem. We need to be able to enter records to an array and know that the memory will be granted as needed.

What is a linked list?

A linked list is defined as a list implemented by each item having a link to the next item.

Now that we have a basic idea of dynamic memory and a linked list we can begin to examine a dynamically allocated linked list.

First, lets build a structure called candles. It will contain a few fields concerning different scented candles.

struct  candles

   char  scent[20];

   char color[10];

   int  qty;

} *next, *can1;

This would mean that we need 40 contiguous bytes of storage.

With the previous code we could build the list below:

**sorted by alphabetically by scent

*next
Watermelon
Null
Mango
Peach
Pineapple

If we were look at the RAM we would see that 40 contiguous bytes of storage were not available.

7050-7052	7053-7060	7061-7072
Available	Assigned	Available
7073-7074	7075-7080	7081-7099
Assigned	Available	Assigned

How could we make use of the memory available even though it is not in a contagious block?

We would need to request dynamic memory therefore we would need to include the following declaration in our program.

can1 = (struct candles *)malloc(sizeof(struct candles));

Data could then be stored in the available memory blocks regardless of continuity.

This brings up the question what does the function malloc do? This function will �ask� the system for a block of memory of the size specified and returns a pointer which is pointing to the first element of the block.  The parameter in the parentheses is the size of the block requested.  It is good programming practice to test for the malloc to return a value if it were to return a null value that would signify that the memory was not available.

In order to get a better grasp on the subject read over the questions below:

QUESTIONS

How is the malloc function defined?
How is the malloc function declared?
What is a heap?
What library file gives us access to the malloc function?
How many types of memory are available?
Are there any additional memory functions?
How is memory given �back� to the system?
Why do want to test for a null value return on the malloc call?

1. How is the malloc function defined?

A function that will allocate a piece of memory on a heap that is x characters in lenth and will be of type character.

What is a heap?

It is a predefined area of memory which can be accessed by the program to store data and variables.

What library file gives us access to the malloc function?

The stdlib.h library file.

How many types of memory are available?

Two � static and dynamic

Are there any additional memory functions?

Yes � Realloc which reallocates the memory block to a bigger or smaller size and Calloc which clears a block a memory and fills it with zeros. Neither of these are widely used.

How is memory given �back� to the system?

With the free statement.

Free(*can1);

Why do want to test for a null value return on the malloc call?

The malloc function will return a NULL when there is no memory space available. We can not proceed with our program if there is no memory available.

References:

http://www.pkirs.utep.edu/cis3355/lecslide.htm

http://www.hamline.edu/personal/wnk/dodrill/c/chap12.html

http://www.nist.gov/dads/HTML/linkedList.html

http://www.inversereality.org/tutorials/c++/linkedlists.html