Introduction to Data Structure

In computer science a data structure is a particular way of storing and organizing data in a computer's memory so that it can be used efficiently.
Data may be organized in many different way, the logical or mathematical model of a particular organization of data is called a data structure.

Primitive data type: These are basic data types that are built into a programming language. Primitive data types are usually faster to access and manipulate than non-primitive data types because they are stored directly in memory.
- These are elementary data structures because they are the most basic and fundamental data types provided by programming languages. They are not constructed from other data types, but instead are the building blocks that are used to create more complex data structures.
- Primitive data structures are atomic because they cannot be divided or broken down into smaller units. For example, an integer data type can hold a single integer value, and a character data type can hold a single character or letter. They are elementary because they are simple and have no internal structure.
Non-primitive data type: These are also known as reference data types, these are more complex and can be composed of multiple values or other data types. They are not built into the programming language, but are defined by the programmer. Examples arrays, structures, etc. Non-primitive data types are stored indirectly and require more complex operations to access and manipulate.

Need of data structure

It gives different level of organization data.
It tells how data can be stored and accessed in its elementary level.
Provide operation on group of data, such as adding an item, looking up highest priority item.
Provide a means to manage huge amount of data efficiently.
Provide fast searching and sorting of data.

Types of Data Structure

Static data structure

A structure whose organizational characteristics are invariant throughout its lifetime.
Such structures are well supported by high-level languages and familiar examples are arrays and records.

Dynamic data structure

A data structure whose organizational characteristics may change during its lifetime.
The adaptability afforded by such structures, e.g. linked lists, is often at the expense of decreased efficiency in accessing elements of the structure.

Linear data structure

A data structure is said to be linear if its elements form any sequence.
There are basicallly two ways of representing such linear structure in memory.
1. One way is to have the linear relationships between the elements represented by means of sequential memory location. These linear structures are called arrays.
2. The other way is to have the linear relationship between the elements represented by means of pointers or links. These linear structures are called linked lists. The common examples of linear data structure are arrays, queues, stacks and linked lists.

Non-linear data structure

This structure is mainly used to represent data containing a hierarchical relationship between elements. E.g. graphs, family trees and table of contents.

Operations on Data Structures

Creation
Insertion
Deletion
Updation
Traversing
Searching
Sorting
Merging

Static memory and Dynamic memory allocation

Dynamic Memory allocation

It can be defined as a procedure in which the size of data structure (like array) is changed during the runtime.
C provides some functions to achieve these tasks.
There are 4 library functions provided by C defined under <stdlib.h> header file to facilitate dynamic memory allocation in C programming. They are:
1. malloc()
2. calloc()
3. realloc()
4. free()

Let's quickly brush up the concept of pointers:

Pointer is a variable that stores address of another variable.
Note: The size of pointer is fixed in a particular system. The size of pointer doesn't depends upon which datatype address it is storing.
why we have to write data type before a pointer, for example- int *ptr?
- The reason for this is that pointers in C and C++ are strongly typed, which means that the data type of the variable being pointed to must match the data type of the pointer itself. This is because pointers are used to store memory addresses, and the size of a memory address can vary depending on the data type of the variable being pointed to.

malloc( ) method

The "malloc" or "memory allocation" method in C is used to dynamically allocate a single large block of memory with the specified size.
It returns a pointer of type void which can be cast into a pointer of any form.
- The return value is a void pointer to the allocated space. Therefore the void pointer needs to be casted to the appropriate type as per the requirements

Syntax ↓

                       
ptr = (cast-type *) malloc(size of memory)

Example ↓

                       
int *ptr;
ptr = (int *) malloc(100 * sizeof(int));
                        
Since the size of int is 4 bytes, this statement will allocate 400 bytes of memory.
And, the pointer ptr holds the address of the first byte in the allocated memory.

we are using sizeof() because in different architecture data-type value changes

Characteristics of malloc function

This function returns a pointer to the first byte of the allocated memory block. If the allocation fails, it returns NULL.
This function takes a single argument, which is the size of the memory block to be allocated in bytes.
The memory allocated by 'malloc()' is not initialized, which means the contents of the block will be undefined until initialized by the program.
The memory block allocated by 'malloc()' remains allocated until the program explicitly frees it using the 'free()' function, or until the program terminates.
'malloc()' can be used to allocate memory for variables of any data type, including structures and arrays.
'malloc()' initializes memory with garbage values.

calloc( ) method

"calloc" or "contiguous allocation" method in C is used to dynamically allocate the specified number of blocks of memory of the specified type.
It is very much similar to malloc() but has two different points and these are:
1. It initializes each block with a default value '0'.
2. It has two parameters or arguments as compare to malloc()

Syntax ↓

                       
ptr = (cast-type *) calloc(n, element-size);
here, n is the no. of blocks and element-sze is the size of each element.

For example ↓

                       
ptr = (float *) calloc(25, sizeof(float));
This statement allocates contiguous space in memory for 25 elements each with the size of the float.

If space is insufficient, allocation fails and returns a NULL pointer.

realloc( )

"realloc" or "re-allocation" method is C is used to dynamically change the memory allocation of a previously allocated memory.
In other words, if the memory previously allocated with the help of malloc or calloc is insufficient, realloc can be used to dynamically re-allocate memory.
Re-allocation of memory maintains the already present value and new blocks will be initialized with the default garbage value.

Syntax ↓

                       
ptr = realloc(ptr, newSize);
here ptr is reallocated with new size 'newSize'.

free( )

"free" method in C is used to dynamically de-allocate the memory.
The memory allocated using functions malloc() and calloc() is not de-allocated on their own. Hence free() method is used, whenever the dynamic memory allocation takes place. It helps to reduce wastage of memory by freeing it.

programs

                    
#include <stdio.h>
#include <stdlib.h>

int main()
{
    // use of malloc
    int *ptr;
    int n;
    printf("Enter the size of the array you want to create : ");
    scanf("%d", &n);
    ptr = (int *)malloc(n * sizeof(int)); // create dynamic array of 10 size

    // Check if the memory has been successfully allocated by malloc or not
    if (ptr == NULL)
    {
        printf("Memory not allocated.\n");
        exit(0);
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            printf("Enter the value no %d of this : ", i);
            scanf("%d", &ptr[i]);
        }

        for (int i = 0; i < n; i++)
        {
            printf("The value %d of this array is %d\n", i, ptr[i]);
        }
    }
    return 0;
}

               
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int *ptr;
    int n, i;

    printf("Enter the number of elements : ");
    scanf("%d", &n);

    // Dynamically allocate memory using calloc()
    ptr = (int *)calloc(n, sizeof(int));

    // check if the memory has been successfully allocated by calloc or not
    if (ptr == NULL)
    {
        printf("Memory not allocated.\n");
        exit(0);
    }
    else
    {
        printf("Memory successfully allocated using calloc.\n");
        for (i = 0; i < n; i++)
        {
            ptr[i] = i + 1;
        }

        // print the elements of the array
        printf("The elements of the array are: ");
        for (i = 0; i < n; i++)
        {
            printf("%d\t", ptr[i]);
        }
    }
    return 0;
}

                
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int *ptr;
    int n, i, previousSize;

    printf("Enter the number of elements : ");
    scanf("%d", &n);

    // Dynamically allocate memory using calloc()
    ptr = (int *)calloc(n, sizeof(int));

    // check if the memory has been successfully allocated by calloc or not
    if (ptr == NULL)
    {
        printf("Memory not allocated.\n");
        exit(0);
    }
    else
    {
        printf("Memory successfully allocated using calloc.\n");
        for (i = 0; i < n; i++)
        {
            ptr[i] = i + 1;
        }

        // print the elements of the array
        printf("The elements of the array are: ");
        for (i = 0; i < n; i++)
        {
            printf("%d\t", ptr[i]);
        }
        previousSize = n;
        printf("\nEnter the new size of the array : ");
        scanf("%d", &n);

        // Dynamically re-allocate memory using realloc()
        ptr = realloc(ptr, n * sizeof(int));

        printf("Memory successfully re-allocated using realloc\n");

        // initializing new element array with new value
        for (i = previousSize; i < n; i++)
        {
            ptr[i] = i + 1;
        }
        // print the elements of the array
        printf("The elements of the array after using realloc are: ");
        for (i = 0; i < n; i++)
        {
            printf("%d\t", ptr[i]);
        }
    }
    return 0;
}

                
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int *ptr1, *ptr2;
    int n, i;

    printf("Enter the number of elements : ");
    scanf("%d", &n);

    // Dynamically allocate memory using malloc()
    ptr1 = (int *)malloc(sizeof(int));

    // Dynamically allocate memory using calloc()
    ptr2 = (int *)calloc(n, sizeof(int));

    // check if the memory has been successfully allocated by calloc or not
    if (ptr1 == NULL || ptr2 == NULL)
    {
        printf("Memory not allocated.\n");
        exit(0);
    }
    else
    {
        printf("Memory successfully allocated using malloc.\n");
        // free ptr1 memory
        free(ptr1);
        printf("Malloc memory successfully freed.\n");

        printf("Memory successfully allocated using calloc.\n");
        // free ptr2 memory
        free(ptr2);
        printf("Calloc memory successfully freed.\n");
    }
    return 0;
}