Contents  Introduction  Getting Started  The Linked List  Node Design  Node Allocation  Node Insertion  - Unsorted  Linked List  Traversal  Searching  Node Deletion  End of File  Source code  Printable version  Adobe PDF version     The Series  Linked Lists

Getting Started

Before we can begin discussing any dynamic data structure, we need to verify that you have a solid background on basic pointer operations.

A Quick Explanation

Dynamic memory is allocated from an area of memory known as the heap - a finite supply of memory that can be accessed by the programmer. It is possible to deplete all available memory from the stack or heap, since both are of some definite size that is machine-dependent. A program uses stack memory when a function is called, and this memory is released when the function exits. Allocation and deallocation of stack memory is therefore automatic. This is, however, not the case for heap memory, and the programmer must carefully manage the allocation and deallocation of heap memory.

You could write a set of functions that can help you keep track of how much heap memory you have allocated and how much is being used in the program, but that is beyond the scope of this article and would be a good topic for another article. Such a system could be used in resource management.

Allocating Memory

To use the memory allocation functions, <STDLIB.H> must be included. Requesting memory from the heap is accomplished through the malloc() function, which is defined by this prototype:

void *malloc(size_t size);

The malloc() function returns a generic pointer to a chunk of memory containing size bytes. Remember that you must typecast the generic pointer returned by malloc() to the type of the pointer variable that is being allocated. If the heap is full, and no memory is available for allocation, malloc() returns NULL.

Other functions include calloc() (also used for memory allocation of an array) and realloc() (used to increase or decrease the size of a chunk of memory previously allocated). For our purposes, we will use malloc() and free(), which frees the memory that has been allocated for the pointer that is passed as free()'s parameter.

Using Pointers

Now let's get into some real implementation. Pointers are declared and dereferenced using an asterisk; the variable itself, without the asterisk, refers to the actual address of the first byte of the allocated memory. Remember, pointers contain as their value an address to another variable. The dereferenced pointer actually points to the value of a variable held in memory at the address indicated by the pointer. The & character (the address of operator) is used to determine the address of a variable.

Consider this fragment of code:

int i, *ptr1, *ptr2;  // integer and 2 pointers to integers
i = 11;               // get space for one integer and assign a value
ptr1 = (int *)malloc(sizeof(int)); // note the typecast to integer
*ptr1 = 43;           // Use already allocated space
ptr2 = &i;
printf("i, *ptr1, and *ptr2 = %d, %d, %d\n", i, *ptr1, *ptr2);

This code outputs:

i, *ptr1, and *ptr2 = 11, 43, 11

Let's run through the code very quickly. The first line declares one integer variable, and two pointers to integers. The second line assigns the value of 11 to integer variable i. Line three allocates memory for integer pointer ptr1. The fourth line assigns the value of 43 to the memory location that has been allocated by ptr1. Line five then sets the integer pointer ptr2's address to the memory location occupied by integer variable i. The last line then prints out the values of integer variable i, and then the values being held in the memory locations pointed to by ptr1 and ptr2.

If you have trouble understanding that, be sure to read over it several times, or look through a C/C++ book or tutorial on pointers. You need to have a solid understanding of pointers before moving on from this point in the series.

Next : The Linked List