Limitations of the Array Implementation

Under the array implementation, a fixed set of nodes represented by an array is established at the start of execution. A pointer to a node is represented by the relative position of the node within the array. The disadvantage of that approach is twofold. First, the number of nodes that are needed often cannot be predicted when a program is written. Usually, the data with which the program is executed determines the number of nodes necessary. Thus no matter how many elements the array of nodes contains, it is always possible that the program will be executed with input that requires a larger number.

The second disadvantage of the array approach is that whatever number of nodes are declared must remain allocated to the program throughout its execution. For example, if 500 nodes of a given type are declared, the amount of storage required for those 500 nodes is reserved for that purpose. If the program actually uses only 100 or even 10 nodes in its execution the additional nodes are still reserved and their storage cannot be used for any other purpose.

The solution to this problem is to allow nodes that are dynamic, rather than static. That is, when a node is needed, storage is reserved for it, and when it is no longer needed, the storage is released. Thus the storage for nodes that are no longer in use is available for another purpose. Also, no predefined limit on the number of nodes is established. As long as sufficient storage is available to the job as a whole, part of that storage can be reserved for use as a node.

Dynamic nodes use notion of pointers intensively. Pointers allow us to build and manipulate linked lists of various types. The concept of a pointer introduces the possibility of assembling a collection of building blocks, called nodes, into flexible structures. By altering the values of pointers, nodes can be attached, detached, and reassembled in patterns that grow and shrink as execution of a program progresses.

Linked Lists Implementation Using Dynamic Variables

There are two limitations or disadvantages when array structures are implemented with linked lists. First the number of nodes that are needed cannot be predicted when a program is written. The second disadvantage is that whatever number of nodes are declared must remain allocated to the program throughout its execution. The program actually use only a few of them in its execution, the additional nodes are still reserved and their storage cannot be used for any other purpose.

Using dynamic nodes rather than static can circumvent these problems. That is when a node is needed, storage is reserved for it, and when it is no longer needed, the storage is released.

Before using dynamic variables to implement linked list, let us understand how storage can be allocated and freed dynamically and how it is accessed in C.

1) Allocating and Freeing Dynamic Variables

In C a pointer variable to an integer can be created by the declaration

int *p;

Once a variable p has been declared as a pointer to a specific type of object, it must be possible to dynamically create an object of that specific type and assign its address to p.

This may be done in C by calling the standard library function malloc(size): malloc dynamically allocates a portion of memory of size size and returns a pointer to an item of specified type. Consider the declarations

int *p;

float *pr;

The statements

p = (int *) malloc(sizeof (int));

pr = (float *) malloc(sizeof (float));

dynamically create the integer variable *p and the float variable *pr. These variables are called dynamic variables. In executing these statements, the operator sizeof returns the size, in bytes, of its operand. This is used to maintain machine independence. malloc can then create an object of that size. Thus malloc(sizeof(int)) allocate storage for an integer, whereas malloc(sizeof(float)) allocate storage for a floating-point number. malloc also returns a pointer to the storage it allocates. This pointer is to the first byte (for example, integer) of that storage and is of type int *. To coerce this pointer so that it points to an integer or real, we use the cast operator (int *) or (float *).