Data Structures in C programming

Dynamic data structures

This tutorial introduces dynamic data structures with sizes that grow and shrink at execution time.

• Linked lists are collections of data items “lined up in a row”—insertions and deletions are made anywhere in a linked list.
• Stacks are important in compilers and operating systems—insertions and deletions are made only at one end of a stack—its top.
• Queues represent waiting lines; insertions are made only at the back (also referred to as the tail) of a queue and deletions are made only from the front (also referred to as the head) of a queue.
• Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representing file system directories and compiling expressions into machine language.

 Self-Referential Structures

Recall that a self-referential structure contains a pointer member that points to a structure of the same structure type.

    struct node {            
    int data;   
    struct node *nextPtr;
    }; // end struct node

The definition above defines a type, struct node. A structure of type struct node has two members—integer member data and pointer member nextPtr.

Member nextPtr points to a structure of type struct node—a structure of the same type as the one being declared here, hence the term “self-referential structure.”

Member nextPtr is referred to as a link—i.e., it can be used to “tie” a structure of type struct node to another structure of the same type.

Dynamic Memory Allocation

Creating and maintaining dynamic data structures requires dynamic memory allocation—the ability for a program to obtain more memory space at execution time to hold new nodes, and to release space no longer needed.

Functions malloc and free, and operator sizeof, are essential to dynamic memory allocation.

Function malloc takes as an argument the number of bytes to be allocated and returns a pointer of type void * (pointer to void) to the allocated memory.

As you recall, a void * pointer may be assigned to a variable of any pointer type. Function malloc is normally used with the sizeof operator.

    newPtr = malloc( sizeof( struct node ) );

The statement evaluates sizeof(struct node) to determine the size in bytes of a structure of type struct node, allocates a new area in memory of that number of bytes and stores a pointer to the allocated memory in variable newPtr.

The allocated memory is not initialized. If no memory is available, malloc returns NULL.

Function free deallocates memory—i.e., the memory is returned to the system so that it can be reallocated in the future. To free memory dynamically allocated by the preceding malloc call, use the statement:

free( newPtr );

C also provides functions calloc and realloc for creating and modifying dynamic arrays.