Introduction to Pointers, Structures and Linked-Lists Part 4
Introduction to Dynamic Memory Allocation
by Chris Bennett aka Dwarfsoft

Introduction

Dynamic Memory Allocation is the method in which you can select a block of memory during the run-time of your program, and use this block of memory for storing more information. This is very useful when using Linked Lists in that you can increase the size of your list without creating new variables. Usually, with your dynamic list, you have a specific function that is dedicated to allocating the memory and adding the block to your list and one for freeing your memory and removing that block from the list.

Dynamic Memory Allocation

OK, so I mentioned allocation and deallocation. How do we go about this? Well, there is a standard function that is available from the library by including <malloc.h> or <stdlib.h> by the name of 'malloc ()' and another that is the reverse of malloc, called 'free ()'. So how do these functions work? The malloc function has the following structure:

void *malloc(size_t size);

This means, that when you use malloc, you call it with the parameter for the size of the memory that you want to allocate, and the function returns a pointer to the memory block. A 'void *' (void pointer) is a special pointer. It has no defined type, and every defined type. You can cast this pointer to be any pointer you choose it to be. If I wanted to allocate a string of 20 characters dynamically, then the following code would suffice

char *Buffer; // Pointer to our dynamic buffer
Buffer = (char *)malloc(20);

The '(char *)' part in the code is the 'casting' of the void pointer to be of type 'char *'. Type casting is very useful and in this case is very important. Without typecasting the pointer to the allocated block, the program is likely to return errors. In the event that the memory allocation fails, the pointer that is returned is a NULL. The other thing that we need to have a look at in detail is the size of memory to be allocated.

When it comes to allocating memory for structures and types, we need to be careful to specify the right size for what we want. If I wanted to allocate enough room for an array of 20 integers (long integers) and I did the following then I would end up with unexpected errors

long *LArray;
LArray = (long *)malloc(20);

This would allocate enough room for 5 long integers. This is because size is measured in bytes, and a long integer is 4 bytes long. But what about when it comes to allocating for large structures? Do we have to add up all of the elements to figure out how big it is? The answer is no, because we can use a keyword that was created for this specific reason. The sizeof keyword evaluates the size of your structure, and by doing so you can allocate the correct memory for a new dynamic instance of that structure. Here is how we can make the above code correct for what we specified for it

long *LArray;
LArray = (long *)malloc(20*sizeof(long));

Before we actually use this array, we should ALWAYS check to see if the memory block was successfully allocated. That is quite simple, as in the event of failure to allocate the memory, the malloc function returns a NULL, so therefore our pointer should be NULL in such a case. Usually I return from a function in the event of an allocation failure.

if (!LArray)
  return(<some error="" in="" allocation="">);
</some>

Now that we have the simple side of allocating memory, we can look at deallocation. Deallocation is quite a bit easier than what we had to go through for allocation. The one thing that you have to be sure of about freeing memory is that there is an allocated block of memory to free. Fortunately, we can do a memory deallocation in a single line, and with a line that also handles the error case.

if (LArray) free(LArray);

This checks that the pointer actually references something, and if it actually points somewhere then the reference is freed.

If you already have an allocated block of memory then you can also use the realloc () function, which reallocates memory to the size that you wanted using the current block of memory. If we wanted to reallocate the block for the LArray so that we could access 40 long integers, then we would do the following.

LArray = (long *)realloc(LArray, sizeof(long)*40);

You need to get the return value to determine if there was a failure (in which case it returns NULL) or if the memory block was moved during the reallocation.

So now that we can allocate and deallocate memory for simple data types, let us use this knowledge in conjunction with the linked list from the previous section. We will now write a function that allocates memory for a new Address to be added to the list.

int NewAddress(AddressPtr_t Head,
               char Name[30],
               char Address[180],
               char PhoneNo[10])
{
   AddressPtr_t Temp, Cur = Head;
   // Go to the end of the list
   if(Cur)
    while(Cur->Next)
       Cur = Cur->Next;

   // Allocate a new block of
   // memory for this address
   Temp = (AddressPtr_t)malloc(sizeof(Address_t));

   // ensure that the allocation passed
   if (!Temp) return (FAILURE);

   // Add the block to the end of the list
   Temp->Next = NULL;
   Cur->Next = Temp;

   // Update the values of the new block
   strcpy(Temp->Name, Name);
   strcpy(Temp->Address, Address);
   strcpy(Temp->PhoneNo, PhoneNo);
   return (SUCCESS);
}

Firstly, the return values of 'FAILURE' and 'SUCCESS' are just macros defined in a way similar to SUCCESS being 0 and failure being 1, or however you want your errors handled through return values. I think that the function is fairly self-explanatory. There still remains one error though. It will not show up unless there was no original list to begin with. If the list was empty, then we need to modify it to avoid getting assertion errors.

int NewAddress(AddressPtr_t Head,
               char Name[30],
               char Address[180],
               char PhoneNo[10])
{
  AddressPtr_t Temp, Cur = Head;

  // Go to the end of the list
  if(Cur)
    while(Cur->Next)
      Cur = Cur->Next;

  // Allocate a new block of memory 
  // for this address
  Temp = (AddressPtr_t)malloc(sizeof(Address_t));

  // ensure that the allocation passed
  if (!Temp) return (FAILURE);

  // Put a plug on the end of the list
  Temp->Next = NULL;

  if (!Cur)
  {
    // If this is the first element, 
    // then avoid assertion
    Cur = Temp;
  }
  else
  {
    // Add to the end of the list
    Cur->Next = Temp;
  }

  // Update the values of the new block
  strcpy(Temp->Name, Name);
  strcpy(Temp->Address, Address);
  strcpy(Temp->PhoneNo, PhoneNo);
  return (SUCCESS);
}

Do you understand what I did just there? Basically, if there was no elements in the list to start with, then Cur was pointing to NULL. If I tried to add to the end of the list by using 'Cur->Next' then I would be causing an assertion. There is no way to point to a NULL->Next, so we need to include a way of avoiding this.

We also need to include a CleanUp routine for when we have finished with our program, so as not to leave memory allocated where the system can't access it. For this, we can use the simple following function

int CleanUp (AddressPtr_t Head)
{
  AddressPtr_t Cur = Head;
  while (Cur)
  {
    Head = Cur;
    Cur = Cur->Next;
    free(Head);
  }
  return(SUCCESS);
}

Conclusion

Well, there you have it, a simple introduction to Dynamic Memory allocation for use in linked lists. Next I will be talking about specific algorithms for use in linked list systems in the region of Sorts, Searches and Saves.

One quick note before I go, though. In the two functions listed above, there is a parameter 'AddressPtr_t Head'. This is the start of the list. Seeing as we are using a single linked list, there needs to be a pointer to the beginning of the list so that each function can start at the beginning of the list and work to the end.

Cheers, Chris (aka. Dwarfsoft)

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/30/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General