Data
Structures Using ‘C’
Unit :-4
DYNAMIC MEMORY ALLOCATION and LINKED LIST
Memory
Allocation:
Memory
allocation refers to the process of reserving memory space within a computer's
memory
to store
data elements and the structure itself. This process is crucial for how a data
structure can
hold and
manage data effectively.
There are
two main types of memory allocation: static and dynamic.
Static
Memory Allocation:
This type of
allocation involves allocating memory space at compile time, meaning the
size of the
data structure is fixed before the program runs. Arrays, for example, often use
static
allocation, where the size is declared and cannot be changed during runtime.
Dynamic
Memory Allocation:
In contrast,
dynamic allocation allows the program to allocate and deallocate memory
space during
runtime, as needed. Linked lists, for example, often use dynamic allocation,
where new
nodes can be added or removed as the list grows or shrinks.
DIFFERENCES
BETWEEN STATIC MEMORY ALLOCATION AND DYNAMIC
MEMORY
ALLOCATION
STATICMEMORYALLOCATION
DYNAMICMEMORYALLOCATION
1. In the
static variables get allocated permanently
till the
program executes.
2. It
executes at compile time.
3. It is
done before program execution.
4. It is
less efficient.
5. There is
no memory reusability.
6. Once the
memory is allocated the memory
cannot be
changed.
7. We cannot
reuse the unused memory.
8. It is
faster than dynamic memory.
1. In the
variables get allocated only if your
program unit
gets active.
2. It
executes at run time.
3. It is
done during program execution.
4. It is
more efficient.
5. There is
memory reusability and memory can be
freed when
elements are not assigned.
6. When
memory is allocated the memory size can
be changed.
7. This
allows the reusing the memory and release
the memory
which is not used
8. It is
slower than static memory
Dynamic
Memory Allocation and De-Allocation Functions
Dynamic
memory allocation functions are classified into 4 types, they are
1. Malloc ()
2. Calloc ()
Memory Allocation Functions
3. Realloc
()
4. Free ()
De-Allocation Function
Malloc ()
It stands
for memory allocation.
The
function Malloc reserves a single block of memory that contains the number of
bits
Specified in
its parameter.
The
general syntax of Malloc is-
Ptr=(datatype*)
malloc (byte size);
Where, size
is the number of bytes to allocate.
This
function returns a void pointer to the allocated memory that needs to be
converted to the
pointer of
required type to be usable. If allocation fails, it returns NULL pointer.
Program To
Show Usage of Malloc Function.
#include<stdio.h>
#include<conio.h>
void main ()
{
int
n,i,*ptr,sum=0;
clrscr();
printf(“Enter
number of elements:”);
Scanf(“%d”,&n);
ptr=(int*)malloc(n*size
of (int));
if(ptr==null)
{
printf(“\n
Error ! Memory not allocated”);
exit(0);
}
printf(“\n
Total memory allocated for %d elements are %d bytes”,n,n*sizeof(int));
printf(“Enter
elements of array:\n”);
for(i=0;i<n;++i)
{
scanf(“%d”,ptr+i);
sum+=*(ptr+i);
}
printf(“sum=%d”,sum);
free(ptr);
getch();
}
Output:
Enter number
of elements: 5
Total memory
allocation for 5 elements are 10 bytes
Enter
elements of array:
10 20 30 40
50
Sum = 15
Calloc ()
It stands
for continuous memory allocation.
It is
primarily used to allocate the memory for arrays.
The only
difference between malloc and calloc is that malloc allocates single
Block of
memory whereas calloc allocates multiple blocks of memory.
The
general syntax of calloc is:
Ptr = calloc
(element-count, element-size);
where n is
the number of elements and size is the size of each element in bytes.
This
function also returns a void pointer to the allocated memory that is converted
to the
pointer of
required type to be usable. If allocation fails, it returns NULL pointer.
Program to
show usage of calloc function.
#include<stdio.h>
#include<conio.h>
void main ()
{
int
n,i,*ptr,sum=0;
clrscr();
printf(“Enter
number of elements:”);
scanf(“%d”,&n);
ptr=(int*)calloc(n,size
of (int));
if(ptr==null)
{
printf(“Error
! memory not allocated”);
exit(0);
}
printf(“\n
Total memory allocated for %d elements is %d bytes”,n,n*size of(int));
printf(“\n
Initial memory contents:”);
for(i=0
;i<n;i++)
{
scanf(“%d”,ptr*i);
Sum+=*(ptr+i);
}
printf(“sum=%d”,sum);
free();
getch();
}
Output:
Enter number of elements:4
Total memory
allocated for 4 elements is 8 bytes.
Initial
memory contents:0 0 0 0
Enter
elements of array:10 20 30 40
Sum=10
Realloc ():
If a
previously allocated memory insufficient or more than sufficient then this
memory
size can be
changed using this function.
The
general syntax is:
ptr=realloc(ptr,new
size);
where, ptr
is the pointer to the previously allocated memory block and new_size is the
reallocated
size that the memory block should have in bytes.
This
function returns a pointer to the newly allocated memory, or NULL if the
reallocation
fails. If it
fails, the original memory block remains unchanged.
Program to
show usage of relloc function.
#include<stdio.h>
#include<conio.h>
void main()
{
int*ptr,i,n1,n2;
clrscr();
printf(“Enter
size of array:”);
scanf(“%d”,&n1);
ptr=(int*)malloc(n1*size
of(int));
printf(“previously
allocated memory address:”);
for(i=0;i<n1;i++)
printf(“%u\t”,ptr+i);
printf(“\n
enter new size of array:”);
scanf(“%d”,&n2);
printf(“Newly
allocated memory address:”);
ptr=realloc(ptr,n2);
for(i=0;i<n2;i++)
printf(“%u\t”,ptr+i);
getch();
}
Output:
Enter size
of array:3
Previously
allocated memory address:1958 1960 1962
Enter new
size of array:4
Newly
allocated memory address:1958 1960 1962 1964
Free ():
It stands
for releasing the memory.
It is a
memory De-allocation function.
When the
memory allocations are allocated by malloc,calloc and realloc are no longer
required
then they are freed using pre-defined function free.
The
general syntax of free function is:
free(ptr);
Where, ptr
is the pointer to the allocated memory.
After
freeing a memory block, the pointer becomes invalid, and it is no longer
pointing to a
valid memory
location.
LINKED LIST
Linked list:
linked list is a linear collection of data elements in which these data
elements are
called
nodes.
It is a
linear data structure.
It
contains collection of data elements which are connected together viva links.
Data.
address (or)link.
Data field
stores actual data &link field contains address of the next node.
Linked
list is a data structure which consists of group of nodes that forms a
sequence.
It is a
popular data structure with a wide range of real-world applications. Unlike
Arrays,
Linked List elements are not stored at a contiguous location.
In the
linked list there is a head pointer, which points to the first element of the
linked
list, and if
the list is empty then it simply points to null or nothing.
Basic
Terminologies of Linked List
Head: The
Head of a linked list is a pointer to the first node or reference of the first
node
of linked
list. This pointer marks the beginning of the linked list.
Node:
Linked List consists of a series of nodes where each node has two
parts: data
and next pointer.
Data: Data
is the part of node which stores the information in the linked list.
Next
pointer: Next pointer is the part of the node which points to the next node of
the
linked list.
Advantages
of Linked list: -
Dynamic
Data structure: The size of memory can be allocated or de-allocated at run time
based on the
operation insertion or deletion.
Ease of
Insertion/Deletion: The insertion and deletion of elements are simpler than
arrays
since no
elements need to be shifted after insertion and deletion, Just the address
needed to
be updated.
Efficient
Memory Utilization: As we know Linked List is a dynamic data structure the
size
increases or decreases as per the requirement so this avoids the wastage of
memory.
Implementation: Various advanced data structures can be implemented using a
linked list
like a
stack, queue, graph, hash maps, etc.
Disadvantage
of linked list: -
Extra
memory space is required for pointer.
Linked list
can be represented as:
Difference
between arrays and linked list: -
There are
two ways to Represent the memory they are: -
1. Static
representation using array.
2. Dynamic
representation of linked list
1. Static
representation using arrays: -
Static
representation of a single linked list maintains two arrays those are one array
for
information
and another array for link (or) pointer.
These two
arrays to be equal size and parallel to each other.
The memory
size of these two arrays should be sufficient to store the entered linked list.
2. Dynamic
representation of linked list: -
The
process of allocating memory at run time is known as Dynamic Memory allocation.
In dynamic
representation of Linked list, a node is created dynamically whenever it is
required.
Any number
of nodes can be created depending upon the requirement.
In order
to create a linked list a structure is to declared that defines all the list
entries.
The
following structure is capable of holding the data + the address of the memory
space
holding the
next structure in the list.
Example:
Struct node
{
Int info;
Struct node
* list;
};
Here link
is the pointer that find to the next node of the same structure time.
Types of
linked list: -
Depending on
the requirement the linked list classified in to 4 types.
1. Singly
linked list.
2. Doubly
linked list.
3. Circular
linked list.
4. Header
linked list.
Singly
linked list: -
Singly
linked list (or) one-way list is a linear collection of data elements called
nodes
where each
node is divided in two parts INFO field &LINK field.
The link
field of each node will point to the next node and the link field of the last
node
always
points to the null.
2. Doubly
linked list: -
To
increase the performance and efficiency of algorithm in two-way list called
doubly
linked list
is introduced.
Doubly
linked list can be used where we can move in either forward(or)backward
direction
through a linear way.
Forward
direction means traversing from left to right.
Backward
direction means traversing from right to left.
Doubly
linked list defined as a collection of nodes where each node is divided in to
two
fields.
1. Backward
field / Pointer to previous node.
2.
Information field
3. Forward
field / Pointer to next node.
In doubly
linked list the backward field of the first node always contains null
indicating
that it is
the first node in the linked list and the forward field of last node also
contains
null
indicating that it is the last node in the linked list.
Advantages
of doubly linked list: -
The doubly
linked list can be traversed in forward (or)backward direction.
If any
particular node address is known one can have both successor node address and
predecessor
that makes inserting and deleting much easier.
The doubly
linked list is used to represent the trees efficiently.
This
simplifies list management.
Disadvantages
of doubly linked list:
Extra
memory is required to store the back pointer.
3. Circular
linked list: - Circular linked list is defined as linear connection of data
elements
called
nodes. Where each node is divided in to two parts (data & link (or)address)
INFO field &
link field
.and the link field of each node will point to the next node and the link field
of the last
node will
point to the first node.
Advantages
of circular linked list: -
The
circular linked list traversed to any node to any node.
All the
nodes link address will have valid address instead of null pointer.
A node can
be inserted (or) deleted from any position of the linked list.
One can
start at any node in the list and traverse the whole list.
4. Header
linked list: -
Header
linked list is a linked list which always INFO contains a special node called
the
header node
at the beginning of the list.
INFO field
of such a header node generally contain the global information of the entire
list.
The header
linked list is widely classified in to two types .
1. Grounded
header linked list.
2. Circular
header linked list.
1. Grounded
header linked list: -
It is also
referred as singly linked list.
In this
the last node link field contains null pointer.
There are
3 nodes because header node is not counted.
2. Circular
header linked list: -
A linked
list in which last node pointer to the header node is called circular header
linked
list.
Operations
on singly linked list: -
1.
Traversing/display
2.
Searching.
3.
Insertion.
4. Deletion.
Traversing
/display:
The
process of going through all the nodes of the linked list from one end to
another end
is called as
traversing.
The
display operation is a good example for traversing.
In display
operation we require to display the contents of every node from start to end.
Algorithm in
traversing linked list:
Step 1: [if
linked list is empty?]
if
(start=null)
Display
(“linked list is empty”)
exit ()
Step 2:
[assign start value to CURRPTR] (current pointer)
CURRPTR =
start
Step 3:
Repeat while (CURRPTR! = NULL)
Process INFO
[CURRPTR]
CURRPTR=LINK[CURRPTR]/*moving
CURRPTR from one node to the next node*/
Step 4: exit
Displaying a
linked list: If you want to display a linked list in certain order. We can
process
each node
exactly once.
Algorithm
for displaying a linked list: -
Step 1:
[check “LIST EMPTY”]
if (start==
NULL)
Write (“LIST
EMPTY”)
return;
Step 2: set
CURRPTR = start
[store the
address of first node in another pointer CURRPTR]
Step 3:
repeat step 4 and step 5 while (CURRPTR! =NULL)
Step 4:
[display the items one – by – one from the first node until CURRPTR becomes
NULL]
Display
[INFO [CURRPTR]);
Step 5:
[after the display of this element, CURRPTR should point to the next node]
CURRPTR =
LINK[CURRPTR]
Step 6: exit
Searching in
a linked list:
Searching
operation refers to a particular element in the list.
For
searching we have to compare each element to the list with the required element
of
the list
until the element is found.
If search
is successful, it returns the location of that node otherwise it returns null.
Algorithm to
search an element in a linked list: -
Step 1: set
CURRPTR= start, LOC=NULL
Step 2:
repeat step 3 while CURRPTR! = NULL
Step 3: if
(ITEM=INFO[CURRPTR])
Then
LOC=CURRPTR and display “search successful”
Exit
else
CURRPTR=LINK[CURRPTR]
[so CURRPTR,
now points to the next node]
Step 4: if
LOC=NULL
Display
“search successful”
Step 5: exit
Insertion
operations in a linked list:
A linked
list can be implemented by dynamic memory allocation where the number of
nodes in a
list may vary after the elements are inserted (or) deleted.
In order
to insert a node in a linked list. first empty node is to be created then the
information
is to be stored in that new node, at last it is placed in the specified
position of
the linked
list.
The
insertion of new node depends on the position of the existing linked list, the
different
insertion that can be performed are as follows
Case 1:
inserting node at the beginning of the linked list.
Case 2:
inserting node at the end of the linked list.
Case 3:
inserting node at the certain position of the linked list.
Case 1:
Insertion at the beginning
Suppose
the linked list has 3 nodes and require other node called new node to be
inserted
in to the
linked list at the beginning.
To insert
a new node at the front, we create a new node and point its next reference to
the current
head of the linked list. Then, we update the head to be this new node. This
operation is
efficient because it only requires adjusting a few pointers.
Make the
first node of Linked List linked to the new node
Remove the
head from the original first node of Linked List
Make the
new node as the Head of the Linked List.
Algorithm to
insert a node at the beginning of the linked list:
Step 1:
[create a new node that is to be inserted]
NEWNODE=get
node ();
Step 2:
[enter the item in to the INFO field of the NEWNODE]
INFO [NEW
NODE] =ITEM;
Step 3:
[assign the “start value” to the LINK part of the inserted node (NEW NODE)]
LINK [NEW
NODE] =start;
[it makes a
link from ‘NEW NODE’ to the previous first node]
[so, now
both ‘start’ and ‘NEW NODE’ are pointing to the original first node of the
linked list]
Step 4:
[reassign ‘start’ with ‘NEW NODE’ so that a link is developed between start and
new
node]
Start=NEWNODE
Step 5: exit
Case 2:
Inserting node at the end of the linked list
In some
situations, we may require to insert an item at the end of the linked list.in
such
situation
first we should traverse the list.
To insert
one more node at the end first we should find the address of the last node.
To get the
last node address starting to ending initially CURRPTR=start
Inserting
at the end involves traversing the entire list until we reach the last node. We
then set the
last node's next reference to point to the new node, making the new
node the
last element in the list.
Following is
the approach to add a new node at the end of the linked list:
Create a
new node and set its next pointer as NULL since it will be the last node.
Store the
head reference in a temporary variable
If the
Linked List is empty, make the new node as the head and return
Else
traverse till the last node
Change the
next pointer of the last node to point to the new node.
Algorithm to
insert a node at the end of a linked list
Step 1: [if
list is empty]
if
(start=null)
Insert at
the beginning
Exit ()
Step 2:
CURRPTR=start
Step 3:
[traverse the list to obtain last node address]
While (LINK
[CURRPTR]! =NULL)
CURRPTR=LINK[CURRPTR]
End while
Step 4:
[create a NEWNODE and enter the accepted ITEM in to its INFO fields]
NEWNODE=get
node ();
NEWNODE
→INF0 = ITEM;
Step 5:
[make list between last node [CURRPTR] and NEWNODE]
LINK[CURRPTR]=NEWNODE
LINK[NEWNODE]=NULL
Step 6: EXIT
Case3:
Insert a node at certain position in a linked list
To insert
an item at any certain position first we have to traverse the linked list up to
the
position
after which we have to insert the element and their by we can insert the node
by
required
position.
If the
original linked list before the insertion is
Example:
If we want to insert the node at 3rd position the linked list is to be
traversed up to
the second
node and the new node after insertion will be in between second and third nodes
Following is
the approach to add a new node at the Specific of the linked list:
Initialize
a variable , say curr points to head and allocate the memory to the new
node with
the given data.
Traverse
the Linked list using curr pointer upto position-1 nodes.
If curr's
next is not null , then next pointer of the new node points to
the next of
curr node.
The next
pointer of current node points to the new node.
return the
head of linked list.
Algorithm to
insert a node at certain position in linked list:
Step 1: [set
CURRPTR to start]
CURRPTR=start
Step 2: [if
the item is to be inserted at 1st position]
If(pos==1)
Algorithm
for inserting at the beginning (case 1)
else goto
step 3.
Step 3: [if
the item is to be inserted at same position other, then 1st position]
for (i=0;
i<pos-2; i++)
{
CURRPTR=LINK[CURRPTR]//traversing
the list
}//end for
Step 4:
[create a NEWNODE]
NEWNODE= get
node ();
Step 5:
[enter the elements INFO field of NEWNODE]
INFO [NEW
NODE] =item;
Step 6:
[make a connection between the NEWNODE and the next node after CURRPTR]
LINK [NEW
NODE] =LINK[CURRPTR]
Step 7:
[make a link between CURRPTR and NEWNODE]
LINK[CURRPTR]=NEWNODE
Step 8:
EXIT.
Deletion
operation on linked list:
A linked
is implemented by dynamic memory allocation method where the number of
nodes in
list may vary after the elements are deleted.
But after
deleting node the memory allocated by the node is free
The cases
performed in deletion operation are:
1. Deleting
a node at the beginning of linked list
2. Deleting
a node at end of linked list
3. Deleting
a node at certain position of linked list
Case 1:
Deleting a node at beginning of linked list
To remove
the first node of a linked list, store the current head in a temporary variable
(temp), move
the head pointer to the next node, delete the temporary head node and finally ,
return the
new head of the linked list.
Algorithm to
delete an element from linked list
Step1: [
check whether the linked list is empty]
if
(start=NULL)
write
“Linked list is empty”
else go to
step 2
Step2: [set
CURRPTR to start]
CURRPTR=start;
Step3:
[Assign the link field node to “start” to delete the original first node]
Start=LINK[Start];
Step4: [Free
the deleted item]
free
(CURRPTR);
Step5: EXIT.
Case2:
Deleting a node at Specific of the linked list
Deletion
at a specified position in a linked list involves removing a node from a
specific
index/position,
which can be the first, middle, or last node.
To perform
the deletion, If the position is 1, we update the head to point to the next
node and
delete the current head. For other positions, we traverse the list to reach the
node just
before the specified position. If the target node exists, we adjust the next of
this
previous node to point to next of next nodes, which will result in skipping the
target node.
Step-by-step
approach:
If list is
empty (head == NULL), returns the head.
If the
position to delete is 1 (the head node):
o Update
head = temp->next
Traverse
the list until reaching the desired position:
o Initialize
prev to keep track of the previous node.
o Move temp
through the list until the position is reached.
Check for
Valid Position:
o If temp
becomes NULL, it means the position exceeds the number of nodes in
the list.
Print a message and return the head.
If the
node to delete is found:
o Set
prev->next to temp->next, effectively skipping over the node to be
deleted.
Algorithm to
delete a node at specific position of the linked list
Step1:
[check for the position whether the deletion is at first position]
if(pos==1)
Algorithm
for deleting from beginning(case1)
else go to
step2
Step2: [set
CURRPTR to start]
CURRPTR=START
Step3: [set
PREVPTR to NULL]
PREVPTR=NULL
Step4: [if
the item to be deleted is not at first position]
for(i=1;i<pos;i++)
{
PREVPTR=CURRPTR[Set
PREVPTR to CURRPTR]
CURRPTR=CURRPTR
LIST[Set CURRPTR to its next node]
}*/end for
Step5: [Link
of PREVPTR is assigned with LINK of CURRPTR i.e., make a link between
The PREVPTR
and the next node of CURRPTR]
PREVPTR
LINK=CURRPTR LINK
Step6: EXIT
Case3:
Deleting a node at end of the linked list
To perform
the deletion operation at the end of linked list, we need to traverse the list
to find
the second
last node, then set its next pointer to null. If the list is empty then there
is no node
to delete or
has only one node then point head to null.
Step-by-step
approach:
Check if
list is empty then return NULL.
If the
list has only one node then delete it and return NULL.
Traverse
the list to find the second last node.
Set the
next pointer of second last node to NULL.
Algorithm
for deleting a node at the end of linked list
Step1:
[Check whether the list is empty]
if(start==NULL)
write
“LINKED LIST IS EMPTY”
else go to
step2
Step2:
[Check if the linked list has only one element]
if
(LINK[START]==NULL) then
Start=NULL
else go to
step 4
Step3: [free
the deleted node]
free
[START];
Step4:
[Assign NULL to another pointer PREVPTR]
CURRPTR=START;
Step5:
[Assign NULL to another pointer PREVPTR]
PREVPTR=NULL
Step6:
[Traverse the list until the CURRPTR points to last node and PREPTR points to
last
before node]
while
(LINK[CURRPTR]! =NULL)
PREVPTR=CURRPTR
CURRPTR=CURRPTR
LINK
Step7: [To
make the link part of the last node, after deletion ,to NULL]
PREVPTR
LINK=NULL;
Step8: EXIT.
GARBAGE
COLLECTION: -
Garbage
collection is automatic management of dynamically allocated storage which
reclaims
unused heap
blocks for later use of program.
(or)
Garbage
collection in linked lists, a common data structure, refers to the automatic
reclaiming of
memory
occupied by nodes that are no longer being used by the program
Automatic
Memory Management:
GC takes the
responsibility of managing memory away from the programmer, making it easier
to develop
applications.
Reclaiming
Memory:
GC
identifies memory blocks that are no longer reachable by the program and
releases them
back to the
system.
Prevents
Memory Leaks:
Without GC,
programs could accumulate unused memory, leading to slow performance and
eventually
crashing.
1.
Reachability: GC determines which objects are still being used (reachable) by
tracing references
from the
program's roots (like stack variables).
2.
Unreachable Objects: Objects that are no longer reachable are marked as
garbage.
3. Memory
Reclamation: The GC then frees up the memory occupied by these garbage objects.
The garbage
collector provides the following benefits:
Frees
developers from having to manually release memory.
Allocates
objects on the managed heap efficiently.
Reclaims
objects that are no longer being used, clears their memory, and keeps the
memory
available for future allocations. Managed objects automatically get clean
content
to start
with, so their constructors don't have to initialize every data field.
Provides
memory safety by making sure that an object can't use for itself the memory
allocated
for another object.
Steps to
process:-
1. GC will
sequentially visit all nodes in memory and mark all nodes which are
being used
in program.
2. It will
collect all unmarked nodes and place them in free storage area.