UNIT - I

Introduction to Data Structures, abstract data types, Linear list – singly linked list
implementation, insertion, deletion and searching operations on linear list, Stacks-
Operations, array and linked representations of stacks, stack applications, Queues-
operations, array and linked representations.

Data Structure

Introduction

Data Structure can be defined as the group of data elements which provides an efficient way of
storing and organizing data in the computer so that it can be used efficiently. Some examples of
Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in
almost every aspect of Computer Science i.e. Operating System, Compiler Design, Artificial
intelligence, Graphics and many more.

Data Structures are the main part of many computer science algorithms as they enable the
programmers to handle the data in an efficient way. It plays a vital role in enhancing the
performance of a software or a program as the main function of the software is to store and
retrieve the user's data as fast as possible.

Basic Terminology

Data structures are the building blocks of any program or the software. Choosing the appropriate
data structure for a program is the most difficult task for a programmer. Following terminology
is used as far as data structures are concerned.

Data: Data can be defined as an elementary value or the collection of values, for example,
student's name and its id are the data about the student.

Group Items: Data items which have subordinate data items are called Group item, for example,
name of a student can have first name and the last name.

Record: Record can be defined as the collection of various data items, for example, if we talk
about the student entity, then its name, address, course and marks can be grouped together to
form the record for the student.

File: A File is a collection of various records of one type of entity, for example, if there are 60
employees in the class, then there will be 20 records in the related file where each record
contains the data about each employee.

3 1
Attribute and Entity: An entity represents the class of certain objects. it contains various
attributes. Each attribute represents the particular property of that entity.

Field: Field is a single elementary unit of information representing the attribute of an entity.

Need of Data Structures

As applications are getting complex and amount of data is increasing day by day, there may arise
the following problems:

Processor speed: To handle very large amount of data, high speed processing is required, but as
the data is growing day by day to the billions of files per entity, processor may fail to deal with
that much amount of data.

Data Search: Consider an inventory size of 106 items in a store, If our application needs to
search for a particular item, it needs to traverse 106 items every time, results in slowing down the
search process.

Multiple requests: If thousands of users are searching the data simultaneously on a web server,
then there are the chances that a very large server can be failed during that process
in order to solve the above problems, data structures are used. Data is organized to form a data
structure in such a way that all items are not required to be searched and required data can be
searched instantly.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures. For example:
suppose, we have some data and we need to perform the search for a particular record. In that
case, if we organize our data in an array, we will have to search sequentially element by element.
hence, using array may not be very efficient here. There are better data structures which can
make the search process efficient like ordered array, binary search tree or hash tables.

Reusability: Data structures are reusable, i.e. once we have implemented a particular data
structure, we can use it at any other place. Implementation of data structures can be compiled
into libraries which can be used by different clients.

Abstraction: Data structure is specified by the ADT which provides a level of abstraction. The
client program uses the data structure through interface only, without getting into the
implementation details.

3 1
Data Structure Classification

Linear Data Structures: A data structure is called linear if all of its elements are arranged in the
linear order. In linear data structures, the elements are stored in non-hierarchical way where each
element has the successors and predecessors except the first and last element.

Linear Data Structures

If a data structure organizes the data in sequential order, then that data structure is called
a Linear DataStructure.
Example
1. Arrays
2. List (Linked List)
3. Stack
4. Queue

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data item is called an
element of the array. The data type of the element may be any valid data type like char, int, float
or double.
The elements of array share the same variable name but each one carries a different index
number known as subscript. The array can be one dimensional, two dimensional or
multidimensional.
The individual elements of the array age are:
age[0], age[1], age[2], age[3],......... age[98], age[99].
Linked List: Linked list is a linear data structure which is used to maintain a list in the memory.
It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node
of the list contains a pointer to its adjacent node.

3 1
Stack: Stack is a linear list in which insertion and deletions are allowed only at one end,
called top.
A stack is an abstract data type (ADT), can be implemented in most of the programming
languages. It is named as stack because it behaves like a real-world stack, for example: - piles of
plates or deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted only at one end called rear and
deleted only at the other end called front.
It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows
First-In-First-Out (FIFO) methodology for storing the data items.

Non Linear Data Structures:

This data structure does not form a sequence i.e. each item or element is connected with two or
more other items in a non-linear arrangement. The data elements are not arranged in sequential
structure.

Non - Linear Data Structures

If a data structure organizes the data in random order, then that data structure is called as
Non-Linear Data Structure.
Example
1. Tree
2. Graph
3. Dictionaries
4. Heaps
5. Tries, Etc.,
Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical relationship among its elements
known as nodes. The bottommost nodes in the herierchy are called leaf node while the topmost
node is called root node. Each node contains pointers to point adjacent nodes.
Tree data structure is based on the parent-child relationship among the nodes. Each node in the
tree can have more than one children except the leaf nodes whereas each node can have atmost
one parent except the root node. Trees can be classfied into many categories which will be
discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented
by vertices) connected by the links known as edges. A graph is different from tree in the sense
that a graph can have cycle while the tree can not have the one.

3 1
Operations on data structure

1) Traversing: Every data structure contains the set of data elements. Traversing the data
structure means visiting each element of the data structure in order to perform some specific
operation like searching or sorting.

Example: If we need to calculate the average of the marks obtained by a student in 6 different
subject, we need to traverse the complete array of marks and calculate the total sum, then we will
devide that sum by the number of subjects i.e. 6, in order to find the average.

2) Insertion: Insertion can be defined as the process of adding the elements to the data structure
at any location.
If the size of data structure is n then we can only insert n-1 data elements into it.

3) Deletion:The process of removing an element from the data structure is called Deletion. We
can delete an element from the data structure at any random location.
If we try to delete an element from an empty data structure then underflow occurs.

4) Searching: The process of finding the location of an element within the data structure is
called Searching. There are two algorithms to perform searching, Linear Search and Binary
Search. We will discuss each one of them later in this tutorial.

5) Sorting: The process of arranging the data structure in a specific order is known as Sorting.
There are many algorithms that can be used to perform sorting, for example, insertion sort,
selection sort, bubble sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of similar type of
elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is
called merging

Abstract Data Type:

An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the
data and the operations that are allowed without regard to how they will be implemented. This
means that we are concerned only with what data is representing and not with how it will
eventually be constructed. By providing this level of abstraction, we are creating an
encapsulation around the data. The idea is that by encapsulating the details of the
implementation, we are hiding them from the user’s view. This is called information hiding. The
implementation of an abstract data type, often referred to as a data structure, will require that we
provide a physical view of the data using some collection of programming constructs and
primitive data types.

3 1
Stack
A Stack is linear data structure. A stack is a list of elements in which an element may be inserted or deleted
only at one end, called the top of the stack. Stack principle is LIFO (last in, first out). Which element
inserted last on to the stack that element deleted first from the stack.

As the items can be added or removed only from the top i.e. the last item to be added to a stack is the first
item to be removed.

Real life examples of stacks are:

Operations on stack:

The two basic operations associated with stacks are:

1. Push
2. Pop

While performing push and pop operations the following test must be conducted on the stack.
a) Stack is empty or not b) stack is full or not

1. Push: Push operation is used to add new elements in to the stack. At the time of addition first check
the stack is full or not. If the stack is full it generates an error message "stack overflow".

2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first check the
stack is empty or not. If the stack is empty it generates an error message "stack underflow".

All insertions and deletions take place at the same end, so the last element added to the stack will be the
first element removed from the stack. When a stack is created, the stack base remains fixed while the stack
top changes as elements are added and removed. The most accessible element is the top and the least
accessible element is the bottom of the stack.

3 1
Representation of Stack (or) Implementation of stack:
The stack should be represented in two ways:
1. Stack using array
2. Stack using linked list

1. Stack using array:

Let us consider a stack with 6 elements capacity. This is called as the size of the stack. The number of
elements to be added should not exceed the maximum size of the stack. If we attempt to add new element
beyond the maximum size, we will encounter a stack overflow condition. Similarly, you cannot remove
elements beyond the base of the stack. If such is the case, we will reach a stack underflow condition.

1.push():When an element is added to a stack, the operation is performed by push(). Below Figure
shows the creation of a stack and addition of elements using push().

Initially top=-1, we can insert an element in to the stack, increment the top value i.e top=top+1. We can
insert an element in to the stack first check the condition is stack is full or not. i.e top>=size-1. Otherwise
add the element in to the stack.

Algorithm: Procedure for push():

Step 1: START
Step 2: if top>=size-1 then
Write “ Stack is Overflow”
Step 3: Otherwise
3.1: read data value ‘x’
3.2: top=top+1;
3.3: stack[top]=x;
Step 4: END

3 1
2.Pop(): When an element is taken off from the stack, the operation is performed by pop(). Below

figure shows a stack initially with three elements and shows the deletion of elements using pop().

We can insert an element from the stack, decrement the top value i.e top=top-1.
We can delete an element from the stack first check the condition is stack is empty or not.
i.e top==-1. Otherwise remove the element from the stack.
Algorithm: procedure pop():
Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “deleted element”
3.2: top=top-1;
Step 4: END

3.display(): This operation performed display the elements in the stack. We display the element in the
stack check the condition is stack is empty or not i.e top==-1.Otherwise display the list of elements in
the stack.

Algorithm: procedure pop():

Step 1: START
Step 2: if top==-1 then
Write “Stack is Underflow”
Step 3: otherwise
3.1: print “Display elements are”
3.2: for top to 0
Print ‘stack[i]’
Step 4: END

3 1
Stack Implementation Using Arrays
#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void display();
void main ()
{

printf("Enter the number of elements in the stack ");

scanf("%d",&n);
printf("*********Stack operations using array\n*********");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}

3 1
}
void push ()
{
int val;
if (top == n )
printf("\n Stack Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}
void pop ()
{
if(top == -1)
printf("Stack Underflow");
else
top = top -1;
}
void display()
{
if(top == -1)
{
printf("Stack is empty");
}
printf("stack elements are\n ")
for (i=top;i>=0;i--)
{
printf(" %d ",stack[i]);
}

OUTPUT:
Enter the number of elements in the stack 5
*********Stack operations using array*********
----------------------------------------------
Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
5

3 1
Please Enter valid choice Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
1
Enter the value?12
Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
3
stack elements are
12
Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
1
Enter the value?12
Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
3
stack elements are
12
12
Chose one from the below options...
1.Push
2.Pop
3.Show
4.Exit
Enter your choice
4
Exiting....

3 1
[Type text]

Applications of STACK:

Application of Stack :

• Recursive Function.
• Expression Evaluation.
• Expression Conversion.
➢ Infix to postfix
➢ Infix to prefix
➢ Postfix to infix
➢ Postfix to prefix
➢ Prefix to infix
➢ Prefix to postfix
• Reverse a Data
• Processing Function Calls

Expressions:

• An expression is a collection of operators and operands that represents a specific value.

• Operator is a symbol which performs a particular task like arithmetic operation or logical
operation or conditional operation etc.,

• Operands are the values on which the operators can perform the task. Here operand can
be a direct value or variable or address of memory location

Expression types:

Based on the operator position, expressions are divided into THREE types. They are as follows.

• Infix Expression

• In infix expression, operator is used in between operands.

• Syntax : operand1 operator operand2

• Example

• Postfix Expression

3 1
[Type text]

• In postfix expression, operator is used after operands. We can say that "Operator
follows the Operands".

• Syntax : operand1 operand2 operator

• Example:

• Prefix Expression

• In prefix expression, operator is used before operands. We can say that "Operands
follows the Operator".

• Syntax : operator operand1 operand2

• Example:

Infix to postfix conversion using stack:

• Procedure to convert from infix expression to postfix expression is as follows:

• Scan the infix expression from left to right.

• If the scanned symbol is left parenthesis, push it onto the stack.

• If the scanned symbol is an operand, then place directly in the postfix expression
(output).

• If the symbol scanned is a right parenthesis, then go on popping all the items from the
stack and place them in the postfix expression till we get the matching left parenthesis.

• If the scanned symbol is an operator, then go on removing all the operators from the stack
and place them in the postfix expression, if and only if the precedence of the operator
which is on the top of the stack is greater than (or greater than or equal) to the precedence
of the scanned operator and push the scanned operator onto the stack otherwise, push the
scanned operator onto the stack.

Example-1

3 1
[Type text]

3 1
[Type text]

Example2:
Convert ((A – (B + C)) * D) ↑ (E + F) infix expression to postfix form:

SYMBOL POSTFIX STRING STACK REMARKS

( (
( ((
A A ((
- A ((-
( A ((-(
B AB ((-(
+ AB ((-(+
C ABC ((-(+
) ABC+ ((-
) ABC+- (
* ABC+- (*
D ABC+-D (*
) ABC+-D*
↑ ABC+-D* ↑
( ABC+-D* ↑(
E ABC+-D*E ↑(
+ ABC+-D*E ↑(+
F ABC+-D*EF ↑(+
) ABC+-D*EF+ ↑
End of The input is now empty. Pop the output symbols
string ABC+-D*EF+↑ from the stack until it is empty.

Example3
Convert a + b * c + (d * e + f) * g the infix expression into postfix form.
SYMBOL POSTFIX STRING STACK REMARKS
a a
+ a +
b ab +
* ab +*
c abc +*
+ abc*+ +

3 1
[Type text]

( abc*+ +(
d abc*+d +(
* abc*+d +(*
e abc*+de +(*
+ abc*+de* +(+
f abc*+de*f +(+
) abc*+de*f+ +
* abc*+de*f+ +*
g abc*+de*f+g +*
End of The input is now empty. Pop the output symbols
abc*+de*f+g*+
string from the stack until it is empty.

Example 3:

Convert the following infix expression A + B * C – D / E * H into its equivalent postfix

expression.

SYMBOL POSTFIX STRING STACK REMARKS

A A
+ A +
B AB +
* AB +*
C ABC +*
- ABC*+ -
D ABC*+D -
/ ABC*+D -/
E ABC*+DE -/
* ABC*+DE/ -*
H ABC*+DE/H -*
End of The input is now empty. Pop the output symbols
string ABC*+DE/H*- from the stack until it is empty.

Example 4:

Convert the following infix expression A+(B *C–(D/E↑F)*G)*H into its equivalent postfix expression.

3 1
[Type text]

SYMBOL POSTFIX STRING STACK REMARKS

A A

+ A +

( A +(

B AB +(

* AB +(*

C ABC +(*

- ABC* +(-

( ABC* +(-(

D ABC*D +(-(

/ ABC*D +(-(/

E ABC*DE +(-(/

↑ ABC*DE +(-(/↑

F ABC*DEF +(-(/↑

) ABC*DEF↑/ +(-

* ABC*DEF↑/ +(-*

G ABC*DEF↑/G +(-*

) ABC*DEF↑/G*- +

* ABC*DEF↑/G*- +*

H ABC*DEF↑/G*-H +*

End of The input is now empty. Pop the output symbols

ABC*DEF↑/G*-H*+
string from the stack until it is empty.

3 1
[Type text]

Evaluation of postfix expression:

• The postfix expression is evaluated easily by the use of a stack.

• When a number is seen, it is pushed onto the stack;
• when an operator is seen, the operator is applied to the two numbers that are popped from
the stack and the result is pushed onto the stack.
• When an expression is given in postfix notation, there is no need to know any
precedence rules.
Example 1:
Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *
OPERAND
SYMBOL OPERAND 2 VALUE STACK REMARKS
1

6 6

5 6, 5

2 6, 5, 2

The first four symbols are placed

3 6, 5, 2, 3
on the stack.

Next a ‘+’ is read, so 3 and 2 are

+ 2 3 5 6, 5, 5 popped from the stack and their
sum 5, is pushed

8 2 3 5 6, 5, 5, 8 Next 8 is pushed

Now a ‘*’ is seen, so 8 and 5 are

* 5 8 40 6, 5, 40
popped as 8 * 5 = 40 is pushed

Next, a ‘+’ is seen, so 40 and 5 are

+ 5 40 45 6, 45
popped and 40 + 5 = 45 is pushed

3 5 40 45 6, 45, 3 Now, 3 is pushed

Next, ‘+’ pops 3 and 45 and

+ 45 3 48 6, 48
pushes 45 + 3 = 48 is pushed

Finally, a ‘*’ is seen and 48 and 6

* 6 48 288 288 are popped, the result 6 * 48 =
288 is pushed

3 1
[Type text]

Example2

3 1
[Type text]

Example 3:

Evaluate the following postfix expression: 6 2 3 + - 3 8 2 / + * 2 ↑ 3 +

SYMBOL OPERAND 1 OPERAND 2 VALUE STACK

6 6

2 6, 2

3 6, 2, 3

+ 2 3 5 6, 5

- 6 5 1 1

3 6 5 1 1, 3

8 6 5 1 1, 3, 8

2 6 5 1 1, 3, 8, 2

/ 8 2 4 1, 3, 4

+ 3 4 7 1, 7

* 1 7 7 7

2 1 7 7 7, 2

↑ 7 2 49 49

3 7 2 49 49, 3

+ 49 3 52 52

Reverse a Data:
To reverse a given set of data, we need to reorder the data so that the first and last elements are
exchanged, the second and second last element are exchanged, and so on for all other elements.

Example: Suppose we have a string Welcome, then on reversing it would be Emoclew.

There are different reversing applications:

3 1
[Type text]

o Reversing a string

o Converting Decimal to Binary

Reverse a String

A Stack can be used to reverse the characters of a string. This can be achieved by simply pushing
one by one each character onto the Stack, which later can be popped from the Stack one by one.
Because of the last in first out property of the Stack, the first character of the Stack is on the
bottom of the Stack and the last character of the String is on the Top of the Stack and after
performing the pop operation in the Stack, the Stack returns the String in Reverse order.

Processing Function Calls:

Stack plays an important role in programs that call several functions in succession. Suppose we
have a program containing three functions: A, B, and C. function A invokes function B, which
invokes the function C.

3 1
[Type text]

When we invoke function A, which contains a call to function B, then its processing will not be
completed until function B has completed its execution and returned. Similarly for function B
and C. So we observe that function A will only be completed after function B is completed and
function B will only be completed after function C is completed. Therefore, function A is first to
be started and last to be completed. To conclude, the above function activity matches the last in
first out behavior and can easily be handled using Stack.

Consider addrA, addrB, addrC be the addresses of the statements to which control is returned
after completing the function A, B, and C, respectively.

The above figure shows that return addresses appear in the Stack in the reverse order in which
the functions were called. After each function is completed, the pop operation is performed, and
execution continues at the address removed from the Stack. Thus the program that calls several
functions in succession can be handled optimally by the stack data structure. Control returns to
each function at a correct place, which is the reverse order of the calling sequence.

3 1
QUEUE

A queue is linear data structure and collection of elements. A queue is another special kind of list, where
items are inserted at one end called the rear and deleted at the other end called the front. The principle of
queue is a “FIFO” or “First-in-first-out”.

Queue is an abstract data structure. A queue is a useful data structure in programming. It is similar to the
ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the
ticket.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first.

More real-world examples can be seen as queues at the ticket windows and bus-stops and our college
library.

The operations for a queue are analogues to those for a stack; the difference is that the insertions go at the
end of the list, rather than the beginning.

Operations on QUEUE:
A queue is an object or more specifically an abstract data structure (ADT) that allows the following
operations:
• Enqueue or insertion: which inserts an element at the end of the queue.
• Dequeue or deletion: which deletes an element at the start of the queue.

Representation of Queue (or) Implementation of Queue:

The queue can be represented in two ways:
1. Queue using Array
2. Queue using Linked List
1.Queue using Array:
Let us consider a queue, which can hold maximum of five elements. Initially the queue is empty.
Now, insert 11 to the queue. Then queue status will be:

3 1
Next, insert 22 to the queue. Then the queue status is:

Again insert another element 33 to the queue. The status of the queue is:

Now, delete an element. The element deleted is the element at the front of the queue.So the status of
the queue is:

Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So,
22 is deleted. The queue status is as follows:

Now, insert new elements 44 and 55 into the queue. The queue status is:

3 1
Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the
rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The
queue status is as follows:

Now it is not possible to insert an element 66 even though there are two vacant positions in
the linear queue. To overcome this problem the elements of the queue are to be shifted
towards the beginning of the queue so that it creates vacant position at the rear end. Then
the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the
rear end. After this operation, the queue status is as follows:

This difficulty can overcome if we treat queue position with index 0 as a position that comes
after position with index 4 i.e., we treat the queue as a circular queue.

Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error

If the item is to be inserted as the first element in the list, in that case set the value of front and
rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear as
the index.

3 1
Algorithm to delete an element from the queue
If, the value of front is -1 or value of front is greater than rear , write an underflow message and
exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the
queue at each time.

display() - Displays the elements of a Queue

We can use the following steps to display the elements of a queue...

• Step 1 - Check whether queue is EMPTY.

• Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
• Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
• Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value reaches to rear (i <= rear)

Queue Implementation using Arrays

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{

3 1
printf("\n*************************Main
Menu*****************************\n");

printf("\n==============================================================
===\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}

3 1
queue[rear] = item;
printf("\nValue inserted ");

}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;

}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}

void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
}

3 1
Drawback of array implementation of Queue
Although, the technique of creating a queue is easy, but there are some drawbacks of using this
technique to implement a queue.
o Memory wastage : The space of the array, which is used to store queue elements, can
never be reused to store the elements of that queue because the elements can only be
inserted at front end and the value of front might be so high so that, all the space before
that, can never be filled.

The above figure shows how the memory space is wasted in the array representation of queue. In
the above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable
is 5, therefore, we can not reinsert the values in the place of already deleted element before the
position of front. That much space of the array is wasted and can not be used in the future (for
this queue).
o Deciding the array size

One of the most common problem with array implementation is the size of the array which
requires to be declared in advance. Due to the fact that, the queue can be extended at runtime
depending upon the problem, the extension in the array size is a time taking process and almost
impossible to be performed at runtime since a lot of reallocations take place. Due to this reason,
we can declare the array large enough so that we can store queue elements as enough as possible
but the main problem with this declaration is that, most of the array slots (nearly half) can never
be reused. It will again lead to memory wastage.

Types of Queues

There are four types of Queues:

1. Linear Queue
2. Circular Queue
3. Priority Queue
4. Deque

3 1
1. Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as front end. It strictly follows the FIFO rule. The linear Queue can
be represented, as shown in the below
figure:

The above figure shows that the elements are inserted from the rear end, and if we insert more
elements in a Queue, then the rear value gets incremented on every insertion. If we want to show
the deletion, then it can be represented as:

In the above figure, we can observe that the front pointer points to the next element, and the
element which was previously pointed by the front pointer was deleted.
The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even though
the space is available in a Linear Queue. In this case, the linear Queue shows
the overflow condition as the rear is pointing to the last element of the Queue.

3 1
2. Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known
as Ring Buffer as all the ends are connected to another end. The circular queue can be
represented as:

he drawback that occurs in a linear queue is overcome by using the circular queue. If the empty
space is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear.

3. Priority Queue

A priority queue is another special type of Queue data structure in which each element has some
priority associated with it. Based on the priority of the element, the elements are arranged in a
priority queue. If the elements occur with the same priority, then they are served according to the
FIFO principle.
In priority Queue, the insertion takes place based on the arrival while the deletion occurs based
on the priority. The priority Queue can be shown as:
The above figure shows that the highest priority element comes first and the elements of the
same priority are arranged based on FIFO structure.

4. Deque

Both the Linear Queue and Deque are different as the linear queue follows the FIFO principle
whereas, deque does not follow the FIFO principle. In Deque, the insertion and deletion can occur
from both ends.

3 1
Linked List
o Linked List can be defined as collection of objects called nodes that are randomly stored
in the memory.
o A node contains two fields i.e. data stored at that particular address and the pointer which
contains the address of the next node in the memory.
o The last node of the list contains pointer to the null

Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node can’t be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements that are to be
stored individually in the memory. However, Array has several advantages and disadvantages
which must be known in order to decide the data structure which will be used throughout the
program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the
size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any
element in the array needs shifting of all its predecessors.

3 1
Linked list is the data structure which can overcome all the limitations of an array. Using linked
list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available memory
space.

Differences between the array and linked list in a tabular form.

ARRAYS LINKED LISTS

An array is a collection of elements of a A linked list is a collection of objects known as
similar data type. a node where node consists of two parts, i.e.,
data and address
Array elements store in a contiguous memory Linked list elements can be stored anywhere in
location the memory or randomly stored
Array works with a static memory. Here static The Linked list works with dynamic memory.
memory means that the memory size is fixed Here, dynamic memory means that the memory
and cannot be changed at the run time. size can be changed at the run time according to
our requirements.
Array elements are independent of each other. Linked list elements are dependent on each
other. As each node contains the address of the
next node so to access the next node, we need
to access its previous node.
Array takes more time while performing any Linked list elements are dependent on each
operation like insertion, deletion, etc. other. As each node contains the address of the
next node so to access the next node, we need
to access its previous node.
Accessing any element in an array is faster as Accessing an element in a linked list is slower
the element in an array can be directly as it starts traversing from the first element of
accessed through the index the linked list.
In the case of an array, memory is allocated at In the case of a linked list, memory is allocated
compile-time at run time
Memory utilization is inefficient in the array. Memory utilization is efficient in the case of a
For example, if the size of the array is 6, and linked list as the memory can be allocated or
array consists of 3 elements only then the rest deallocated at the run time according to our
of the space will be unused. requirement

3 1
Types of Linked List

The following are the types of linked list:

1. Singly linked list

2. Doubly linked list
3. Circular linked list

Singly Linked list

It is the commonly used linked list in programs. If we are talking about the linked list, it means it
is a singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is
the data part, and the other one is the address part, which contains the address of the next or the
successor node. The address part in a node is also known as a pointer.
Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:

We can observe in the above figure that there are three different nodes having address 100, 200
and 300 respectively. The first node contains the address of the next node, i.e., 200, the second
node contains the address of the last node, i.e., 300, and the third node contains the NULL value
in its address part as it does not point to any node. The pointer that holds the address of the initial
node is known as a head pointer.
The linked list, which is shown in the above diagram, is known as a singly linked list as it
contains only a single link. In this list, only forward traversal is possible; we cannot traverse in
the backward direction as it has only one link in the list.
Representation of the node in a singly linked list
struct node

{
int data;
struct node *next;
}

3 1
In the above representation, we have defined a user-defined structure named a node containing
two members, the first one is data of integer type, and the other one is the pointer (next) of the
node type.

Doubly linked list

As the name suggests, the doubly linked list contains two pointers. We can define the doubly
linked list as a linear data structure with three parts: the data part and the other two address part.
In other words, a doubly linked list is a list that has three parts in a single node, includes one data
part, a pointer to its previous node, and a pointer to the next node.
Suppose we have three nodes, and the address of these nodes are 100, 200 and 300, respectively.
The representation of these nodes in a doubly-linked list is shown below

As we can observe in the above figure, the node in a doubly-linked list has two address parts;
one part stores the address of the next while the other part of the node stores the previous node's
address. The initial node in the doubly linked list has the NULL value in the address part, which
provides the address of the previous node.

Representation of the node in a doubly linked list

struct node
{
int data;
struct node *next;
struct node *prev;
}
In the above representation, we have defined a user-defined structure named a node with three
members, one is data of integer type, and the other two are the pointers, i.e., next and prev of
the node type. The next pointer variable holds the address of the next node, and the prev
pointer holds the address of the previous node. The type of both the pointers, i.e., next and
prev is struct node as both the pointers are storing the address of the node of the struct
node type.

3 1
Circular linked list

A circular linked list is a variation of a singly linked list. The only difference between the singly
linked list and a circular linked list is that the last node does not point to any node in a singly
linked list, so its link part contains a NULL value. On the other hand, the circular linked list is a
list in which the last node connects to the first node, so the link part of the last node holds the
first node's address. The circular linked list has no starting and ending node. We can traverse in
any direction, i.e., either backward or forward. The diagrammatic representation of the circular
linked list is shown below:

struct node
{
int data;
struct node *next;
}
A circular linked list is a sequence of elements in which each node has a link to the next node,
and the last node is having a link to the first node. The representation of the circular linked list
will be similar to the singly linked list, as shown below:

Singly linked list

Singly linked list can be defined as the collection of ordered set of elements. The number of
elements may vary according to need of the program. A node in the singly linked list consist of
two parts: data part and link part. Data part of the node stores actual information that is to be
represented by the node while the link part of the node stores the address of its immediate
successor.

One way chain or singly linked list can be traversed only in one direction. In other words, we can
say that each node contains only next pointer, therefore we can not traverse the list in the reverse
direction.

Consider an example where the marks obtained by the student in three subjects are stored in a
linked list as shown in the figure.

3 1
In the above figure, the arrow represents the links. The data part of every node contains the
marks obtained by the student in the different subject. The last node in the list is identified by the
null pointer which is present in the address part of the last node. We can have as many elements
we require, in the data part of the list.

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such
operations is given below.

Node Creation

struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
Insertion
The insertion into a singly linked list can be performed at different positions. Based on the
position of the new node being inserted, the insertion is categorized into the following categories.
1. Inserting at Beginning
2. Inserting at the End of the LIst
3. Inserting after specified node

Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to
make a few adjustments in the node links. There are the following steps which need to be
followed in order to inser a new node in the list at beginning.
1. Allocate the space for the new node and store data into the data part of the node. This will
be done by the following statements.
ptr = (struct node *) malloc(sizeof(struct node *));
ptr → data = item
2. Make the link part of the new node pointing to the existing first node of the list. This will
be done by using the following statement.

ptr->next = head

3 1
3. At the last, we need to make the new node as the first node of the list this will be done by
using the following statement.

head = ptr;

Algorithm
o Step 1: IF PTR = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
o Step 2: SET NEW_NODE = PTR
o Step 3: SET PTR = PTR → NEXT
o Step 4: SET NEW_NODE → DATA = VAL
o Step 5: SET NEW_NODE → NEXT = HEAD
o Step 6: SET HEAD = NEW_NODE
o Step 7: EXIT
Function for inserting element at beginning of the list
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\n memory insufficient to allocate");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head; head = ptr;

3 1
printf("\nNode inserted");
}
}

2.Inserting at the End of the List

In order to insert a node at the last, there are two following scenarios which need to be
mentioned.
1. The node is being added to an empty list(CASE 1)
2. The node is being added to the end of the linked list(CASE2)
in the first case,(CASE1)
o The condition (head == NULL) gets satisfied. Hence, we just need to allocate the space
for the node by using malloc statement in C. Data and the link part of the node are set up
by using the following statements.
ptr->data = item;
ptr -> next = NULL;
o Since, ptr is the only node that will be inserted in the list hence, we need to make this
node pointed by the head pointer of the list. This will be done by using the following
Statements.
Head = ptr
In the second case: CASE(2):
o The condition Head = NULL would fail, since Head is not null. Now, we need to declare
a temporary pointer temp in order to traverse through the list. temp is made to point the
first node of the list.
Temp = head
o Then, traverse through the entire linked list using the statements:
while (temp→ next != NULL)
temp = temp → next;
o At the end of the loop, the temp will be pointing to the last node of the list. Now, allocate
the space for the new node, and assign the item to its data part. Since, the new node is
going to be the last node of the list hence, the next part of this node needs to be pointing
to the null. We need to make the next part o
o If the temp node (which is currently the last node of the list) point to the new node (ptr)
.temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;

3 1
Algorithm
Step 1: IF PTR = NULL Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET NEW_NODE = PTR
Step 3: SET PTR = PTR - > NEXT
Step 4: SET NEW_NODE - > DATA = VAL
Step 5: SET NEW_NODE - > NEXT = NULL
Step 6: SET PTR = HEAD
Step 7: Repeat Step 8 while PTR - > NEXT != NULL
Step 8: SET PTR = PTR - > NEXT
[END OF LOOP]
Step 9: SET PTR - > NEXT = NEW_NODE
Step 10: EXIT
Function for inserting element at the end of the list

void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n"); scanf("%d",&item);
ptr->data = item;
if(head == NULL)

3 1
3 1
Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the
rear crossed the maximum size of the queue (i.e., 5). There will be queue full signal. The
queue status is as follows:

Now it is not possible to insert an element 66 even though there are two vacant positions in
the linear queue. To overcome this problem the elements of the queue are to be shifted
towards the beginning of the queue so that it creates vacant position at the rear end. Then
the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the
rear end. After this operation, the queue status is as follows:

This difficulty can overcome if we treat queue position with index 0 as a position that comes
after position with index 4 i.e., we treat the queue as a circular queue.

Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error

If the item is to be inserted as the first element in the list, in that case set the value of front and
rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear as
the index.

3 1
Algorithm to delete an element from the queue
If, the value of front is -1 or value of front is greater than rear , write an underflow message and
exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the
queue at each time.

3 1
display() - Displays the elements of a Queue
We can use the following steps to display the elements of a queue...

• Step 1 - Check whether queue is EMPTY.

• Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
• Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
• Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same
until 'i' value reaches to rear (i <= rear)

Queue Implementation using Arrays

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{

3 1
printf("\n*************************Main
Menu*****************************\n");

printf("\n==============================================================
===\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{ 3 1
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}

3 1
queue[rear] = item;
printf("\nValue inserted ");

}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;

}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}

void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
}
}
3 1
}
Drawback of array implementation of Queue
Although, the technique of creating a queue is easy, but there are some drawbacks of using this
technique to implement a queue.
o Memory wastage : The space of 3 the 1array, which is used to store queue elements, can
never be reused to store the elements of that queue because the elements can only be
inserted at front end and the value of front might be so high so that, all the space before
that, can never be filled.

The above figure shows how the memory space is wasted in the array representation of queue. In
the above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable
is 5, therefore, we can not reinsert the values in the place of already deleted element before the
position of front. That much space of the array is wasted and can not be used in the future (for
this queue).
o Deciding the array size

One of the most common problem with array implementation is the size of the array which
requires to be declared in advance. Due to the fact that, the queue can be extended at runtime
depending upon the problem, the extension in the array size is a time taking process and almost
impossible to be performed at runtime since a lot of reallocations take place. Due to this reason,
we can declare the array large enough so that we can store queue elements as enough as possible
but the main problem with this declaration is that, most of the array slots (nearly half) can never
be reused. It will again lead to memory wastage.

Types of Queues

There are four types of Queues:

1. Linear Queue
2. Circular Queue
3. Priority Queue
4. Deque

3 1
1. Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which the
deletion takes place is known as front end. It strictly follows the FIFO rule. The linear Queue can
be represented, as shown in the below
figure:

The above figure shows that the elements are inserted from the rear end, and if we insert more
elements in a Queue, then the rear value gets incremented on every insertion. If we want to show
the deletion, then it can be represented as:
3 1
In the above figure, we can observe that the front pointer points to the next element, and the
element which was previously pointed by the front pointer was deleted.
The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even though
the space is available in a Linear Queue. In this case, the linear Queue shows
the overflow condition as the rear is pointing to the last element of the Queue.

3 1
2. Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known
as Ring Buffer as all the ends are connected to another end. The circular queue can be
represented as:

he drawback that occurs in a linear queue is overcome by using the circular queue. If the empty
space is available in a circular queue, the new element can be added in an empty space by simply
incrementing the value of rear.

3. Priority Queue

A priority queue is another special type of Queue data structure in which each element has some
priority associated with it. Based on the priority of the element, the elements are arranged in a
priority queue. If the elements occur with the same priority, then they are served according to the
FIFO principle.
In priority Queue, the insertion takes place based on the arrival while the deletion occurs based
on the priority. The priority Queue can be shown as:
The above figure shows that the highest priority element comes first and the elements of the
same priority are arranged based on FIFO3 structure.
1

4. Deque
4. Deque

Both the Linear Queue and Deque are different as the linear queue follows the FIFO principle
whereas, deque does not follow the FIFO principle. In Deque, the insertion and deletion can occur
from both ends.

3 1
Linked List
o Linked List can be defined as collection of objects called nodes that are randomly stored
in the memory.
o A node contains two fields i.e. data stored at that particular address and the pointer which
contains the address of the next node in the memory.
o The last node of the list contains pointer to the null

Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
o list size is limited to the memory size and doesn't need to be declared in advance.
o Empty node can’t be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements that are to be
stored individually in the memory. However, Array has several advantages and disadvantages
which must be known in order to decide the data structure which will be used throughout the
program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the
size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any
element in the array needs shifting of all its predecessors.

3 1
Linked list is the data structure which can overcome all the limitations of an array. Using linked
list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available memory
space.

Differences between the array and linked list in a tabular form.

3 1
ARRAYS LINKED LISTS
An array is a collection of elements of a A linked list is a collection of objects known as
similar data type. a node where node consists of two parts, i.e.,
data and address
Array elements store in a contiguous memory Linked list elements can be stored anywhere in
location the memory or randomly stored
Array works with a static memory. Here static The Linked list works with dynamic memory.
memory means that the memory size is fixed Here, dynamic memory means that the memory
and cannot be changed at the run time. size can be changed at the run time according to
our requirements.
Array elements are independent of each other. Linked list elements are dependent on each
other. As each node contains the address of the
next node so to access the next node, we need
to access its previous node.
Array takes more time while performing any Linked list elements are dependent on each
operation like insertion, deletion, etc. other. As each node contains the address of the
next node so to access the next node, we need
to access its previous node.
Accessing any element in an array is faster as Accessing an element in a linked list is slower
the element in an array can be directly as it starts traversing from the first element of
accessed through the index the linked list.
In the case of an array, memory is allocated at In the case of a linked list, memory is allocated
compile-time at run time
Memory utilization is inefficient in the array. Memory utilization is efficient in the case of a
For example, if the size of the array is 6, and linked list as the memory can be allocated or
array consists of 3 elements only then the rest deallocated at the run time according to our
of the space will be unused. requirement

3 1
Types of Linked List

The following are the types of linked list:

1. Singly linked list

2. Doubly linked list
3. Circular linked list

Singly Linked list

It is the commonly used linked list in programs. If we are talking about the linked list, it means it
is a singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is
the data part, and the other one is the address part, which contains the address of the next or the
successor node. The address part in a node is also known as a pointer.
Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:

We can observe in the above figure that there are three different nodes having address 100, 200
and 300 respectively. The first node contains the address of the next node, i.e., 200, the second
node contains the address of the last node, i.e., 300, and the third node contains the NULL value
in its address part as it does not point to3any node.
1 The pointer that holds the address of the initial
node is known as a head pointer.
The linked list, which is shown in the above diagram, is known as a singly linked list as it
contains only a single link. In this list, only forward traversal is possible; we cannot traverse in
the backward direction as it has only one link in the list.
Representation of the node in a singly linked list
struct node

{
int data;
struct node *next;
}

3 1
In the above representation, we have defined a user-defined structure named a node containing
two members, the first one is data of integer type, and the other one is the pointer (next) of the
node type.

Doubly linked list

As the name suggests, the doubly linked list contains two pointers. We can define the doubly
linked list as a linear data structure with three parts: the data part and the other two address part.
In other words, a doubly linked list is a list that has three parts in a single node, includes one data
part, a pointer to its previous node, and a pointer to the next node.
Suppose we have three nodes, and the address of these nodes are 100, 200 and 300, respectively.
The representation of these nodes in a doubly-linked list is shown below

As we can observe in the above figure, the node in a doubly-linked list has two address parts;
one part stores the address of the next while the other part of the node stores the previous node's
address. The initial node in the doubly linked list has the NULL value in the address part, which
provides the address of the previous node.

Representation of the node in a doubly linked list

struct node
{
int data;
struct node *next;
struct node *prev;
}
In the above representation, we have defined a user-defined structure named a node with three
members, one is data of integer type, and the other two are the pointers, i.e., next and prev of
the node type. The next pointer variable holds the address of the next node, and the prev
pointer holds the address of the previous node. The type of both the pointers, i.e., next and
prev is struct node as both the pointers are storing the address of the node of the struct
node type.

3 1 4
Circular linked list

A circular linked list is a variation of a singly linked list. The only difference between the singly
linked list and a circular linked list is that the last node does not point to any node in a singly
linked list, so its link part contains a NULL value. On the other hand, the circular linked list is a
list in which the last node connects to the first node, so the link part of the last node holds the
first node's address. The circular linked3list has
1 no starting and ending node. We can traverse in
any direction, i.e., either backward or forward. The diagrammatic representation of the circular
linked list is shown below:
struct node
{
int data;
struct node *next;
}
A circular linked list is a sequence of elements in which each node has a link to the next node,
and the last node is having a link to the first node. The representation of the circular linked list
will be similar to the singly linked list, as shown below:

Singly linked list

Singly linked list can be defined as the collection of ordered set of elements. The number of
elements may vary according to need of the program. A node in the singly linked list consist of
two parts: data part and link part. Data part of the node stores actual information that is to be
represented by the node while the link part of the node stores the address of its immediate
successor.

One way chain or singly linked list can be traversed only in one direction. In other words, we can
say that each node contains only next pointer, therefore we can not traverse the list in the reverse
direction.

Consider an example where the marks obtained by the student in three subjects are stored in a
linked list as shown in the figure.

3 1
In the above figure, the arrow represents the links. The data part of every node contains the
marks obtained by the student in the different subject. The last node in the list is identified by the
null pointer which is present in the address part of the last node. We can have as many elements
we require, in the data part of the list.

Operations on Singly Linked List

There are various operations which can be performed on singly linked list. A list of all such
operations is given below.

Node Creation

struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
3 1
Insertion
The insertion into a singly linked list can be performed at different positions. Based on the
position of the new node being inserted, the insertion is categorized into the following categories.
1. Inserting at Beginning
2. Inserting at the End of the LIst
3. Inserting after specified node

Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to
make a few adjustments in the node links. There are the following steps which need to be
followed in order to inser a new node in the list at beginning.
1. Allocate the space for the new node and store data into the data part of the node. This will
be done by the following statements.
ptr = (struct node *) malloc(sizeof(struct node *));
ptr → data = item
2. Make the link part of the new node pointing to the existing first node of the list. This will
be done by using the following statement.

ptr->next = head

3 1
3. At the last, we need to make the new node as the first node of the list this will be done by
using the following statement.

head = ptr;

Algorithm
o Step 1: IF PTR = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
o Step 2: SET NEW_NODE = PTR
o Step 3: SET PTR = PTR → NEXT
o Step 4: SET NEW_NODE → DATA = VAL
o Step 5: SET NEW_NODE → NEXT = HEAD
o Step 6: SET HEAD = NEW_NODE
o Step 7: EXIT
Function for inserting element at beginning of the list
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\n memory insufficient to allocate");
}
else
{ 3 1
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head; head = ptr;

printf("\nNode inserted"); 3 1
}
}
2.Inserting at the End of the List

In order to insert a node at the last, there are two following scenarios which need to be
mentioned.
1. The node is being added to an empty list(CASE 1)
2. The node is being added to the end of the linked list(CASE2)
in the first case,(CASE1)
o The condition (head == NULL) gets satisfied. Hence, we just need to allocate the space
for the node by using malloc statement in C. Data and the link part of the node are set up
by using the following statements.
ptr->data = item;
ptr -> next = NULL;
o Since, ptr is the only node that will be inserted in the list hence, we need to make this
node pointed by the head pointer of the list. This will be done by using the following
Statements.
Head = ptr
In the second case: CASE(2):
o The condition Head = NULL would fail, since Head is not null. Now, we need to declare
a temporary pointer temp in order to traverse through the list. temp is made to point the
first node of the list.
Temp = head
o Then, traverse through the entire linked list using the statements:
while (temp→ next != NULL)
temp = temp → next;
o At the end of the loop, the temp will be pointing to the last node of the list. Now, allocate
the space for the new node, and assign the item to its data part. Since, the new node is
going to be the last node of the list hence, the next part of this node needs to be pointing
to the null. We need to make the next part o
o If the temp node (which is currently the last node of the list) point to the new node (ptr)
.temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;

3 1
Algorithm
Step 1: IF PTR = NULL Write OVERFLOW
Go to Step 1
[END OF IF] 3 1
Step 2: SET NEW_NODE = PTR
Step 3: SET PTR = PTR - > NEXT
Step 4: SET NEW_NODE - > DATA = VAL
Step 5: SET NEW_NODE - > NEXT = NULL
Step 6: SET PTR = HEAD
Step 7: Repeat Step 8 while PTR - > NEXT != NULL
Step 8: SET PTR = PTR - > NEXT
[END OF LOOP]
Step 9: SET PTR - > NEXT = NEW_NODE
Step 10: EXIT
Function for inserting element at the end of the list

void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n"); scanf("%d",&item);
ptr->data = item;
if(head == NULL)

3 1
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");

}
}
}

Insertion in singly linked list after specified Node

o In order to insert an element after the specified number of nodes into the linked list, we
need to skip the desired number of elements in the list to move the pointer at the position
after which the node will be inserted. This will be done by using the following
statements.
emp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
return;
} 3 1
}
o Allocate the space for the new node and add the item to the data part of it. This will be
o Allocate the space for the new node and add the item to the data part of it. This will be
done by using the following statements.
ptr = (struct node *) malloc (sizeof(struct node));
ptr->data = item;
o Now, we just need to make a few more link adjustments and our node at will be inserted
at the specified position. Since, at the end of the loop, the loop pointer temp would be
pointing to the node after which the new node will be inserted. Therefore, the next part of
the new node ptr must contain the address of the next part of the temp (since, ptr will be

10

3 1
in between temp and the next of the temp). This will be done by using the following
statements.
ptr→ next = temp → next
now, we just need to make the next part of the temp, point to the new node ptr. This will insert
the new node ptr, at the specified position.
temp ->next = ptr;

Algorithm
o STEP 1: IF PTR = NULL
WRITE OVERFLOW
GOTO STEP 12
END OF IF
o STEP 2: SET NEW_NODE = PTR
o STEP 3: NEW_NODE → DATA = VAL
o STEP 4: SET TEMP = HEAD
o STEP 5: SET I = 0
o STEP 6: REPEAT STEP 5 AND 6 UNTIL I<loc< li=""></loc<>
o STEP 7: TEMP = TEMP → NEXT
o STEP 8: IF TEMP = NULL
WRITE "DESIRED NODE NOT PRESENT"
GOTO STEP 12
END OF IF
END OF LOOP
o STEP 9: PTR → NEXT = TEMP → NEXT
o STEP 10: TEMP → NEXT = PTR
o STEP 11: SET PTR = NEW_NODE
o STEP 12: EXIT

C Function
void randominsert()
{
int i,loc,item;

11

3 1
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item); 3 1
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=1;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
Deletion
The Deletion of a node from a singly linked list can be performed at different positions. Based on
the position of the node being deleted, the operation is categorized into the following categories.
1. Deleting at Beginning
2. Deleting at the End of the List
3. Deleting after specified node
Deletion in singly linked list at beginning

Deleting a node from the beginning of the list is the simplest operation of all. It just need a few
adjustments in the node pointers. Since the first node of the list is to be deleted, therefore, we just
need to make the head, point to the next of the head. This will be done by using the following
statements

12

3 1
ptr = head;
head = ptr->next;

Now, free the pointer ptr which was pointing to the head node of the list. This will be done by
using the following statement.
free(ptr)

Algorithm
o Step 1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
o Step 2: SET PTR = HEAD
o Step 3: SET HEAD = HEAD -> NEXT
o Step 4: FREE PTR
o Step 5: EXIT 3 1

C function
void begdelete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\n Node deleted from the begining ...");
}

13

3 1
}
Deletion in singly linked list at the end
Here are two scenarios in which, a node is deleted from the end of the linked list.
1. There is only one node in the list and that needs to be deleted.
2. There are more than one node in the list and the last node of the list will be deleted.

In the first scenario,

the condition head → next = NULL will survive and therefore, the only node head of the
list will be assigned to null. This will be done by using the following statements.
ptr = head
head = NULL
free(ptr)
In the second scenario,
The condition head → next = NULL would fail and therefore, we have to traverse the
node in order to reach the last node of the list.
For this purpose, just declare a temporary pointer temp and assign it to head of the list.
We also need to keep track of the second last node of the list. For this purpose, two
pointers ptr and ptr1 will be used where ptr will point to the last node and ptr1 will point
to the second last node of the list.
this all will be done by using the following statements.
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
Now, we just need to make the pointer ptr1 point to the NULL and the last node of the
list that is pointed by ptr will become free. It will be done by using the following
statements.
ptr1->next = NULL;
free(ptr);

3 1
14

Algorithm
o Step 1: IF HEAD = NULL
Write UNDERFLOW
Go to Step 8 3 1
[END OF IF]
o Step 2: SET PTR HEAD
o Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
o Step 4: SET PREPTR = PTR
o Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
o Step 6: SET PREPTR -> NEXT = NULL
o Step 7: FREE PTR
o Step 8: EXIT

C Function
void end_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\n Deleted Node from the last ...");

15

3 1
}
}
}
Deletion in singly linked list after the specified node
In order to delete the node, which is present after the specified node, we need to skip the desired
number of nodes to reach the node after which the node will be deleted. We need to keep track of
the two nodes. The one which is to be deleted the other one if the node which is present before
that node. For this purpose, two pointers are used: ptr and ptr1.
Use the following statements to do so.
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nThere are less than %d elements in the list..",loc);
3 1
return;
}
}
Now, our task is almost done, we just need to make a few pointer adjustments. Make the next of
ptr1 (points to the specified node) point to the next of ptr (the node which is to be deleted).
This will be done by using the following statements.

Algorithm
o STEP 1: IF HEAD = NULL

WRITE UNDERFLOW
GOTO STEP 10
END OF IF

16

3 1
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nNode Inserted\n");
}

}
void traverse()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");

while(ptr -> next != head)

{

printf("%d\n", ptr -> data);

ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}

3 1