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-
|
---------- ----------
|
Stack
|
A stack is a data
structure that resembles a stack of trays in a spring loaded
bin.
|
A tray will be added to the bin on
top of the stack. When you add a tray, the previous one on top will go down
by one position.
|
You can add trays till the first
trays reach the bottom of the stack. Similarly, a tray can be
removed only from the top of the stack.
|
In the computer science item is
nothing but a data element or an object.
|
Therefore a stack is
a list in which items are added, deleted or examined at one only one end.
|
The size of the stack is
defined by the user before compilation and hence this is a static data
structure.
|
It adopts LIFO (last in first
out ) methodology for storage and retrieval.
|
Queue
|
Queue is also a list. Here, the data items are
added at one end and removed from the other hand work as first in first out
for storage and retrieval.
|
Queues are used extensively in operating systems to keep
track of user waiting for resources such as CPU, printing etc.
|
It adopts FIFO(first in first
out )methodology for storage and retrieval.
|
Previous Page Next Page
More Topics :
