CHAPTER 16

Dynamic Memory Allocation and Linked List

Chapter Outline

16.1 Dynamic Memory Allocation

16.2 Memory Models

16.3 Memory Allocation Functions

16.4 List

16.5 Traversal of a List

16.6 Searching and Retrieving an Element

16.7 Predecessor and Successor

16.8 Insertion

16.9 Linked Lists

16.10 Linked List with and without Header

16.1 DYNAMIC MEMORY ALLOCATION

For the execution of a program, it is essential to bring the

program in the main memory. When a program does not fit into
the main memory, parts of it are brought into the main memory
one by one and the full program is executed eventually. Of
course, the parts of program which are not currently in main
memory are resident either at secondary memory such as floppy
or hard disk or at any other magnetic disk. When a new segment
of a program is to be moved into a full main memory, it must
replace another segment already resident in the main memory.
There are memory replacement policies and their description is
beyond the scope of this book. Hence, a programmer should not
worry about the method of transfer of program from secondary
to primary memory or memory replacement policies.
There are two techniques used for storing the information of C
programs in the main memory. The first technique involves
storing global and local variables, which are fixed during
compilation and remain constant throughout the run time
program. Here, even the variables of structures and arrays are
stored in the main memory during compilation. Space for local
variables is allocated from the stack each time when the variable
comes into existence. Global and local variables are efficiently
stored in C. But the programmer must know the amount of space
required for every program.

The second technique by which a program can obtain memory

space in the main memory is with dynamic allocation. One of the
features provided in C is the allocation of memory at the time of
execution of a program. The method of allocation of memory at
the time of execution of a program is called dynamic memory
allocation. Acquiring main memory by a program and freeing it
are done by some library functions provided in C. Memory
allocation techniques are described in this chapter. These
functions are described in the following sections.

The free region of the memory is called the heap. The size of
heap does not remain constant all the time for all the programs.
Its size keeps on changing during the execution of program. This
is due to creation and destruction of variables that are local to
the functions and bocks.

Conceptually the C programs are stored as per Figure 16.1. The

heap changes depending on the memory model used. 8086
memory models are described in this chapter. The amount of
memory requirement is decided by how the program is designed.
For example, if a program is developed with many recursive
functions then this is implemented with stack
Figure 16.1 A view of a C program’s use of memory

16.2 MEMORY MODELS

1. TINY: All segment registers are initialized with the identical value
and all addressing is accomplished using 16 bits. This means that
the code, data and stack all must fit within the same 64-KB segment.
Programs are executed quickly in this case.
2. SMALL: All codes should fit in a single 64-KB segment and all data
should fit in a second 64-KB segment. All pointers are 16 bits in
length. Execution speed is the same as tiny model.
3. MEDIUM: All data should be fit in a single 64-KB segment;
however, the code is allowed to use multiple segments. All pointers
to data are 16 bits, but all jumps and calls require 32-bit addresses.
Fast access to data is observed, but slower program execution is
also noticed with this model.
4. COMPACT: All codes should fit in 64 KB segment, but the data can
use multiple segments. However, no data item can surpass 64 KB.
All pointers to data are 32 bits, but jumps and calls can use 16 bit
addresses. There is slow access to data and quick code execution.
5. LARGE: Both code and data are allowed to use multiple segments.
All pointers are 32 bits in length. However, no single data item can
exceed 64 KB. There is slower code execution.
6. HUGE: Both code and data are allowed to use multiple segments.
Every pointer is of 32-bit in length. Single data item can exceed 64
KB. There is slowest code execution.

16.3 MEMORY ALLOCATION FUNCTIONS

A variable is allowed to use memory to store its value. But
permanently memory is not used by the variables. Recent
programming languages permit memory space for storing the
variables when necessary. They also deallocate the memory of
the variables when not required. Dynamic memory allocation
permits to use memory for the variables at run time with
memory allocation functions. In this and the following sections,
we discuss the various memory allocation and deallocation
functions together with their implementation in the programs.

1. malloc(): A memory block is allocated with a function

called malloc(). In other words, the malloc() function is used to
allocate memory space in bytes to the variables of different data
types. The function reserves bytes of determined size and returns
the base address to pointer variable. The prototypes are declared
in alloc.h and stdlib.h. The format of the malloc() function is as
follows:
pnt= (data type*) malloc(given size);
Here, from data type, compiler understands the pointer
type and given size is the size to reserve in the memory.
For example:
pnt=( int *) malloc(20);
Here, in this declaration 20 bytes are allocated to pointer
variable pnt of type int and base address is returned to
pointer pnt.
A few programs are illustrated below on this function.

16.1 Write a program to allocate memory to a pointer

variable based on the number of subjects marks to be
entered. Compute average marks.

# include <alloc.h>

void main()

int k,*p,j=0,sum=0;

float avg;

clrscr();
 puts(“\n How many subjects marks to be entered :
”);

scanf(“%d”,&k);

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

while(j!=k)

printf(“Subject %d marks=”,j+1);

scanf(“%d”,p+j);

j++;

j=0;

printf(“\n Sum of marks : ”);

while(j!=k)

sum=*(p+j++)+sum;

printf(“%d”,sum);

avg=sum/k;

printf(“\n Average marks =%f: ”,avg);

getche();

OUTPUT:

How many subjects marks to be entered :

Subject 1 marks=88

Subject 2 marks=89
Subject 3 marks=90

Subject 4 marks=87

Subject 5 marks=91

Sum of marks : 445

Average marks =89.000000:

Explanation:
In the above program, program prompts user to enter the
number of subjects. The sizeof function determines the
size of data type required to store single value of that
type. The size determined by sizeof function and the
number entered (k) are multiplied and the result obtained
is nothing but the number bytes to be allocated to a
pointer ‘ * p’. The pointer ‘ * p’ contains the base address.
The first while loop reads marks of the subjects through
the keyboard. Each time while entering the marks,
‘j’ variables value is added to pointer ‘ * p’, which indicates
successive address of its type and entered subjects marks
are stored in the successive locations. This process is
continued till the value of ‘j’ reaches to ‘k’. Thus, in a
single variable by allocating memory, a programmer can
store multiple subjects marks. In the second while loop,
sum and average of marks are calculated.

16.2 Write a program to allocate memory to a pointer

variable based on the number of items. Display the values
of items.

void main()

int *ptr;

int i, item;

clrscr();

printf(“How many items you want?”);

scanf(“%d”,&item);
 ptr = (int*)malloc(sizeof(int)*item);

printf(“\nEnter the values of items in Rs:”);

for(i=0;i<item;i++)

scanf(“%d”,(ptr+i));

printf(“You have entered the values :\n”);

for(i=0;i<item;i++)

printf(“\n%d”,*(ptr+i));

OUTPUT:

How many items you want?3

Enter the values of items in Rs:111

233

100

You have entered the values :

111

233

100
Explanation:
Refer to the explanation of Example 16.1.
2. calloc(): This function is useful for allocating multiple blocks of
memory. It is declared with two arguments. The prototypes are
declared in alloc.h and stdlib.h. The format of
the calloc() function is as follows:
pnt= (int *)calloc(4,2);
The above declaration allocates four blocks of memory;
each block containing two bytes. The base address is
stored in the integer pointer. This function is usually used
for allocating memory for array and structure. The calloc()
can be used in place of the malloc() function. The
programs illustrated with the malloc() function can be
executed using the calloc() function.

16.3 Write a program to allocate memory based on

requirement of the number of books to a pointer variable
using the calloc() function.

# include <alloc.h>

void main()

int k,j=0,sum=0;

int *p;

clrscr();

puts(“\n How many books to be purchased?”);

scanf(“%d”,&k);

p=(int *) calloc(k,2);

while(j!=k)

printf(“Cost of the book(%d)=”,j+1);

scanf(“%d”,p+j);

sum=sum+*(p+j);

j++;

printf(“\n Total cost of the books: ”);

printf(“%d”,sum);

}
 OUTPUT:

How many books to be purchased?

Cost of the book(1)=100

Cost of the book(2)=200

Cost of the book(3)=400

Cost of the book(4)=500

Total cost of the books: 1200

Explanation:
Logic of the above program is the same as the previous
one.
Here, the calloc() function is used to allocate the
memory instead of malloc().
3. free(): The free() function is used to release the memory if not
required. Thus, using this function the wastage of memory is
prevented. The declaration of the function is as follows:
free(pnt);
In the above declaration, pnt is a pointer.
The free() function releases the memory occupied by the
pointer variable pnt. You can put free(p) after the first
while loop and see its response by executing the program.
16.4 Based on the requirement of the number of e-
books, write a program to allocate memory
using calloc() and release it using free(). Display the
memory locations where the cost of the each e-book is
stored and total cost of e-books.

Given below program is supporting free(pnt).

# include <alloc.h>

void main()

int j=0,k=5;
 int *p;

float sum=0.0;

clrscr();

p=(int *) calloc(k * sizeof(int),2);

printf(“\nFirst location %u”,p);

printf(“\n”);

while(j!=k)

printf(“\nCost of the e-book(%d)=”,j+1);

scanf(“%d”,p+j);

printf(“(%d)location %u\n”,j+1,p+j);

sum=sum+*(p+j);

j++;

printf(“\n Total cost of the e-books: ”);

printf(“%g”,sum);

free(p);

printf(“\n After freeing the memory the

location:%u”,p);

OUTPUT:

First location 3176

Cost of the e-book(1)=1000

(1)location 3176
 Cost of the e-book(2)=2000

(2)location 3178

Cost of the e-book(3)=3000

(3)location 3180

Cost of the e-book(4)=4000

(4)location 3182

Cost of the e-book(5)=5000

(5)location 3184

Total cost of the e-books: 15000

After freeing the memory the location:3176

Explanation:
Program logic is the same as used in the earlier programs
where calloc() is used. In addition to this free() is used for
freeing the memory. Different locations where the costs of
e-books are stored are displayed.
4. realloc(): This function reallocates the main memory. This is
needed as and when allocat ed memory is different from the
required memory. The prototypes are declared
in alloc.h and stdlib.h. Attempts are made to shrink or enlarge
the previously allocated memory by malloc()or calloc()functions.
It returns the address of the reallocated block, which can be
different from the original address. If the block cannot be
reallocated or size == 0, realloc()returns NULL. The declaration
of function is as follows:
str=(char*) realloc (str, 30)
In the above declaration, str is a pointer.
The realloc() function reallocates the memory
previously allocated by pointer variable str to the new size
30.

16.5 Write a program to reallocate memory using

realloc() function.

# include <alloc.h>
# include <string.h>

void main()

char *str;

str=(char *)malloc(6);

str=(“India”);

clrscr();

printf(“str = %s”,str);

str=( char *)realloc(str,30);

strcpy(str,“Great Researchers’ of India”);

printf(“\nNow str= %s”,str);free(str);

OUTPUT:

str = India

Now str= Great Researchers’ of India

Explanation:
In the above program, using malloc() function six 6 bytes
are allocated to character pointer str. The character
pointer is initialized with string ‘India’. To store more than
six characters, we need to allocate more bytes to
pointer str. Using realloc() function memory
reallocation takes place. After reallocation the pointer
contains 30 bytes. The pointer str is again initialized with
‘Great Researchers’ of India’ The output displays contents
of str before and after reallocation. The free() function
releases the memory allocated.

16.6 Write a program to display two numbers

with malloc() and reallocate memory for displaying three
numbers.
# include <alloc.h>

# include <string.h>

void main()

int j,*p;

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

clrscr();

for(j=0;j<2;j++)

printf(“number %d=”,j+1);

scanf(“\n%d”,(p+j));

printf(“\nNumbers are”);

printf(“\n”);

for(j=0;j<2;j++)

printf(“number %d= %d\n”,j+1,*(j+p));

printf(“\n\n”);

printf(“numbers after Reallocation\n”);

p=( int *) realloc (p,6);

for(j=0;j<3;j++)

printf(“number %d=”,j+1);

scanf(“\n%d”,(p+j));
 }

printf(“\nnumbers are\n ”);

for(j=0;j<3;j++)

printf(“number %d= %d\n”,j+1,*(j+p));

free(p);

getche();

OUTPUT:

number 1=1

number 2=2

Numbers are

number 1= 1

number 2= 2

numbers after Reallocation

number 1=3

number 2=4

number 3=5

numbers are

number 1= 3

number 2= 4
 number 3= 5
Explanation:
In the above program, using malloc() function four bytes
are allocated to two integers to pointer p. The integer
pointer is initialized with for loop. To store three integers,
we need to allocate more bytes to pointer p. Using
the realloc() function, memory reallocation takes place.
After reallocation the pointer contains six bytes. The
pointer p is again initial-ized. The output displays contents
of p before and after reallocation. The free() function
releases the memory allocated.
5. coreleft(): This function returns a measure of unused memory. If
the memory model selected is tiny, small or medium, then follow the
function declaration as per statement (a). If the memory model
selected is compact, large or huge, follow the declaration (b).

1. unsigned coreleft(void);
2. unsigned long coreleft (void);
16.7 Write a program to display unused memory using
the coreleft() function.

# include <alloc.h>

void main()

clrscr();

printf(“\n Measure of unused memory =

%u”,coreleft());

OUTPUT:

Measure of unused memory = 56936

Explanation:
In the above program, the function coreleft() is invoked
without any argument. The function displays unused
memory i.e. 56936.
 16.4 LIST

A list is a sequential arrangement of elements. The programmer

can add, delete or search the individual element in the list. There
are two techniques for creating lists. A list is created using an
array or linked lists.

First method is to take an array and store the elements. Arrays

have many drawbacks. To delete an element from an array or to
insert an element into an array, it requires a lot of actions. It may
be possible that the required elements in the list may be
more/less than declared size of an array. The operations such as
deletion, insertion, searching of element can be performed on an
array.

The list implemented using an array is called a static list. A list is

a series of linearly arranged numbers of the same data type. The
list can be of basic data type or custom data type. The elements
are positioned one after another and their position number
appears in sequence. The first element of the list is called HEAD
and the last element is called TAIL.

Please refer to Figure 16.2, where elements having a value 1 is

at HEAD position (0th) and element 2 is at TAIL position (5th).
The element 5 is a predecessor of the element 8 and 4 is
a successor. Every element can act as a successor excluding the
first element because it is the first element of the list. The list
has the following properties:

Figure 16.2 Elements of a list

1. The list can be enlarged or reduced from the end.

2. The TAIL (ending) position of the list depends on how long the list is
extended by the user.
3. Various operations such as transverse, insertion and deletion can be
performed on the list.
 4. Applying static (array) or dynamic (pointer) a list can be
implemented.

16.5 TRAVERSAL OF A LIST

The simple list can be created using an array. In it elements are

stored in successive memory locations. Consider the following
program.

16.8 Write a program to create a simple list of elements.

Display the list in original and reverse order.

void main()

int arr[5],j;

clrscr();

printf(“\nEnter five integers : ”);

for(j=0;j<5;j++)

scanf(“%d”,&arr[j]);

printf(“\n Elements of List are: ”);

for(j=0;j<5;j++)

printf(“ %d ”,arr[j]);

printf(“\n Elements of List in reverse :”);

for(j=4;j>=0;j--)

printf(“ %d”,arr[j]);

OUTPUT:

Enter five integers : 4 5 6 7 8

Elements of List are: 4 5 6 7 8

Elements of List in reverse : 8 7 6 5 4

Explanation:

Using simple declaration of an array, a list can be implemented.

Using for loop and scanf() statements, five integers are
entered. The list can be displayed using printf() statement.
Once a list is created, various operations such as sorting,
searching can be applied. A user is advised to see the
chapter Data Structure: Array for more information on arrays.

16.6 SEARCHING AND RETRIEVING AN ELEMENT

Once a list is created, we can access and perform operations

with the elements. In the last program, all the elements are
displayed. One can also specify some conditions such as to
display numbers after a specific number or remove the duplicate
numbers from the list or finding a specific number or
concatenation of two lists, etc. If the list contains large elements,
then it may be difficult to find a particular element and its
position. Consider the following program on searching an
element from the list.

16.9 Write a program to create a list of integer elements and

search the entered number from the list.

void main()

int sim[5],j,n,f=0;

clrscr();

printf(“\nEnter five Integers : ”);

for(j=0;j<5;j++)

scanf(“%d”,&sim[j]);
 printf(“\n Enter an integer from the entered numbers
for Search :”);

scanf(“%d”,&n);

for(j=0;j<5;j++)

if(sim[j]==n)

f=1;

printf(“\n Found ! Position of integer %d is %d “,

n,j+1 );

break;

if(f==0)

printf(“\n Element not found ! ”);

OUTPUT:

Enter five Integers : 1 2 3 4 5

Enter an integer from the entered numbers for Search :

4

Found ! Position of integer 4 is 4

16.7 PREDECESSOR AND SUCCESSOR

In the list of elements, for any location n, (n-1) is the predecessor

and (n+1)is successor. In other words, for any location n in the
list the left element is a predecessor and the right element is a
successor. One can find predecessor and successors of an
element in the list. The first element of a list does not have a
predecessor and last does not have a successor.

Figure 16.3 shows the predecessor and successor elements of

number 10.

Figure 16.3 Predecessor and successor

The following program displays the predecessor and successor

elements of the entered element from the list.

16.10 Write a program to find predecessor and successor of

the entered number in a list.

void main()

int num[8],j,n,k=0,f=0;

clrscr();

printf(“\n Enter eight elements : ”);

for(j=0;j<8;j++)

scanf(“%d”,&num[j]);

printf(“\n Enter an element : ”);

scanf(“%d”,&n);

for(j=0;j<8;j++)

if(n==num[j])
 {

f=1;

(j>0) ? printf(“\n The Predecessor of %d is

%d ” ,num[j],num[j-1]):

printf(“ No Predecessor”);

(j==7) ? printf(“\n No Successor”) :

printf(“\n The Successor of %d is %d”,

num[j],num[j+1]);

break;

k++;

if(f==0)

printf(“\nThe element %d is not found in list”,n);

OUTPUT:

Enter eight elements: 1 2 5 8 7 4 4 6

Enter an element: 5

The Predecessor of 5 is 2

The Successor of 5 is 8

Enter eight elements : 1 2 3 4 5 6 7 8

Enter an element : 1

No Predecessor

The Successor of 1 is 2
 Enter eight elements : 12 34 54 76 69 78 85 97

Enter an element : 3

The element 3 is not found in list

Explanation:

In this program, eight elements are entered. The user has to

enter an element whose predecessor and successors are to be
identified.All the elements of the array are checked with the
entered number. When the match is found, the next element of
the entered number displays as a successor and the previous
element displays as a predecessor. If the element entered is the
first element of the list then only successor is displayed. If the
entered element is the last element of the list then only the
predecessor is displayed. The above conditions are checked
using conditional operator (? :).

16.8 INSERTION

Appending is a process in which a new element is added.

However, insertion of an element can also be done in the list.
Insertion means an element is added in between two elements in
the list. The insertion can be done at the beginning, inside or
anywhere in the list.

For a successful insertion of an element, the array-implementing

list should have at least one empty location. If the array is full,
insertion cannot be possible. The target location where element
is to be inserted is made empty by shifting elements downwards
by one position and the newly inserted element is placed at that
location. Consider Figure 16.4.

(a)

As per the above figure, two empty spaces are available. Suppose
we want to insert 3 in between 7 and 9. All the elements after 7
must be shifted towards the end of the array. The resulting array
would be
(b)

The entered number 3 can be assigned to that memory location

and the array would look like. Figure 16.4 describes the insertion
of an element. The following program illustrates the insertion
operation.

(c)

Figure 16.4 Insertion

16.11 Write a program to create a list. Insert some element at

the specified location.

# include <process.h>

void main()

int num[8]={0},j,k=0,p,n;

clrscr();

printf(“\n Enter elements ( 0 to exit ) : ” );

for(j=0;j<8;j++)

scanf(“%d”,&num[j]);

if( num[j]==0)

break;

}
 if(j<8)

printf(“\n Enter Position number and element : ”);

scanf(“%d %d”,&p,&n);

--p;

else

while(num[ k]!=0)

k++;

k--;

for(j=k;j>=p;j--)

num[ j+1]=num[j];

num[p]=n;

for(j=0;j<8;j++)

printf(“ %d ”, num[ j]);

OUTPUT:

Enter elements (0 to exit) : 1 2 3 4 5 6 0

Enter Position number and element: 5 10

1 2 3 4 10 5 6 0

Explanation:

In the above program, an array num[8] is declared. The user has

to enter elements continuously. A user can enter zero to exit
from the continuous input routine. If zero is entered, the break
statement takes control out of the for loop. Thus, the list contains
a few empty memory locations, which are enough to carry out
insertion operations. When a user enters eight elements then the
program ends. In this case, due to the lack of space, insertion
operation is impossible.

The position number where an element is to be inserted is

prompted by the program. After entering these values by the
user, using while loop, the position of the first vacant location is
determined. From user-specified position number, next all
successive elements are shifted one memory location towards
down side of array. Due to shifting one memory, space is
generated and the entered element is placed at that location.

The reader can perform other operations on list such as the

deletion of an element, sorting of elements and merging two
lists.

16.9 LINKED LISTS

A linked list is implemented with pointers. This method is called

Dynamic implementation because all operations as described
above on the list can be implemented without complication. By
applying increment, operation on pointer successive locations of
memory can be accessed and an element can be stored in that
location. Thus, the series of element can be continued to any
number of elements. The programmer has to keep the starting
address of the pointer in which the first element is stored. Thus,
in the same way, the numbers can be viewed or altered. Here is
the simple example.

Singly Linked list

In this type of linked list, two successive nodes of the linked list
are linked with each other in sequential linear manner, Figure
16.5 describes singly link list. It is like a train, in which two
successive bogies are connected. The train is an example of
single linked list.

Figure 16.5 Single linked list

A linked list is a dynamic data structure with the ability to
expand and shrink as per the program requirement. The singly
liked list is easy and straightforward data structure as compared
to other structure. By changing the link position, other type of
linked list such as circular, doubly linked list can be formed. For
creating a linked list, the structure is defined as follows:

struct node

int number;

struct node *p;

};

The above structure is used to implement the linked list. In it

the number, variable entered numbers are stored. The second
member is pointer to the same structure. The pointer p points to
the same structure. Here, though the declaration of struct node
has not been completed, the compiler permits the pointer
declaration of the same structure type. However, the variable
declaration is not allowed. This is because the pointers are
dynamic in nature whereas variables are formed by early
binding. The declaration of objects inside the struct leads to the
preparation of very complex data structure. This concept is
called object composition and its detailed discussion is out of the
scope of this book.

We are familiar with the array and we know the importance of

the base address. Once a base address is obtained, later
successive elements can be accessed. In the linked list, also a list
can be created with or without header node. The head holds the
starting address.

16.12 Write a program to create a simple linked list.

struct list

int n;
 struct list *p;

};

void main()

struct list item0,item1, item2;

item2.n=3;

item2.p=NULL;

item1.n=5;

item1.p=&item2.n;

item0.n=7;

item0.p=&item1.n;

clrscr();

printf(“\n Linked list elements are :”);

printf(“ %d ”,item0.n);

printf(“ %d ”,*item0.p);

printf(“ %d ”,*item1.p);

printf(“ %d ”,*item2.p);

OUTPUT:

Linked list elements are: 7 5 3 0

Explanation:

In the above program, the structure list is declared with two

elements int n and struct list *p. The pointer *p recursively
points to the same structure. The struct list item0,
item1 and item2 are three variables of type list. Consider the
initialization
item2.n=3;

item2.p=NULL;

The item2 is the third (last) node of the list. The pointer *p is
initialized with a null. This is because node 2 is the last node and
after this node no node exists and thus it need not require to
pointing any address.

item1.n=5;

item1.p=&item2.n;

In this node, n is assigned with five. The pointer points to the

data field of the next node, i.e. item2.n (7).

item0.n=7;

item0.p=&item1.n;

16.10 LINKED LIST WITH AND WITHOUT HEADER

16.10.1 Linked List with Header

The following steps are used to create linked list with header:

1. Three pointers header, first and rear are declared. The header
pointer is initially initialized with NULL. For example,
header=NULL, where the header is pointer to structure. If it
remains NULL, it implies that the list has no element. Such list is
known as the NULL list or empty list. Figure 16.6 explains header
pointer initialization.

Figure 16.6 Header pointer initialization

2. In the second step, memory is allocated for the first node of the
linked list. For example, the address of the first node is 1888. An
 integer say 8 is stored in the variable num and value of header is
assigned to pointer next. Figure 16.7 enlightens memory allocation
to the first node.

Figure 16.7 Memory allocation to the first node

Both the header and rear are initialized the address of first
node.
The statement would be

header=first;
rear=first;

3. The address of pointer first is assigned to

pointers header and rear. The rear pointer is used to identify the
end of the list and to detect the NULL pointer.
4. Again, create a memory location, suppose 1890, for the successive
node.
5. Join the element of 1890 by assigning the value of node rear-
>next. Move the rear pointer to the last node.

Figure 16.8 Rear pointer to the last node with other

pointers

The following program explains the above concept.

16.13 Write a program to create the linked list with header

# include <malloc.h>

struct num
{

int num;

struct num *next;

*header,*first,*rear;

void main()

void form(void);

form();

clrscr();

printf(“\n Linked list elements are : ”);

while (header!=NULL)

printf(“ %d ”,header->num);

header=header->next;

void form(void)

struct num *node;

printf(“\n Enter number : ”);

if(header==NULL)

first=(struct num*)malloc(size of(struct num));

 scanf(“%d”,&first->num);

first->next=header;

header=first;

rear=first;

while(1)

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

scanf(“%d”,&node->num);

if(node->num==0) break;

node->next=NULL;

rear->next=node;

rear=node;

OUTPUT:

Enter number : 1 3 4 8 7 9 0

Linked list elements are : 1 3 4 8 7 9

Explanation:

The above program is an example of linked list with header.

Three structure pointers header,*first and *rear are declared
after structure declaration. Initially, these pointers are NULL
because they are declared as global. The form function is used to
create linked list nodes. Inside the function form() another
structure pointer *node is defined and its scope is local to the
same function. The procedure for creating the first and later
successive nodes is different. The if() statement checks the value
of the header. The value of header is NULL. The malloc()
function allocates memory to pointer first and the entered
number is stored in variable num of the node. In the same if()
block, both the pointer’s header and rear are assigned the value
of first. Once the first node is created, next time the execution of
the if() block is not required. The while loop iterated
continuously and successive nodes are created by allocating
memory to the pointer node. Consider the statements

1. node->next=NULL;
The above statement assigns NULL to the pointer next of
current node. If users do not want, create more nodes. The
linked list can be closed here.
2. rear->next=node;
The rear pointer keeps track of the last node, the address
of current node (node) is assigned to link field of the
previous node.
3. rear=node;

Before creating the next node, the address of the last

created node is assigned to the pointer *rear, which is
used for statement (2). In function main(), using while loop
the elements of linked list are displayed.
Header: The pointer *header is very useful in the formation
of the linked list. The address of the first node (1888) is
stored in pointer *header. The value of the header remains
unchanged until it turns out to be NULL. Pointer *header only
can determine the starting location of the list only.

while(header!=NULL)

printf(“ %d ” ,header->num);

header=header->next;

We can perform different operations on the linked list. They are

as follows.

1. Traversing a Link List:

 Figure 16.9 Linked list

In the above linked list, the data is the information part

of the structure (Figure 16.9). The link is the address of the
coming element. BEGIN is the address of the first element.
We declare P as a pointer variable. First p points to the
address of the BEGIN that points to the first element of the
list. For accessing the next element, we give the address
of the next element to the P as:
p=p->LINK
Now, the P has the address of the next element. We can
traverse the entire list till the P has NULL address.
2. Searching a Link List : Searching refers to the searching of an
element into a linked list. For searching the element, initially we
transverse the linked list and with traversing the list we compare
data part of each element with the given element.
3. Insertion into a Linked List: Insertion into a linked list is possible
in two methods (Figure 16.10)

1. Insertion at beginning
2. Insertion in between
 Figure 16.10 Insertion of element at the
beginning of the linked list

P is the address of the BEGIN. For inserting at the

beginning address of the P is given to the link part.

Figure 16.11 Insertion of element in between the

linked list

First we transverse the list for finding the node.

After that, we insert the element. For inserting the
element after the particular node, we give the
address of that node to the link part of the inserted
node and address of the inserted node is arranged
into the LINK part of the former node (Figure 16.11).

(a) Deletion from linked list

Figure 16.12 Deletion of element at the beginning of linked list

For deleting the node from the linked list, first we transverse the
linked list and compare the every element (Figure 16.12). If the
element is the first element then we give the address of the link
part of node to the pt.Here, pt is another pointer, which points
to the address of BEGIN.

pt=p-> LINK
If the element is other than the first element, then we give the
address of the link part of the deleted node to the link part of the
previous node (Figure 16.13).

Figure 16.13 Deletion of element in between the linked list

16.14 Write a program to create a linked list. Add, delete and

insert the element in the linked list. Also display and count the
elements of the linked list.

# include <alloc.h>

struct node

int data;

struct node *next;

*p;

printf(“Enter the element : ”);

void addatstart(struct node *pt,int);

void append(struct node *pt, int, int);

void erase(struct node *pt,int);

void show(struct node *pt);

void count(struct node *pt);

void descending(struct node *pt);

void main()
{

int n,m,po,d,i,j;

char ch=‘y’;

clrscr();

p=NULL;

do

clrscr();

printf(“ 1 Generate\n”);

printf(“ 2 Add at starting\n”);

printf(“ 3 Append \n”);

printf(“ 4 Delete\n”);

printf(“ 5 Show\n”);

printf(“ 6 Count\n”);

printf(“ 7 Descending\n”);

printf(“Enter your choice : ”);

scanf(“%d”,&n);

switch(n)

case 1:

printf(“\n How many node you want : ”);

scanf(“%d”,&i);

for(j=0;j<i;j++)

{
 printf(“enter the element : ”);

scanf(“%d”,&m);

gen_rate (p,m);

show(p);

break;

case 2:

printf(“Enter the element : ”);

scanf(“%d”,&m);

addatstart(p,m);

show(p);

break;

case 3 :

printf(“\n Enter the element and position ”);

scanf(“%d %d”,&m,&po);

append(p,m,po);

show(p);

break;

case 4 :

printf(“\n Enter the number for deletion :”);

scanf(“%d”,&d);

erase(p,d);

show(p);

break;
 case 5 :

show(p);

break;

case 6 :

count(p);

break;

case 7:

descending(p);

break;

default:

printf(“\n Enter value between 1 to 7”);

printf(“\n Do u want to continue (Y/N)”);

ch=getche();

while (ch==‘Y’ || ch==‘y’);

void gen_rate(struct node *q,int num)

if(q==NULL)

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

p->data=num;

p->next=NULL;
 }

else

while(q->next!=NULL)

q=q->next;

q->next=(struct node *)malloc(sizeof(struct

node));

q->next->data=num;

q->next->next=NULL;

void addatstart( struct node *q, int num)

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

p->data=num;

p->next=q;

void append( struct node *q,int num, int c)

struct node *tmp;

int i;

for(i=0;i<c-2;i++)

q=q->next;
 if(q==NULL)

printf(“There are less than %d elements\n”,c);

return;

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

tmp->next=q->next;

tmp->data=num;

q->next=tmp;

void erase( struct node *q, int num)

struct node *t;

if(q->data==num)

p=q->next;

free(q);

return;

while(q->next->next!=NULL)

if(q->next->data==num)

{
 t=q->next;

q->next=q->next->next;

free(t);

return;

q=q->next;

if(q->next->data==num)

free(q->next);

p->next=NULL;

return;

printf(“element %d not fount\n”,num);

void show( struct node *q)

printf(“Your list is :\n”);

while(q!=NULL)

printf(“%d\t”,q->data);

q=q->next;

}
 printf(“\n”);

void count ( struct node *q)

int c=0;

while (q!=NULL)

q=q->next;

c++;

printf(“\n Number of element are %d\n”, c);

void descending( struct node *x)

struct node *q,*r,*s;

q=x;

r=NULL;

while(q!=NULL)

s=r;

r=q;

q=q->next;

r->next=s;

}
 p=r;

show(p);

OUTPUT:

1 Generate

2 Add at starting

3 Append

4 Delete

5 Show

6 Count

7 Descending

Enter your choice : 1

How many node you want : 4

enter the element : 1

enter the element : 5

enter the element : 4

enter the element : 7

Your list is :

1 5 4 7

Do u want to continue (Y/N) N

Explanation:

In the above program, a self-referential structure node is

declared with member variables int data and integer
pointer next. A menu appears with seven options on the screen.
The menu options are given as per given in the output. Different
functions are defined to perform the tasks given in the menu.
The gen_rate() function is used to create a linked list. When
the user enters the number of nodes, the for loop in the first
case structure is executed and at each iteration a number is
entered by the user. The entered number and pointer ‘p’ are
passed to function ger_rate(). If the pointer ‘p’ contains NULL,
the malloc() function allocates memory to pointer ‘p’. The
number entered is assigned to data part of the structure
and NULL value is assigned to the address part. If the
pointer ‘p’ contains value other than NULL, in such a case
the while loop transverses the entire list and the number is
added at the end of the list. The show() function displays the
total elements of the linked list.

The function addatstart() adds the entered elements at the

beginning of the linked list. In this function,
the malloc() function allocates the memory to pointer ‘p’. The
entered number is assigned to variable and the pointer
variable next is initialized with the address of the next node.

The function append() adds the elements at given position in the

linked list. The for loop is executed till the pointer ‘q’ is not
equal to the position number. When the element number is found
the entered number is inserted using tmpstructure variable.

The function erase() is used to delete the given number from

the linked list. In this function, the entered number is checked in
the entire list. When the number occurs, the free() function
releases the memory of that node.

The function count() counts the total numbers present in the

linked list; the function descending() displays the elements in
reverse order and the function show() displays the number.
These functions are self-explanatory.