Dynamic Data Structure

Linked list

Before talking about the different mechanism of data structure we will take a short view of DMA (Dynamic Memory Allocation).

DMA: C language requires the number of elements in an array to be specified at compile time.

But it is not practically possible with Array.

In array we allocate the memory first and then start using it.

This may result in failure of a program or wastage of memory space.

The concept of dynamic memory allocation can be used to eradicate this problem.

In this technique , the allocation of memory is done at run time.

C language provides four library function known as memory management function that can be used for allocating and freeing memory during program execution.

These are:

malloc: allocate memory and return a pointer to the first byte of allocated space.

Example:

ptr=(cast.type*)malloc(byte_size);

calloc: allocates the memory spaces, initialize them to zero and returns pointer to first byte.

Example:

ptr=(cast_type*)calloc(n.elem_size);

free: frees previously allocated space.

Example:

free(ptr);

realloc: modifies the size of previously assigned space

Example:

ptr=realloc(ptr,newsize);

We studied about Array there we can observe one major disadvantage of Array is ,if an array is not filled by value, then memory will be locked up.

To overcome this problem we use Linked lists and other data structure mechanism.

Linked List are a way to store data with structures so that the programmer can automatically create a new place to store data whenever necessary.

Specifically, the programmer writes a struct definition that contains variables holding information about something, and then has a pointer to a struct of its type.

Each of these individual struct in the list is known as a node.

Think of it like a train. The programmer always stores the first node of the list. This would be the engine of the train.

The pointer is the connector between cars of the train.

Every time the train add a car, it uses the connectors to add a new car.

This is like a programmer using the keyword new to create a pointer to a new struct

In memory it is often described as looking like this:

---------- ----------

- Data - >- Data ->

---------- - ----------

- Pointer- - - - Pointer-

---------- ----------