2 of 17

Dynamic memory

Variables, constants are basic building blocks which are manipulated in a program to achieve the desired task.
This means that you know what are all the entities you are going to work.
That is, you know the size of the entities before hand.
This is not completely true! Often you want to use a list of entities where the number of entities are unknown before hand.
That is, you need to dynamically allocate memory.
For example the array size may not be known before hand.

12/27/2022

3 of 17

Dynamic memory

Basically what we want is:

To allocate memory to hold entities.
To free the memory when the entities are no longer required.
We can access the entities by their addresses; we can not create a name for the dynamically allocated memory (since this requires declaration of names).
So, pointers are essential.

12/27/2022

4 of 17

Dynamic memory allocation

stdlib.h contains

void *malloc(size_t size);

size_t is an alias for unsigned int.

malloc returns a pointer to space for an object of the given size. It returns NULL if the request cannot be satisfied. The space is uninitialized.

void *calloc(size_t n, size_t size);

returns a pointer to space for an array of n objects of the specified size, or NULL if the request cannot be satisfied. The storage is initialized to zero.

void free(void *p);

releases the memory pointed by p; p must be a pointer to space allocated dynamically. It does nothing if p is NULL.

12/27/2022

5 of 17

Dynamic memory allocation

void *realloc(void *block, size_t size);

realloc adjusts the amount of memory allocated to the block to size, copying the contents to the new location if necessary. block must be an allocated memory using dynamic memory functions.

On success, the function returns the address of the reallocated block, which might be different from the address of the original block.
On failure the function returns NULL.

12/27/2022

6 of 17

examples

int *p;

p = (int *)malloc( sizeof(int) );

*p = 10;

printf(“%d”, *p);

free(p);

the address returned by malloc needs to be type casted.

12/27/2022

7 of 17

example

int *p;

p = (int *) calloc(10, sizeof(int) );

/* now p is the starting address of an array of 10 ints */

p[5] = 10;

12/27/2022

8 of 17

Concepts of linked lists

List is a set of items organized sequentially. An array is an example of list.
In arrays sequential organization is provided by its index.
One problem with arrays is that size of an array must be specified and which cannot be a variable. This might be not possible in many real life applications.
One remedy is to use dynamic memory using malloc, calloc, etc.

12/27/2022

9 of 17

Arrays

One more problem with arrays is: how to insert a new element in the middle of an array.
Eg: int a[10] = { 0,1, 2, 3,5, 6,7};
Now we want to make a[4] = 4, a[5] = 5, ….
This can be achieved by several assignment statements. May be we can use a loop.
This is an overhead if you want to modify the sequence by adding a new element in between.
Similarly if you want to delete an element from the middle of an array. You need to pull forward all elements that follows the deleted element to fill the vacated space.

12/27/2022

10 of 17

lists

The problem with arrays is: it is not suitable for maintaining a list for which the size changes dynamically.
Dynamic memory allocation cannot solve this problem.

12/27/2022

11 of 17

Linked list

12/27/2022

Item

Structure 1

Structure 2

Structure 3

struct node {

int item;

struct node *next;

};

12 of 17

Linked list of names (in reverse order)

struct node { char name[64]; struct node * next; };

main( )

{

char s[64];

struct node *head = NULL, *new_node;

do{

puts(“enter a name:”);

gets(s);

if(strlen(s) > 0) {

new_node = (struct node *) malloc(sizeof(struct node));

strcpy(new_node->name, s);

new_node -> next = head;

head = new_node;

}

} while(strlen(s) > 0);

}

12/27/2022

13 of 17

How to insert in between a linked list

We want to insert a node s after the node pointed by where.
void insert(struct node *where, struct node s)

{

struct node *temp;

temp = where ->next;

where->next = &s;

s.next = temp;

}

12/27/2022

14 of 17

How to delete from middle

The following fn deletes a node which is after the node pointed by p
void delete(struct node *p)

{

struct node *temp;

temp = p ->next ->next;

free(p->next);

p->next = temp;

}

12/27/2022

15 of 17

Searching a linked list

Assume that structures contain some info like roll_no, marks, etc.
struct node *search(struct node *head, int roll_no)

{

struct node *temp;

temp = head;

while(temp != NULL) {

if(temp->roll_no == roll_no)

return(temp);

else temp = temp->next;

}

return NULL;

}

12/27/2022

16 of 17

17 of 17

Don’t we have any drawbacks of linked lists ?

If the list is a static one, then the next pointers in the linked list consumes additional space (which is not consumed by arrays).
Array is a randomly accessible data structure, whereas linked lists are sequential.
Searching a sorted array might be very easy when compared with searching a sorted linked list.

12/27/2022