Dynamic Data Structure(Link list)

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 aarray
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-
---------- ----------