--> Sayadasite

Multiple Ads

Search

Menu Bar

DYNAMIC MEMORY ALLOCATION and LINKED LIST

 

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.