Dynamically Allocated Linked List

This tutorial is design to show and give an example of a dynamically allocated linked list.  At the end of this tutorial, you will be able to have a better understanding of how dynamically allocated linked list work.

When the program is written, the programmer may not know how many the amount of data will be needed.  Therefore, we need to be sure that we know how to manage memory in RAM as we construct the program. 

The easiest way to fix the problem of memory allocation is to use dynamic memory allocation.  Dynamic memory allocation helps us to determine the amount of storage allocated and adjust when the program is run.

In this tutorial we will be introducing malloc.  Malloc take one parameter, the size in bytes of the block of memory that you are requesting.  If it succeeds, it returns a pointer to the block of memory. 

Example:

Malloc(sizeof(char))   // this request enough storage for 1 character 

But remember, if there is not enough memory space available, malloc returns a NULL.  So, you must always check that to make sure that you have enough memory.

For example;

 If(c_ptr==(char*) NULL)

{

            printf(“memory fail\n”)

            exit(1);

}

  now let’s take a look at how to construct a dynamically allocated linked list.

  Struct classgrade

            { char  classname[10];      

               char  grade[2];

               struct  classgrade *next; };  //don’t forget our pointer!!!

  So far, we want to look into finding the memory of our class and our grade for each class.  The data may be:

//classname[10] + grade [2]  = 12

We know that we need 12 * 3 = 36 bytes of contiguous storage.  But when we look into RAM, we found

Let’s take a look at the storage of RAM above

Remember that our record required 16 bytes per record.

How do we get that???

Well, by adding classname [10] + grade [2] + pointer 4 = 16

Refer to the storage above we got plenty of room in RAM to store our record.  But this time we will use linked list.

See how organized of the memory space we use!

We just finished learning about how to construct a dynamically allocated linked list.  Hope the tutorial can help you to have a better understanding about the subject.   Good luck.

Questions:

1. what does malloc() function do?

The malloc() function requests memory at compile time and free() returns memory to the heap for use by other programs. 

2. where can malloc() function be found?

This function can be found in stdlib.h library file.

3. why is it important to always check malloc for NULL?

malloc() will return a NULL when there is no memory space available.  We need to make sure that the program doesn’t attempt to put data into NULL.      

References:

1. http://menbers.aol.com/mcccompsci/cpp-ch10.htm
2. http://www.sputnix.com/LearnC/DynamicMemory.htm
3. http://www.pkirs.utep.edu/cis3355/lecslide.htm