Principles of C Programming Unit 13

Unit 13 Dynamic Memory Allocation and

Linked List
Structure:
13.1 Introduction
Objectives
13.2 Dynamic Memory Allocation
Allocating Memory with malloc
Allocating Memory with calloc
Freeing Memory
Reallocating Memory Blocks
13.3 Pointer Safety
13.4 The Concept of Linked list
Inserting a Node by using Recursive Programs
Sorting and Reversing a Linked List
Deleting the Specified Node in a Singly Linked List
13.5 Summary
13.6 Terminal Questions
13.7 Answers
13.8 Exercises

13.1 Introduction
In the previous unit, we learned about the preprocessor in C. We discussed
that the preprocessor is a program that processes the source code before it
passes through the compiler. During the preprocessing stage, all
occurrences of a macro name are replaced by the macro body that is
associated with the macro name. The C preprocessor also enables us to
include additional source files in the program or compile sections of C code
conditionally. In this unit, we will discuss the various dynamic memory
allocation techniques. We will also discuss the linked list data structure. A
linked list is a chain of nodes. Each node consists of data items and a
pointer that points to the next node in the list. The last item has a null
pointer to signify the end of the list.
An array can be used to process data of the same data type. At the time of
declaration, the size of data that is array size must be given. But this not
always the case; sometimes the size of data is not known. An example of

Sikkim Manipal University B2074 Page No.: 272

Principles of C Programming Unit 13

this is reservation system. At the time of compilation we do not the number

of customer comes for reservation or for the cancellation. In such a case, an
array is not useful because we do not know what the dimension of the array
should be.
Thus, it is desirable to create correct-sized array variables at runtime. The C
programming language provides facility to dynamically allocate and
deallocate memory when required. The functions that accomplish this are:
malloc(), calloc() and realloc() which allocates memory to a variable, sizeof(),
which determines how much memory a specified variable occupies, and
free(), which deallocates the memory assigned to a variable back to the
system.

Objectives:
After studying this unit, you should be able to:
 explain the dynamic memory allocation
 implement dynamic memory allocation functions like – malloc(), calloc()
and realloc()
 explain the concept of linked lists
 discuss the different operations on linked lists

13.2 Dynamic Memory Allocation

The process of allocating memory at run time is known as Dynamic Memory
Allocation. Although C does not inherently have this facility, there are four
library routines known as “Memory Management Functions” that can be
used for allocating and freeing memory during program execution. They are
listed in Table 13.1. These functions help us build complex application
programs that use the available memory intelligently.
Table 13.1: Functions used for Dynamic Memory allocations and its tasks
Function Tasks
malloc Allocates requested size of bytes and returns a pointer to the
first byte of the allocated space
calloc Allocates space for an array of elements, initializes them to zero
and then returns a pointer to the memory
free Frees previously allocated space
realloc Modifies the size of previously allocated space
Table 13.2 shows the conceptual view of storage of a C program in memory.

Sikkim Manipal University B2074 Page No.: 273

Principles of C Programming Unit 13

Table 13.2: storage of a C program- a conceptual view

Local variables
Free memory
Global variables
C program instructions

The program instructions and global and static variables are stored in a
region known as permanent storage area and the local variables are stored
in another area called stack. The memory space that is located between
these two regions is available for dynamic allocation during execution of the
program. This free memory region is called heap. The size of the heap
keeps changing when program is executed due to creation and deallocation
of variables that are local to functions and blocks. Therefore, it is possible to
encounter memory “overflow” during dynamic allocation process.
13.2.1 Allocating Memory with malloc
There are many cases when we do not know the exact size of arrays used
in programs, until much later when programs are actually being executed.
We can specify the sizes of arrays in advance, but the arrays can be too
small or too big if the numbers of data items we want to put into the arrays
change dramatically at runtime.
C provides dynamic memory allocation functions that we can employ to
allocate certain memory spaces while program is running. We can use the
malloc() function to allocate a specified size of memory space. The syntax
for the malloc() function is
#include <stdlib.h>
void *malloc(size_t size);
Here size indicates the number of bytes of storage to allocate. The malloc()
function returns a void pointer.
Note that the header file, stdlib.h, has to be included before the malloc()
function can be called.
Because the malloc() function itself returns a void pointer, its type is then
automatically converted to the type of the pointer on the left side of an
assignment operator in Compilers that are compliant with ANSI C. For the
compilers which are not compliant with ANSI C standard, we need to do the
type casting as :
ptr=(cast-type *)malloc(byte-size)
Sikkim Manipal University B2074 Page No.: 274
Principles of C Programming Unit 13

where ptr is a pointer of type cast-type. The malloc returns a pointer (of
cast-type) to an area of memory with size byte-size.
If the malloc() function fails to allocate a piece of memory space, it returns a
null pointer. Normally, this happens when enough memory is not available.
Therefore, we should always check the returned pointer from malloc()
before we use it. It is good programming practice that program should
immediately check for a null pointer, and if it returned pointer is a null
pointer, it should at least print an error message and exit, or figure out some
way of proceeding without the memory it asked for.

Example 13.1: Here is an example allocates block of 100 characters using

malloc()
#include <stdlib.h>
char *line;
int linelen = 100;
line = (char *)malloc(linelen);
if(ip == NULL)
{
printf("out of memory\n");
// code exit or return
}
getline(line, linelen);

If malloc returns NULL, after printing the error message, this code should
return to its caller, or exit from the program entirely; it cannot proceed with
the code that would have used ip.
Character data type takes one byte of storage. Invocation of malloc gives us
exactly space for 100 characters. Resulting pointer line looks like this:

The 100 bytes of memory (not all of which are shown) pointed to by line are
those allocated by malloc.
Now if we want to allocate memory for 100 integer numbers. We have to
calculate, how many bytes is that? If we know how big integers are on our

Sikkim Manipal University B2074 Page No.: 275

Principles of C Programming Unit 13

machine (depending on whether we are using a 16-bit or 32-bit machine) we

could try to compute it ourselves, but it is much safer and more portable to
let C compute it for us. We can use sizeof operator, which computes the
size, in bytes, of a variable or type. To allocate space for 100 integers, we
could call
int *ip =(int *)malloc(100 * sizeof(int));
Above call to malloc initializes ip to point at storage for 100 integers, we can
access integers as ip[0], ip[1], ... up to ip[99] and we can get the effect of an
array even if we do not know the size of array until run time.
Program 13.1: program to find sum of n elements entered by user with
dynamic memory allocation using malloc() function.
#include <stdio.h>
#include <stdlib.h>
int main(){
int n,i,*ptr,sum=0;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof(int)); //memory allocated using malloc
if(ptr==NULL)
{
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements of array: ");
for(i=0;i<n;++i)
{
scanf("%d",ptr+i);
sum+=*(ptr+i);
}
printf("Sum=%d",sum);
free(ptr);
return 0;
}

In program 13.1, we want to store integer numbers whose size is

determined runtime. To achieve this, we have used malloc function and
Sikkim Manipal University B2074 Page No.: 276
Principles of C Programming Unit 13

created an integer pointer *ptr, instead of using fixed sized array. Then
malloc function invoked by the statement ptr=(int*)malloc(n * sizeof(int));
in program. Note that the value of n is entered by user of program during the
execution of the program at run time.
13.2.2 Allocating Memory with calloc
Besides the malloc() function, we can also use the calloc() function to
allocate memory storage dynamically. The differences between the two
functions are that the latter takes two arguments and that the memory space
allocated by calloc() is always initialized to 0. There is no such guarantee
that the memory space allocated by malloc() is initialized to 0. The syntax
for the calloc() function is
#include <stdlib.h>
void *calloc(size_t nitem, size_t size);
Here nitem is the number of items we want to save in the allocated memory
space. size gives the number of bytes that each item takes. The calloc()
function returns a void pointer.
If the calloc() function fails to allocate a piece of memory space, it returns a
null pointer.
ptr=(cast-type *)calloc(n, elem-size);
The above statement allocates contiguous space for n blocks, each of size
elem-size bytes. All bytes are initialized to zero and a pointer to the first byte
of the allocated region is returned. If there is not enough space, a NULL
pointer is returned.
Program 13.2 Program to illustrate the use of malloc and calloc
functions.
#include <stdlib.h>
main()
{
float *ptr1, *ptr2;
int i, n;
n = 5;
ptr1 = calloc(n, sizeof(float));
ptr2 = malloc(n * sizeof(float));
if (ptr1 == NULL)

Sikkim Manipal University B2074 Page No.: 277

Principles of C Programming Unit 13

{
printf(“malloc() failed.\n”);
exit(0);
}
else if (ptr2 == NULL)
{
printf(“calloc() failed.\n”);
exit(0);
}
else
{
for (i=0; i<n; i++)
printf(“ptr1[%d]=%5.2f, ptr2[%d]=%5.2f\n”,i, *(ptr1 + i), i, *(ptr2
+ i));
free(ptr1);
free(ptr2);
}
}
Output :
ptr1[0] = 0.00, ptr2[0] = 7042.23
ptr1[1] = 0.00, ptr2[1] = 1427.00
ptr1[2] = 0.00, ptr2[2] = 2787.14
ptr1[3] = 0.00, ptr2[3] = 0.00
ptr1[4] = 0.00, ptr2[4] = 5834.73

In program 13.2, ptr1 and prt2 are two floating point pointers. Memory
allocation for ptr1 is achieved using calloc() function and for ptr2 is achieved
using malloc() function. The purpose of the program 13.2 is to use the
calloc() function to allocate a piece of memory space. To prove that the
calloc() function initializes the allocated memory space to 0, the initial values
of the memory are printed out. Also, another piece of memory space is
allocated by using the malloc() function, and the initial values of the second
memory space are printed out too.
13.2.3 Freeing Memory
If we have allocated a memory block with the functions malloc(), calloc() or
realloc() then we need to free the allocated memory if it is no longer

Sikkim Manipal University B2074 Page No.: 278

Principles of C Programming Unit 13

required. Memory allocated with malloc lasts as long as duration of program.

It does not automatically disappear when a function returns, as automatic
variables do. Just as we can use malloc to control exactly when and how
much memory we allocate, we can also control exactly when deallocate it.
Because memory is finite, it is a good idea to free memory we are no longer
using.
We can free dynamically allocated memory using the free function. If ptr
contains a pointer previously returned by malloc, we can call
free(ptr);
The memory which is free now can immediately become usable by other
parts of program. Theoretically, it may even be usable by other programs.
Freeing unused memory is a good idea, but it is not mandatory. When a
program exits, any memory which has been allocated to it but not freed
should be automatically released. If computer were to somehow “lose''
memory just because program forgot to free it, that would indicate a
problem or deficiency in operating system.
Naturally, once we have freed some memory we must remember not to use
it anymore. After calling
free(ptr);
it is probably the case that ptr still points at the same memory. However, a
later call to malloc might give that memory to some other part of program.
One good way to record the fact that it is not to be used anymore would be
to set ptr to a null pointer and we would not misuse any memory via the
pointer p:
free(p);
p = NULL;
13.2.4 Reallocating Memory Blocks
The realloc() function is used to change the size of a memory space
previously allocated by the malloc() function, the calloc() function, or even
realloc() itself. The syntax for the realloc() function is:

#include <stdlib.h>
void *realloc(void *block, size_t size);

Sikkim Manipal University B2074 Page No.: 279

Principles of C Programming Unit 13

Here block is the pointer to the start of a piece of memory space previously
allocated using malloc() or calloc(). size specifies the total byte number we
want to change to, it should not be less than size previously allocated. If it
is, we will get memory area allocated same as the previously available
memory area.
The realloc() function returns a void pointer. The realloc() function returns a
null pointer if it fails to reallocate a piece of memory space.
Example 13.2: if we wanted the ip variable from an earlier example to point
at 200 ints instead of 100, we could try calling
ip = realloc(ip, 200 * sizeof(int));
Example 13.3: Reads lines of text from the user, treats each line as an
integer by calling atoi, and stores each integer in a dynamically-
allocated “array'':
#define MAXLINE 100
char line[MAXLINE];
int *ip;
int nalloc, nitems;

nalloc = 100;
ip = (int *)malloc(nalloc * sizeof(int)); /* initial allocation */
if(ip == NULL)
{
printf("out of memory\n");
exit(1);
}

nitems = 0;

while(getline(line, MAXLINE) != EOF)

{
if(nitems >= nalloc)
{ /* increase allocation */
int *newp;
nalloc += 100;
newp = realloc(ip, nalloc * sizeof(int));
Sikkim Manipal University B2074 Page No.: 280
Principles of C Programming Unit 13

if(newp == NULL)
{
printf("out of memory\n");
exit(1);
}
ip = newp;
}

ip[nitems++] = atoi(line);
}

In code, two different variables keep track of the “array'' pointed to by ip.
nalloc is how many elements we have allocated, and nitems is how many of
them are in use. Whenever we are about to store another item in the
“array,'' if nitems >= nalloc, the old “array'' is full, and we need to call realloc
to make it bigger.
Self Assessment Questions
1. The process of allocating memory at run time is known as
_________________.
2. malloc() function returns a pointer to integer. (True/False)
3. For deallocating memory, ___________ function is used.
4. The function that is used to alter the size of a block previously allocated
is __________________.

13.3 Pointer Safety

The hard thing about pointers is not so much manipulating them as ensuring
that the memory they point to is valid. When a pointer does not point where
we think it does, if we inadvertently access or modify the memory it points to,
we can damage other parts of our program, or (in some cases) other
programs or the operating system itself.
When we use pointers to simple variables, there is not much that can go
wrong. When we use pointers into arrays, and begin moving the pointers
around, we have to be more careful, to ensure that the moving pointers
always stay within the bounds of the array(s). When we begin passing
pointers to functions, and especially when we begin returning them from

Sikkim Manipal University B2074 Page No.: 281

Principles of C Programming Unit 13

functions, we have to be more careful, because the code using the pointer
may be far removed from the code which owns or allocated the memory.
One particular problem concerns functions that return pointers. Where is the
memory to which the returned pointer points? Is it still around by the time
the function returns? The strstr function, returns either a null pointer (which
points definitively nowhere, and which the caller presumably checks for) or it
returns a pointer which points into the input string, which the caller supplied,
which is pretty safe. One thing a function must not do, however, is return a
pointer to one of its own, local, automatic arrays. Remember that automatic
variables (which includes all non-static local variables), including automatic
arrays, are deallocated and disappear when the function returns. If a
function returns a pointer to a local array, that pointer will be invalid by the
time the caller tries to use it.
Finally, when we are doing dynamic memory allocation with malloc, calloc,
realloc, and free, we have to be careful. Dynamic allocation gives us a lot
more flexibility in how our programs use memory, although with that
flexibility comes a responsibility that we must manage the dynamically
allocated memory carefully. The possibilities for misdirected pointers and
associated havoc are greatest in programs that make heavy use of dynamic
memory allocation. We can reduce this by designing the program in such a
way that it is easy to ensure that pointers are used correctly and that
memory is always allocated and deallocated correctly.

13.4 The Concept of Linked List

A linked list is a data structure that is used to model such a dynamic list of
data items, so the study of the linked lists as one of the data structures is
important. When dealing with many problems we need a dynamic list,
dynamic in the sense that the size requirement need not be known at
compile time. Thus, the list may grow or shrink during runtime.
Linked lists and arrays are similar since they both store collections of data.
Array elements are stored in memory in sequential form, which has the
property that elements are fixed distance apart. When we have dynamic list
of items, it is difficult to use arrays. This is because the insertion or deletion
at any arbitrary position in an array is a costly operation, as it involves the
movement of some existing elements.

Sikkim Manipal University B2074 Page No.: 282

Principles of C Programming Unit 13

One of the alternative representations to overcome these disadvantages is

a linked representation. In a linked representation, it is not necessary that
the elements be at a fixed distance apart. We can place elements anywhere
in the memory, but to make it a part of the same list, an element is required
to be linked with a previous element of the list. This can be done by storing
the address of the next element in the previous element itself. This requires
that every element be capable of holding the data as well as the address of
the next element. Thus, every element must be a structure with a minimum
of two fields, one for holding the data value, which we call a data field, and
the other for holding the address of the next element, which we call link field.
Therefore, a linked list is a chain of nodes (or elements). Each node
consists of data Field and link field, it is a pointer that points to the next
node in the list. The last item has a null pointer to signify the end of the list.
The figure 13.1 shows a node with data and link fields.

Figure 13.1: Node of a linked list

The figure 13.2 shows the linked list. The arrow drawn represents the link
between two nodes. The link field of last node contains a special value,
called null pointer which indicated the end of the list. The linked list also
contains a list pointer variable called START which contains the address of
the first node. The list with no node is called null list or empty list and it is
denoted by the null pointer in the variable START.

Figure 13.2: Linked list

Sikkim Manipal University B2074 Page No.: 283

Principles of C Programming Unit 13

Program 13.3: Here is a program for building and printing the elements
of the linked list
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
/* if the existing list is empty then insert a new node as the
starting node */
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node)); /* creates new node
data value passes as parameter */
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = p; /* makes the pointer pointing to itself because it
is a circular list*/
}
else
{
temp = p;
/* traverses the existing list to get the pointer to the last node of
it */
while (temp-> link != p)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node)); /*

Sikkim Manipal University B2074 Page No.: 284

Principles of C Programming Unit 13

creates new node using data value passes as parameter and puts its
address in the link field of last node of the existing list*/
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = p;
}
return (p);
}
void printlist ( struct node *p )
{
struct node *temp;
temp = p;
printf("The data values in the list are\n");
if(p!= NULL)
{
do
{
printf("%d\t",temp->data);
temp=temp->link;
} while (temp!= p);
}
else
printf("The list is empty\n");
}

void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");

Sikkim Manipal University B2074 Page No.: 285

Principles of C Programming Unit 13

scanf("%d",&n);
while ( n -- > 0 )
{
printf("Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("The created list is\n");
printlist ( start );
}

13.4.1 Inserting a Node by using Recursive Programs

A linked list is a recursive data structure. A recursive data structure is a data
structure that has the same form regardless of the size of the data. We can
easily write recursive programs for such data structures.
Program 13.4 : Program for inserting a node by using Recursion
# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;

Sikkim Manipal University B2074 Page No.: 286

Principles of C Programming Unit 13

}
else
p->link = insert(p->link,n);/* the while loop replaced by
recursive call */
return (p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- - 0 )
{
printf( "Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf("The created list is\n");
printlist ( start );
}

13.4.2 Sorting and Reversing a Linked List

To sort a linked list, first we traverse the list searching for the node with a
minimum data value. Then we remove that node and append it to another
list which is initially empty. We repeat this process with the remaining list

Sikkim Manipal University B2074 Page No.: 287

Principles of C Programming Unit 13

until the list becomes empty, and at the end, we return a pointer to the
beginning of the list to which all the nodes are moved.
To reverse a list, we maintain a pointer each to the previous and the next
node. Then we make the link field of the current node point to the previous,
make the previous equal to the current, and the current equal to the next.
Therefore, the code needed to reverse the list is
Prev = NULL;
While (curr != NULL)
{
Next = curr->link;
Curr -> link = prev;
Prev = curr;
Curr = next;
}

Program 13.5: Example in sorting lists.

# include <stdio.h>
# include <stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
Sikkim Manipal University B2074 Page No.: 288
Principles of C Programming Unit 13

}
else
{
temp = p;
while (temp-> link!= NULL)
temp = temp-> link;
temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = null;
}
return(p);
}

void printlist ( struct node *p )

{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}

/* a function to sort reverse list */

struct node *reverse(struct node *p)
{
struct node *prev, *curr;
prev = NULL;
curr = p;
while (curr != NULL)

Sikkim Manipal University B2074 Page No.: 289

Principles of C Programming Unit 13

{
p = p-> link;
curr-> link = prev;
prev = curr;
curr = p;
}
return(prev);
}
/* a function to sort a list */
struct node *sortlist(struct node *p)
{
struct node *temp1,*temp2,*min,*prev,*q;
q = NULL;
while(p != NULL)
{
prev = NULL;
min = temp1 = p;
temp2 = p -> link;
while ( temp2 != NULL )
{
if(min -> data > temp2 -> data)
{
min = temp2;
prev = temp1;
}
temp1 = temp2;
temp2 = temp2-> link;
}
if(prev == NULL)
p = min -> link;
else
prev -> link = min -> link;
min -> link = NULL;
if( q == NULL)
q = min; /* moves the node with the lowest data value in the list
pointed to by p to the list pointed to by q as a first node*/

Sikkim Manipal University B2074 Page No.: 290

Principles of C Programming Unit 13

else
{
temp1 = q;
/* traverses the list pointed to by q to get pointer to its
last node */
while( temp1 -> link != NULL)
temp1 = temp1 -> link;
temp1 -> link = min; /* moves the node with the lowest data value in
the list pointed to by p to the list pointed to by q at the end of list pointed by
q*/
}
}
return (q);
}

void main()
{
int n;
int x;
struct node *start = NULL ;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n- > 0 )
{
printf( "Enter the data values to be placed in a
node\n");
scanf("%d",&x);
start = insert ( start,x);
}
printf("The created list is\n");
printlist ( start );
start = sortlist(start);
printf("The sorted list is\n");
printlist ( start );
start = reverse(start);
printf("The reversed list is\n");
printlist ( start );
}

Sikkim Manipal University B2074 Page No.: 291

Principles of C Programming Unit 13

13.4.3 Deleting the Specified Node in a Singly Linked List

If the nodes of the list are numbered serially from 1 to n, to delete a node,
first we determine the node number to be deleted. Then we traverse the
linked list to get the pointer to the node whose number is given as well as a
pointer to a node that appears before the node to be deleted. Then the link
field of the node that appears before the node to be deleted is made to point
to the node that appears after the node to be deleted, and the node to be
deleted is freed.
Program 13.6: Example of working with nodes.
# include <stdio.h>
# include <stdlib.h>
struct node *delet ( struct node *, int );
int length ( struct node * );
struct node
{
int data;
struct node *link;
};
struct node *insert(struct node *p, int n)
{
struct node *temp;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
if(p==NULL)
{
printf("Error\n");
exit(0);
}
p-> data = n;
p-> link = NULL;
}
else
{
temp = p;
while (temp-> link != NULL)
Sikkim Manipal University B2074 Page No.: 292
Principles of C Programming Unit 13

temp = temp-> link;

temp-> link = (struct node *)malloc(sizeof(struct node));
if(temp -> link == NULL)
{
printf("Error\n");
exit(0);
}
temp = temp-> link;
temp-> data = n;
temp-> link = NULL;
}
return (p);
}
void printlist ( struct node *p )
{
printf("The data values in the list are\n");
while (p!= NULL)
{
printf("%d\t",p-> data);
p = p-> link;
}
}
void main()
{
int n;
int x;
struct node *start = NULL;
printf("Enter the nodes to be created \n");
scanf("%d",&n);
while ( n-- > 0 )
{
printf("Enter the data values to be placed in a node\n");
scanf("%d",&x);
start = insert ( start, x );
}
printf(" The list before deletion id\n");

Sikkim Manipal University B2074 Page No.: 293

Principles of C Programming Unit 13

printlist ( start );
printf("% \n Enter the node no \n");
scanf ( " %d",&n);
start = delet (start , n );
printf(" The list after deletion is\n");
printlist ( start );
}
/* a function to delete the specified node*/
struct node *delet ( struct node *p, int node_no )
{
struct node *prev, *curr ;
int i;

if (p == NULL )
{
printf("There is no node to be deleted \n");
}
else
{
if ( node_no > length (p))
{
printf("Error\n");
}
else
{
prev = NULL;
curr = p;
i=1;
while ( i < node_no )
{
prev = curr;
curr = curr-> link;
i = i+1;
}
if ( prev == NULL )
{
Sikkim Manipal University B2074 Page No.: 294
Principles of C Programming Unit 13

p = curr -> link;

free ( curr );
}
else
{
prev -> link = curr -> link ;
free ( curr );
}
}
}
return(p);
}
/* a function to compute the length of a linked list */
int length ( struct node *p )
{
int count = 0 ;
while ( p != NULL )
{
count++;
p = p->link;
}
return ( count ) ;
}

Self Assessment Questions

5. A linked list is a data structure that is used to model a dynamic list of
data items and is a collection of ___________.
6. Linked list make use of ____________ memory allocation technique.

13.5 Summary
 The process of allocating memory at run time is known as Dynamic
Memory Allocation.
 The allocation of memory is done using three functions: malloc(), calloc(),
and realloc(). These functions return the pointer to void, so it can be
typecast to any data type, thus making the functions generic.

Sikkim Manipal University B2074 Page No.: 295

Principles of C Programming Unit 13

 The memory space that is used for dynamic allocation during execution
of the program is called heap.
 When a pointer does not point where we think it does, if we inadvertently
access or modify the memory it points to, we can damage other parts of
program. So safety of pointers is essential in dynamic memory allocation.
 Linked list is one of the applications of dynamic memory allocation.

13.6 Terminal Questions

1. Assuming that there is a structure definition with structure tag student,
write the malloc function to allocate space for the structure.
2. Write a structure definition to represent a node in the linked list with two
data fields of type integer.
3. If ptr points to a node and link is the address field of the node, how can
we move from the node to the next node?
4. Explain concept of the linked list.
5. Explain Reallocating Memory Blocks in C.

13.7 Answers
Self Assessment Questions
1. Dynamic Memory Allocation.
2. False
3. free()
4. realloc()
5. nodes.
6. dynamic

Terminal Questions
1. ptr=(struct student *) malloc(sizeof(struct student));
(Refer to section 13.2.1 for more details)
2. struct node
{
int data1;
int data2;
struct node *link;
};
(Refer to section 13.2.1 for more details)

Sikkim Manipal University B2074 Page No.: 296

Principles of C Programming Unit 13

3. ptr=ptr->link; (Refer to section 13.4 for more details)

4. A linked list is a data structure that is used to model a dynamic list of
data items and is a collection of nodes. (Refer to section 13.4 for more
details).
5. The realloc() function is used to change the size of a memory space
previously allocated by the malloc() function, the calloc() function, or
even realloc() itself. (Refer to section 13.2.4 for more details).

13.8 Exercises
1. Write a menu driven program to create a linked list of a class of students
and perform the following operations.
i. Write out the contents of a list
ii. Edit the details of a specified student
iii. Count the number of students above a specified age and weight
2. Write a program to insert a node after the specified node in a linked list.
3. Write a program to count the number of nodes in linked list.
4. Write a program to merge two sorted lists.
5. Explain briefly how to represent polynomials using linked lists. Write a
program to add two polynomials.
Reference and further reading:
1. Balaguruswami, “Programming In Ansi C 5E” Tata McGraw-Hill
2. Ajay Mittal (2010), “Programming In C: A Practical Approach”, Published
by Pearson education.

Sikkim Manipal University B2074 Page No.: 297