What is Data Structure?

Data Structure is a way to store and organize data so that it can

be used efficiently.

The data structure name indicates itself that organizing the data in
memory. There are many ways of organizing the data in the
memory as we have already seen one of the data structures, i.e.,
array in C language. Array is a collection of memory elements in
which data is stored sequentially, i.e., one after another. In other
words, we can say that array stores the elements in a continuous
manner. This organization of data is done with the help of an array
of data structures. There are also other ways to organize the data
in memory. Let's see the different types of data structures.

The data structure is not any programming language like C, C++,

java, etc. It is a set of algorithms that we can use in any
programming language to structure the data in the memory.

 Linear data structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and
next adjacent elements, is called a linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.

Page
  Static data structure: Static data structure has a fixed memory size. It
is easier to access the elements in a static data structure.
An example of this data structure is an array.
 Dynamic data structure: In dynamic data structure, the size is not fixed.
It can be randomly updated during the runtime which may be considered
efficient concerning the memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.
 Non-linear data structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures. In a non-
linear data structure, we can’t traverse all the elements in a single run only.
Examples of non-linear data structures are trees and graphs.

For example, we can store a list of items having the same data-type using
the array data structure.

Major Operations
The major or the common operations that can be performed on the data
structures are:
AD

o Searching: We can search for any element in a data structure.

o Sorting: We can sort the elements of a data structure either in an
ascending or descending order.
o Insertion: We can also insert the new element in a data structure.
o Updation: We can also update the element, i.e., we can replace the
element with another element.
o Deletion: We can also perform the delete operation to remove the
element from the data structure.

Page
DS Algorithm
What is an Algorithm?
An algorithm is a process or a set of rules required to perform calculations
or some other problem-solving operations especially by a computer. The
formal definition of an algorithm is that it contains the finite set of
instructions which are being carried in a specific order to perform the
specific task. It is not the complete program or code; it is just a solution
(logic) of a problem, which can be represented either as an informal
description using a Flowchart or Pseudocode.

Characteristics of an Algorithm
The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input value to an
algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the instructions in
an algorithm should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the
algorithm should contain a limited number of instructions, i.e., the instructions should be
countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm
affects the overall process.
o Language independent: An algorithm must be language-independent so that the
instructions in an algorithm can be implemented in any of the languages with the same
output.

Dataflow of an Algorithm

o Problem: A problem can be a real-world problem or any instance from the real-world
problem for which we need to create a program or the set of instructions. The set of
instructions is known as an algorithm.
o Algorithm: An algorithm will be designed for a problem which is a step by step
procedure.
o Input: After designing an algorithm, the required and the desired inputs are provided to
the algorithm.
o Processing unit: The input will be given to the processing unit, and the processing unit
will produce the desired output.
o Output: The output is the outcome or the result of the program.

Why do we need Algorithms?

Page
We need algorithms because of the following reasons:

o Scalability: It helps us to understand the scalability. When we have a big real-world

problem, we need to scale it down into small-small steps to easily analyze the problem.
o Performance: The real-world is not easily broken down into smaller steps. If the problem
can be easily broken into smaller steps means that the problem is feasible.

Let's understand the algorithm through a real-world example. Suppose we want to make a lemon
juice, so following are the steps required to make a lemon juice:

Step 1: First, we will cut the lemon into half.

Step 2: Squeeze the lemon as much you can and take out its juice in a container.

Step 3: Add two tablespoon sugar in it.

Step 4: Stir the container until the sugar gets dissolved.

Step 5: When sugar gets dissolved, add some water and ice in it.

Step 6: Store the juice in a fridge for 5 to minutes.

Step 7: Now, it's ready to drink.

Now we will look an example of an algorithm in programming.

We will write an algorithm to add two numbers entered by the

user.

The following are the steps required to add two numbers

entered by the user:

Step 1: Start

Step 2: Declare three variables a, b, and sum.

AD

Step 3: Enter the values of a and b.

Step 4: Add the values of a and b and store the result in the sum
variable, i.e., sum=a+b.

Step 5: Print sum

Page
Step 6: Stop

Array in Data Structure

In this article, we will discuss the array in data structure. Arrays are defined as the collection of
similar types of data items stored at contiguous memory locations. It is one of the simplest data
structures where each data element can be randomly accessed by using its index number.

In C programming, they are the derived data types that can store the primitive type of data such
as int, char, double, float, etc. For example, if we want to store the marks of a student in 6
subjects, then we don't need to define a different variable for the marks in different subjects.
Instead, we can define an array that can store the marks in each subject at the contiguous
memory locations.

Properties of array
There are some of the properties of an array that are listed as follows -

o Each element in an array is of the same data type and carries the same size that is 4
bytes.
o Elements in the array are stored at contiguous memory locations from which the first
element is stored at the smallest memory location.
o Elements of the array can be randomly accessed since we can calculate the address of
each element of the array with the given base address and the size of the data element.

Representation of an array
We can represent an array in various ways in different programming languages. As an
illustration, let's see the declaration of array in C language -

As per the above illustration, there are some of the following important points -

o Index starts with 0.

o The array's length is 10, which means we can store 10 elements.
o Each element in the array can be accessed via its index.

AD

Why are arrays required?

Page
Arrays are useful because -

o Sorting and searching a value in an array is easier.

o Arrays are best to process multiple values quickly and easily.
o Arrays are good for storing multiple values in a single variable - In computer
programming, most cases require storing a large number of data of a similar type. To
store such an amount of data, we need to define a large number of variables. It would be
very difficult to remember the names of all the variables while writing the programs.
Instead of naming all the variables with a different name, it is better to define an array and
store all the elements into it.

Memory allocation of an array

As stated above, all the data elements of an array are stored at contiguous locations in the main
memory. The name of the array represents the base address or the address of the first element
in the main memory. Each element of the array is represented by proper indexing.

We can define the indexing of an array in the below ways -

1. 0 (zero-based indexing): The first element of the array will be arr[0].

2. 1 (one-based indexing): The first element of the array will be arr[1].
3. n (n - based indexing): The first element of the array can reside at any random index
number.

In the above image, we have shown the memory allocation of an array arr of size 5. The array
follows a 0-based indexing approach. The base address of the array is 100 bytes. It is the
address of arr[0]. Here, the size of the data type used is 4 bytes; therefore, each element will
take 4 bytes in the memory.

How to access an element from the array?

We required the information given below to access any random element from the array -

o Base Address of the array.

o Size of an element in bytes.
o Type of indexing, array follows.

Page
 The formula to calculate the address to access an array element -

1. Byte address of element A[i] = base address + size * ( i - first index)

Here, size represents the memory taken by the primitive data types. As an instance, int takes 2
bytes, float takes 4 bytes of memory space in C programming.

We can understand it with the help of an example -

Suppose an array, A[-10 ..... +2 ] having Base address (BA) = 999 and size of an element = 2
bytes, find the location of A[-1].

L(A[-1]) = 999 + 2 x [(-1) - (-10)]

= 999 + 18

= 1017

AD

Basic operations
Now, let's discuss the basic operations supported in the array -

o Traversal - This operation is used to print the elements of the array.

o Insertion - It is used to add an element at a particular index.
o Deletion - It is used to delete an element from a particular index.
o Search - It is used to search an element using the given index or by the value.
o Update - It updates an element at a particular index.

Traversal operation
This operation is performed to traverse through the array elements. It prints all array elements
one after another. We can understand it with the below program -

#include <stdio.h>
void main() {
int Arr[5] = {18, 30, 15, 70, 12};
int i;
printf("Elements of the array are:\n");
for(i = 0; i<5; i++) {
printf("Arr[%d] = %d, ", i, Arr[i]);
}
}

Output

Page
 Insertion operation
This operation is performed to insert one or more elements into the array. As per the
requirements, an element can be added at the beginning, end, or at any index of the array. Now,
let's see the implementation of inserting an element into the array.

#include <stdio.h>
int main()
{
int arr[20] = { 18, 30, 15, 70, 12 };
int i, x, pos, n = 5;
printf("Array elements before insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

x = 50; // element to be inserted

pos = 4;
n++;

for (i = n-1; i >= pos; i--)

arr[i] = arr[i - 1];
arr[pos - 1] = x;
printf("Array elements after insertion\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}

Output

AD

Deletion operation
As the name implies, this operation removes an element from the array and then reorganizes all
of the array elements.

#include <stdio.h>

void main() {
int arr[] = {18, 30, 15, 70, 12};
int k = 30, n = 5;

Page
 int i, j;

printf("Given array elements are :\n");

for(i = 0; i<n; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}

j = k;

while( j < n) {
arr[j-1] = arr[j];
j = j + 1;
}

n = n -1;

printf("\nElements of array after deletion:\n");

for(i = 0; i<n; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
}

Output

Search operation
This operation is performed to search an element in the array based on the value or index.

#include <stdio.h>

void main() {
int arr[5] = {18, 30, 15, 70, 12};
int item = 70, i, j=0 ;

printf("Given array elements are :\n");

for(i = 0; i<5; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
printf("\nElement to be searched = %d", item);
while( j < 5){
Page
 if( arr[j] == item ) {
break;
}

j = j + 1;
}

printf("\nElement %d is found at %d position", item, j+1);

}

Output

Update operation
This operation is performed to update an existing array element located at the given index.

#include <stdio.h>

void main() {
int arr[5] = {18, 30, 15, 70, 12};
int item = 50, i, pos = 3;

printf("Given array elements are :\n");

for(i = 0; i<5; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}

arr[pos-1] = item;
printf("\nArray elements after updation :\n");

for(i = 0; i<5; i++) {

printf("arr[%d] = %d, ", i, arr[i]);
}
}

Output

Page
 Advantages of Array
o Array provides the single name for the group of variables of the same type. Therefore, it is
easy to remember the name of all the elements of an array.
o Traversing an array is a very simple process; we just need to increment the base address
of the array in order to visit each element one by one.
o Any element in the array can be directly accessed by using the index.

2D Array
2D array can be defined as an array of arrays. The 2D array is organized as matrices which can
be represented as the collection of rows and columns.

However, 2D arrays are created to implement a relational database look alike data structure. It
provides ease of holding bulk of data at once which can be passed to any number of functions
wherever required.

How to declare 2D Array

The syntax of declaring two dimensional array is very much similar to that of a one dimensional
array, given as follows.

1. int arr[max_rows][max_columns];

however, It produces the data structure which looks like following.

Page
Above image shows the two dimensional array, the elements are organized in the form of rows
and columns. First element of the first row is represented by a[0][0] where the number shown in
the first index is the number of that row while the number shown in the second index is the
number of the column.

How do we access data in a 2D array

Due to the fact that the elements of 2D arrays can be random accessed. Similar to one
dimensional arrays, we can access the individual cells in a 2D array by using the indices of the
cells. There are two indices attached to a particular cell, one is its row number while the other is
its column number.

However, we can store the value stored in any particular cell of a 2D array to some variable x by
using the following syntax.

int x = a[i][j];

where i and j is the row and column number of the cell respectively.

We can assign each cell of a 2D array to 0 by using the following code:

Page
for ( int i=0; i<n ;i++)
{
for (int j=0; j<n; j++)
{
a[i][j] = 0;
}
}

Initializing 2D Arrays
We know that, when we declare and initialize one dimensional array in C programming
simultaneously, we don't need to specify the size of the array. However this will not work with 2D
arrays. We will have to define at least the second dimension of the array.

The syntax to declare and initialize the 2D array is given as follows.

int arr[2][2] = {0,1,2,3};

The number of elements that can be present in a 2D array will always be equal to
(number of rows * number of columns).

Example : Storing User's data into a 2D array and printing it.

C Example :

#include <stdio.h>
void main ()
{
int arr[3][3],i,j;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++)
{
printf("Enter a[%d][%d]: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n printing the elements ....\n");
for(i=0;i<3;i++)
{
printf("\n");
for (j=0;j<3;j++)
{
printf("%d\t",arr[i][j]);
}
}
}

Page
What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has
one end, whereas the Queue has two ends (front and rear). It contains only one pointer top
pointer pointing to the topmost element of the stack. Whenever an element is added in the
stack, it is added on the top of the stack, and the element can be deleted only from the stack. In
other words, a stack can be defined as a container in which insertion and deletion can
be done from the one end known as the top of the stack.

Some key points related to stack

o It is called as stack because it behaves like a real-world stack, piles of books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means that it can store
the elements of a limited size.
o It is a data structure that follows some order to insert and delete the elements, and that
order can be LIFO or FILO.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure there are five memory
blocks in the stack; therefore, the size of the stack is 5.

Suppose we want to store the elements in a stack and let's assume that stack is empty. We have
taken the stack of size 5 as shown below in which we are pushing the elements one by one until
the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it
goes from the top to the bottom when we were entering the new element in the stack. The stack
gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one way for entry and exit as
the other end is closed. It follows the LIFO pattern, which means that the value entered first will

Page
be removed last. In the above case, the value 5 is entered first, so it will be removed only after
the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the stack:

o push(): When we insert an element in a stack then the operation is known as a push. If
the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known as a pop. If the
stack is empty means that no element exists in the stack, this state is known as an
underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then the overflow condition
occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
o When the new element is pushed in a stack, first, the value of the top gets incremented,
i.e., top=top+1, and the element will be placed at the new position of the top.
o The elements will be inserted until we reach the max size of the stack.

Page
POP operation
The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then the underflow condition
occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Page
The following are the applications of the stack:

o Balancing of symbols: Stack is used for balancing a symbol. For example, we have the
following program:

int main()
{
cout<<"Hello";
cout<<"javaTpoint";
}

As we know, each program has an opening and closing braces; when the opening braces come,
we push the braces in a stack, and when the closing braces appear, we pop the opening braces
from the stack. Therefore, the net value comes out to be zero. If any symbol is left in the stack, it
means that some syntax occurs in a program.

o String reversal: Stack is also used for reversing a string. For example, we want to
reverse a "javaTpoint" string, so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until we reach the null character.
After pushing all the characters, we start taking out the character one by one until we
reach the bottom of the stack.
o UNDO/REDO: It can also be used for performing UNDO/REDO operations. For example, we
have an editor in which we write 'a', then 'b', and then 'c'; therefore, the text written in an
editor is abc. So, there are three states, a, ab, and abc, which are stored in a stack. There
would be two stacks in which one stack shows UNDO state, and the other shows REDO
state.
If we want to perform UNDO operation, and want to achieve 'ab' state, then we implement
pop operation.
o Recursion: The recursion means that the function is calling itself again. To maintain the
previous states, the compiler creates a system stack in which all the previous records of
the function are maintained.
o DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the
stack data structure.
o Backtracking: Suppose we have to create a path to solve a maze problem. If we are
moving in a particular path, and we realize that we come on the wrong way. In order to
come at the beginning of the path to create a new path, we have to use the stack data
structure.
o Expression conversion: Stack can also be used for expression conversion. This is one of
the most important applications of stack. The list of the expression conversion is given
below:
o Infix to prefix
o Infix to postfix
o Prefix to infix
o Prefix to postfix
Postfix to infix
o Memory management: The stack manages the memory. The memory is assigned in the
contiguous memory blocks. The memory is known as stack memory as all the variables

Page
 are assigned in a function call stack memory. The memory size assigned to the program is
known to the compiler. When the function is created, all its variables are assigned in the
stack memory. When the function completed its execution, all the variables assigned in
the stack are released.

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding the
stack are performed using arrays. Lets see how each operation can be implemented on the stack
using array data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation
involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element
at the top of the stack.

Stack is overflown when we try to insert an element into a completely filled stack therefore, our
main function must always avoid stack overflow condition.

Algorithm:

begin
if top = n then stack full
top = top + 1
stack (top) : = item;
end

Time Complexity : o(1)

implementation of push algorithm in C language

void push (int val,int n) //n is size of the stack

{
if (top == n )
printf("\n Overflow");
else
{
top = top +1;
stack[top] = val;
}
}

Page
Deletion of an element from a stack (Pop operation)
Deletion of an element from the top of the stack is called pop operation. The value of the
variable top will be incremented by 1 whenever an item is deleted from the stack. The top most
element of the stack is stored in an another variable and then the top is decremented by 1. the
operation returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an already empty stack.

Algorithm :

begin
if top = -1 then stack empty;
item := stack(top);
top = top - 1;
end;

Time Complexity : o(1)

Implementation of POP algorithm using C language

int pop ()
{
if(top == -1)
{
printf("Underflow");
return 0;
}
else
{
Item=stack[top];
return stack[top - - ];
}
}

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without
deleting it. Underflow condition can occur if we try to return the top element in an already empty
stack.

Algorithm :

PEEK (STACK, TOP)

Begin
if top = -1 then stack empty
item = stack[top]
return item

Page
 End
Time complexity: o(n)

Implementation of Peek algorithm in C language

int peek()
{
if (top == -1)
{
printf("Underflow");
return 0;
}
1. else
{
return stack [top];
}
}
C program
#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{

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

scanf("%d",&n);
printf("*********Stack operations using array*********");

printf("\n----------------------------------------------\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();

Page
 break;
}
case 3:
{
show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}

void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

void pop ()
{
if(top == -1)
printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}

Page
 if(top == -1)
{
printf("Stack is empty");
}
}

Queue
1. A queue can be defined as an ordered list which enables insert operations to be performed at
one end called REAR and delete operations to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.

Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite fair for the
ordering of actions. There are various applications of queues discussed as below.

1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at
the same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD player,
etc.
4. Queue are used to maintain the play list in media players in order to add and remove the
songs from the play-list.
5. Queues are used in operating systems for handling interrupts.

Page
Types of Queue
In this article, we will discuss the types of queue. But before moving towards the types, we
should first discuss the brief introduction of the queue.

What is a Queue?
Queue is the data structure that is similar to the queue in the real world. A queue is a data
structure in which whatever comes first will go out first, and it follows the FIFO (First-In-First-Out)
policy. Queue can also be defined as the list or collection in which the insertion is done from one
end known as the rear end or the tail of the queue, whereas the deletion is done from another
end known as the front end or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the last person enters in the queue gets
the ticket at last. Similar approach is followed in the queue in data structure.

The representation of the queue is shown in the below image -

Types of Queue
There are four different types of queue that are listed as follows -

Page
 o Simple Queue or Linear Queue
o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or 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 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.

To know more about the queue in data structure, you can click the link
- https://www.javatpoint.com/data-structure-queue

Circular Queue
Page
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 representation of circular queue is
shown in the below image -

The 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. The main advantage of using the circular queue is better
memory utilization.

To know more about the circular queue, you can click the link
- https://www.javatpoint.com/circular-queue

Priority Queue
It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements 7,

Page
 5, and 3 in the same order, so, insertion can be done with the same sequence, but the
order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in
arbitrary order, but only the largest element can be deleted first. Suppose an array with
elements 7, 3, and 5 in the same order, so, insertion can be done with the same sequence,
but the order of deleting the elements is 7, 5, 3.
o Deque (or, Double Ended Queue)
o In Deque or Double Ended Queue, insertion and deletion can be done from both ends of
the queue either from the front or rear. It means that we can insert and delete elements
from both front and rear ends of the queue. Deque can be used as a palindrome checker
means that if we read the string from both ends, then the string would be the same.
o Deque can be used both as stack and queue as it allows the insertion and deletion
operations on both ends. Deque can be considered as stack because stack follows the LIFO
(Last In First Out) principle in which insertion and deletion both can be performed only
from one end. And in deque, it is possible to perform both insertion and deletion from one
end, and Deque does not follow the FIFO principle.
o The representation of the deque is shown in the below image -

o
o To know more about the deque, you can click the link - https://www.javatpoint.com/ds-
deque
o There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from both
ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from both

Page
 ends.

Now, let's see the operations performed on the queue.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns the
element which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the front
pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is completely
full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.

Now, let's see the ways to implement the queue.

Ways to implement the queue

There are two ways of implementing the Queue:

o Implementation using array: The sequential allocation in a Queue can be implemented

using an array. For more details, click on the below link: https://www.javatpoint.com/array-
representation-of-queue
o Implementation using Linked list: The linked list allocation in a Queue can be
implemented using a linked list. For more details, click on the below
link: https://www.javatpoint.com/linked-list-implementation-of-queue

So, that's all about the article. Hope, the article will be helpful and informative to you.

Page
Array representation of Queue
We can easily represent queue by using linear arrays. There are two variables i.e. front and rear,
that are implemented in the case of every queue. Front and rear variables point to the position
from where insertions and deletions are performed in a queue. Initially, the value of front and
queue is -1 which represents an empty queue. Array representation of a queue containing 5
elements along with the respective values of front and rear, is shown in the following figure.

The above figure shows the queue of characters forming the English word "HELLO". Since, No
deletion is performed in the queue till now, therefore the value of front remains -1 . However, the
value of rear increases by one every time an insertion is performed in the queue. After inserting
an element into the queue shown in the above figure, the queue will look something like
following. The value of rear will become 5 while the value of front remains same.

Page
After deleting an element, the value of front will increase from -1 to 0. however, the queue will
look something like following.

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.

Algorithm
o Step 1:
o IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

Page
C Function
void insert (int queue[], int max, int front, int rear, int item)
{
if (rear + 1 == max)
{
printf("overflow");
}
else
{
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear + 1;
}
queue[rear]=item;
}
}

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.

Algorithm
o Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT

AD

C Function
int delete (int queue[], int max, int front, int rear)
{
int y;

Page
 if (front == -1 || front > rear)

{
printf("underflow");
}
else
{
y = queue[front];
if(front == rear)
{
front = rear = -1;
else
front = front + 1;

}
return y;
}
}

Menu driven program to implement queue using array

#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)
{
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:

Page
 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;
}
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)
{

Page
 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]);
}
}
}

Circular Queue
Why was the concept of the circular queue introduced?
There was one limitation in the array implementation of Queue. If the rear reaches to the end
position of the Queue then there might be possibility that some vacant spaces are left in the
beginning which cannot be utilized. So, to overcome such limitations, the concept of the circular
queue was introduced.

Page
As we can see in the above image, the rear is at the last position of the Queue and front is
pointing somewhere rather than the 0 th position. In the above array, there are only two elements
and other three positions are empty. The rear is at the last position of the Queue; if we try to
insert the element then it will show that there are no empty spaces in the Queue. There is one
solution to avoid such wastage of memory space by shifting both the elements at the left and
adjust the front and rear end accordingly. It is not a practically good approach because shifting
all the elements will consume lots of time. The efficient approach to avoid the wastage of the
memory is to use the circular queue data structure.

What is a Circular Queue?

A circular queue is similar to a linear queue as it is also based on the FIFO (First In First Out)
principle except that the last position is connected to the first position in a circular queue that
forms a circle. It is also known as a Ring Buffer.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

o Front: It is used to get the front element from the Queue.

o Rear: It is used to get the rear element from the Queue.

Page
 o enQueue(value): This function is used to insert the new value in the Queue. The new
element is always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The deletion in a Queue
always takes place from the front end.

Applications of Circular Queue

The circular Queue can be used in the following scenarios:

o Memory management: The circular queue provides memory management. As we have

already seen that in linear queue, the memory is not managed very efficiently. But in case
of a circular queue, the memory is managed efficiently by placing the elements in a
location which is unused.
o CPU Scheduling: The operating system also uses the circular queue to insert the
processes and then execute them.
o Traffic system: In a computer-control traffic system, traffic light is one of the best
examples of the circular queue. Each light of traffic light gets ON one by one after every
jinterval of time. Like red light gets ON for one minute then yellow light for one minute and
then green light. After green light, the red light gets ON.

AD

Enqueue operation
The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.

o Initially the front and rear are set to -1. When we insert the first element in a Queue, front
and rear both are set to 0.
o When we insert a new element, the rear gets incremented, i.e., rear=rear+1.

Scenarios for inserting an element

There are two scenarios in which queue is not full:

o If rear != max - 1, then rear will be incremented to mod(maxsize) and the new value
will be inserted at the rear end of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then set the value of
rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

o When front ==0 && rear = max-1, which means that front is at the first position of the
Queue and rear is at the last position of the Queue.
o front== rear + 1;

Algorithm to insert an element in a circular queue

Page
 Step 1: IF (REAR+1)%MAX = FRONT
Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT

Dequeue Operation
The steps of dequeue operation are given below:

o First, we check whether the Queue is empty or not. If the queue is empty, we cannot
perform the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1.

Page
 o If there is only one element left which is to be deleted, then the front and rear are reset to
-1.

Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]

Step 2: SET VAL = QUEUE[FRONT]

AD

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]

Step 4: EXIT

Let's understand the enqueue and dequeue operation through the diagrammatic
representation.

Page
Page
Page
Implementation of circular queue using Array

#include <stdio.h>

# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;
// function to insert an element in a circular queue
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is empty
{
front=0;
rear=0;

Page
 queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is full
{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at the rear position.
}
}

// function to delete the element from the queue

int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
// function to display the elements of a queue
void display()
{
if (rear == -1)
printf("\nQueue is Empty!!!");
else
{
int i;
printf("\nQueue elements are:\n");
for (i = front; i <= rear; i++)
printf("%d ", queue[i]);
}
printf("\n");
}
int main()

Page
 {
int choice=1,x; // variables declaration

while(choice<4 && choice!=0) // while loop

{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
scanf("%d", &choice);

switch(choice)
{

case 1:

printf("Enter the element which is to be inserted");

scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();

}}
return 0;
}

Deque (or double-ended queue)

In this article, we will discuss the double-ended queue or deque. We should first see a brief
description of the queue.

What is a queue?
A queue is a data structure in which whatever comes first will go out first, and it follows the FIFO
(First-In-First-Out) policy. Insertion in the queue is done from one end known as the rear end or
the tail, whereas the deletion is done from another end known as the front end or the head of
the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the person enters last in the queue gets
the ticket at last.

What is a Deque (or double-ended queue)

Page
The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion
and deletion operations are performed from both ends. We can say that deque is a generalized
version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not follow
the FIFO rule. The representation of a deque is given as follows -

Types of deque
There are two types of deque -

o Input restricted queue

o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion
can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion
can be performed from both ends.

Page
Operations performed on deque
There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear

AD

We can also perform peek operations in the deque along with the operations listed above.
Through peek operation, we can get the deque's front and rear elements of the deque. So, in
addition to the above operations, following operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an example.

Insertion at the front end

In this operation, the element is inserted from the front end of the queue. Before implementing
the operation, we first have to check whether the queue is full or not. If the queue is not full,
then the element can be inserted from the front end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
first element.
o Otherwise, check the position of the front if the front is less than 1 (front < 1), then
reinitialize it by front = n - 1, i.e., the last index of the array.

Page
Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue. Before implementing
the operation, we first have to check again whether the queue is full or not. If the queue is not
full, then the element can be inserted from the rear end by using the below conditions -

AD

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
first element.
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead of
increasing it by 1, we have to make it equal to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue. Before implementing
the operation, we first have to check whether the queue is empty or not.

Page
If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion. If the queue is not full, then the element can be inserted from the front end by using
the below conditions -

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

AD

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue. Before implementing
the operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

Page
 Check empty

This operation is performed to check whether the deque is empty or not. If front = -1, it means
that the deque is empty.

Check full

This operation is performed to check whether the deque is full or not. If front = rear + 1, or front
= 0 and rear = n - 1 it means that the deque is full.

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

OR

----------------------------------- -----------------------------------------------------------------------------

1. Insert at the Front

This operation adds an element at the front.

1. Check if the deque is full.

2. Check the position of front

3. If the deque is full (i.e. (front == 0 && rear == n - 1) || (front == rear + 1)), insertion operation cannot
be performed (overflow condition).
4. If the deque is empty, reinitialize front = 0. And, add the new key into array[front].

Page
5. If front = 0, reinitialize front = n-1 (last index).
6. Shift front to the end
7. Else, decrease front by 1.

8. Add the new key 5 into array[front]. Insert the

element at Front

2. Insert at the Rear

This operation adds an element to the rear.

1. Check if the deque is full.

2. Check if deque is full

3. If the deque is full, insertion operation cannot be performed (overflow condition).

4. If the deque is empty, reinitialize rear = 0. And, add the new key into array[rear].
5. If rear = n - 1, reinitialize real = 0 (first index).

Page
6. Else, increase rear by 1. Increase the rear

7. Add the new key 5 into array[rear]. Insert the

element at rear
3. Delete from the Front
The operation deletes an element from the front.

1. Check if the deque is empty. Check if deque is

empty

2. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
3. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.

4. Else if front is at the last index (i.e. front = n - 1), set front = 0.

5. Else, front = front + 1. Increase the front

4. Delete from the Rear
Page
 This operation deletes an element from the rear.

1. Check if the deque is empty. Check if deque is

empty

2. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
3. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else follow the steps
below.
4. If rear is at the first index (i.e. rear = 0), reinitialize rear = n - 1.

5. Else, rear = rear - 1. Decrease the rear

5. Check Empty
This operation checks if the deque is empty. If front = -1, the deque is empty.
6. Check Full
This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front = rear + 1, the deque is
full.

Page
Applications of deque
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string from both
ends, the string would be the same.

Implementation of deque
Now, let's see the implementation of deque in C programming language.

#include <stdio.h>
#define size 5
int deque[size];
int f = -1, r = -1;
// insert_front function will insert the value from the front
void insert_front(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
f=r=0;
deque[f]=x;
}
else if(f==0)
{
f=size-1;
deque[f]=x;
}
else
{
f=f-1;
deque[f]=x;
}
}

// insert_rear function will insert the value from the rear

void insert_rear(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{

Page
 r=0;
deque[r]=x;
}
else if(r==size-1)
{
r=0;
deque[r]=x;
}
else
{
r++;
deque[r]=x;
}

// display function prints all the value of deque.

void display()
{
int i=f;
printf("\nElements in a deque are: ");

while(i!=r)
{
printf("%d ",deque[i]);
i=(i+1)%size;
}
printf("%d",deque[r]);
}

// getfront function retrieves the first value of the deque.

void getfront()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at front is: %d", deque[f]);
}

// getrear function retrieves the last value of the deque.

void getrear()
{

Page
 if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at rear is %d", deque[r]);
}

// delete_front() function deletes the element from the front

void delete_front()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[f]);
f=-1;
r=-1;

}
else if(f==(size-1))
{
printf("\nThe deleted element is %d", deque[f]);
f=0;
}
else
{
printf("\nThe deleted element is %d", deque[f]);
f=f+1;
}
}

// delete_rear() function deletes the element from the rear

void delete_rear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[r]);

Page
 f=-1;
r=-1;

}
else if(r==0)
{
printf("\nThe deleted element is %d", deque[r]);
r=size-1;
}
else
{
printf("\nThe deleted element is %d", deque[r]);
r=r-1;
}
}

int main()
{
insert_front(20);
insert_front(10);
insert_rear(30);
insert_rear(50);
insert_rear(80);
display(); // Calling the display function to retrieve the values of deque
getfront(); // Retrieve the value at front-end
getrear(); // Retrieve the value at rear-end
delete_front();
delete_rear();
display(); // calling display function to retrieve values after deletion
return 0;
}

What is a priority queue?

A priority queue is an abstract data type that behaves similarly to the normal queue except that
each element has some priority, i.e., the element with the highest priority would come first in a
priority queue. The priority of the elements in a priority queue will determine the order in which
elements are removed from the priority queue.

The priority queue supports only comparable elements, which means that the elements are
either arranged in an ascending or descending order.

For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue
with an ordering imposed on the values is from least to the greatest. Therefore, the 1 number
would be having the highest priority while 22 will be having the lowest priority.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

Page
 o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of the lesser
priority.
o If two elements in a priority queue have the same priority, they will be arranged using the
FIFO principle.

Let's understand the priority queue through an example.

We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22

All the values are arranged in ascending order. Now, we will observe how the priority queue will
look after performing the following operations:

o poll(): This function will remove the highest priority element from the priority queue. In
the above priority queue, the '1' element has the highest priority, so it will be removed
from the priority queue.
o add(2): This function will insert '2' element in a priority queue. As 2 is the smallest
element among all the numbers so it will obtain the highest priority.
o poll(): It will remove '2' element from the priority queue as it has the highest priority
queue.
o add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it will
obtain the third highest priority in a priority queue.

AD

Types of Priority Queue

There are two types of priority queue:

o Ascending order priority queue: In ascending order priority queue, a lower priority
number is given as a higher priority in a priority. For example, we take the numbers from 1
to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is

Page
 given as the highest priority in a priority queue.

o Descending order priority queue: In descending order priority queue, a higher priority
number is given as a higher priority in a priority. For example, we take the numbers from 1
to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is
given as the highest priority in a priority queue.

Representation of priority queue

Now, we will see how to represent the priority queue through a one-way list.

We will create the priority queue by using the list given below in which INFO list contains the
data elements, PRN list contains the priority numbers of each data element available in
the INFO list, and LINK basically contains the address of the next node.

Page
Let's create the priority queue step by step.

In the case of priority queue, lower priority number is considered the higher priority,
i.e., lower priority number = higher priority.

Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be inserted in
the list as shown in the below diagram:

Step 2: After inserting 333, priority number 2 is having a higher priority, and data values
associated with this priority are 222 and 111. So, this data will be inserted based on the FIFO
principle; therefore 222 will be added first and then 111.

Step 3: After inserting the elements of priority 2, the next higher priority number is 4 and data
elements associated with 4 priority numbers are 444, 555, 777. In this case, elements would be
inserted based on the FIFO principle; therefore, 444 will be added first, then 555, and then 777.

Step 4: After inserting the elements of priority 4, the next higher priority number is 5, and the
value associated with priority 5 is 666, so it will be inserted at the end of the queue.

AD

Page
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list, heap data
structure and binary search tree. The heap data structure is the most efficient way of
implementing the priority queue, so we will implement the priority queue using a heap data
structure in this topic. Now, first we understand the reason why heap is the most efficient way
among all the other data structures.

Analysis of complexities using different implementations

Implementation add Remove peek

Linked list O(1) O(n) O(n)

Binary heap O(logn) O(logn) O(1)

Binary search tree O(logn) O(logn) O(1)

What is Heap?
A heap is a tree-based data structure that forms a complete binary tree, and satisfies the heap
property. If A is a parent node of B, then A is ordered with respect to the node B for all nodes A
and B in a heap. It means that the value of the parent node could be more than or equal to the
value of the child node, or the value of the parent node could be less than or equal to the value
of the child node. Therefore, we can say that there are two types of heaps:

Page
 o Max heap: The max heap is a heap in which the value of the parent node is greater than
the value of the child nodes.

o Min heap: The min heap is a heap in which the value of the parent node is less than the
value of the child nodes.

Both the heaps are the binary heap, as each has exactly two child nodes.

Priority Queue Operations

Page
The common operations that we can perform on a priority queue are insertion, deletion and
peek. Let's see how we can maintain the heap data structure.

AD

o Inserting the element in a priority queue (max heap)

If we insert an element in a priority queue, it will move to the empty slot by looking from top to
bottom and left to right.

If the element is not in a correct place then it is compared with the parent node; if it is found out
of order, elements are swapped. This process continues until the element is placed in a correct
position.

Page
 o Removing the minimum element from the priority queue

As we know that in a max heap, the maximum element is the root node. When we remove the
root node, it creates an empty slot. The last inserted element will be added in this empty slot.
Then, this element is compared with the child nodes, i.e., left-child and right child, and swap with
the smaller of the two. It keeps moving down the tree until the heap property is restored.

Applications of Priority queue

The following are the applications of the priority queue:

o It is used in the Dijkstra's shortest path algorithm.

o It is used in prim's algorithm
o It is used in data compression techniques like Huffman code.
o It is used in heap sort.
o It is also used in operating system like priority scheduling, load balancing and interrupt
handling.

Program to create the priority queue using the binary max heap.

#include <stdio.h>
#include <stdio.h>
int heap[40];
int size=-1;

// retrieving the parent node of the child node

int parent(int i)
{

return (i - 1) / 2;
}

// retrieving the left child of the parent node.

int left_child(int i)
{
return i+1;
}
// retrieving the right child of the parent
int right_child(int i)
{
return i+2;
}
// Returning the element having the highest priority
int get_Max()
{
return heap[0];
}

Page
//Returning the element having the minimum priority
int get_Min()
{
return heap[size];
}
// function to move the node up the tree in order to restore the heap property.
void moveUp(int i)
{
while (i > 0)
{
// swapping parent node with a child node
if(heap[parent(i)] < heap[i]) {

int temp;
temp=heap[parent(i)];
heap[parent(i)]=heap[i];
heap[i]=temp;

}
// updating the value of i to i/2
i=i/2;
}
}

//function to move the node down the tree in order to restore the heap property.
void moveDown(int k)
{
int index = k;

// getting the location of the Left Child

int left = left_child(k);

if (left <= size && heap[left] > heap[index]) {

index = left;
}

// getting the location of the Right Child

int right = right_child(k);

if (right <= size && heap[right] > heap[index]) {

index = right;
}

// If k is not equal to index

if (k != index) {
int temp;

Page
 temp=heap[index];
heap[index]=heap[k];
heap[k]=temp;
moveDown(index);
}
}

// Removing the element of maximum priority

void removeMax()
{
int r= heap[0];
heap[0]=heap[size];
size=size-1;
moveDown(0);
}
//inserting the element in a priority queue
void insert(int p)
{
size = size + 1;
heap[size] = p;

// move Up to maintain heap property

moveUp(size);
}

//Removing the element from the priority queue at a given index i.

void delete(int i)
{
heap[i] = heap[0] + 1;

// move the node stored at ith location is shifted to the root node
moveUp(i);

// Removing the node having maximum priority

removeMax();
}
int main()
{
// Inserting the elements in a priority queue

insert(20);
insert(19);
insert(21);
insert(18);
insert(12);
insert(17);
insert(15);

Page
 insert(16);
insert(14);
int i=0;

printf("Elements in a priority queue are : ");

for(int i=0;i<=size;i++)
{
printf("%d ",heap[i]);
}
delete(2); // deleting the element whose index is 2.
printf("\nElements in a priority queue after deleting the element are : ");
for(int i=0;i<=size;i++)
{
printf("%d ",heap[i]);
}
int max=get_Max();
printf("\nThe element which is having the highest priority is %d: ",max);

int min=get_Min();
printf("\nThe element which is having the minimum priority is : %d",min);
return 0;
}

In the above program, we have created the following functions:

o int parent(int i): This function returns the index of the parent node of a child node, i.e., i.
o int left_child(int i): This function returns the index of the left child of a given index, i.e.,
i.
o int right_child(int i): This function returns the index of the right child of a given index,
i.e., i.
o void moveUp(int i): This function will keep moving the node up the tree until the heap
property is restored.
o void moveDown(int i): This function will keep moving the node down the tree until the
heap property is restored.
o void removeMax(): This function removes the element which is having the highest
priority.
o void insert(int p): It inserts the element in a priority queue which is passed as an
argument in a function.
o void delete(int i): It deletes the element from a priority queue at a given index.
o int get_Max(): It returns the element which is having the highest priority, and we know
that in max heap, the root node contains the element which has the largest value, and
highest priority.
o int get_Min(): It returns the element which is having the minimum priority, and we know
that in max heap, the last node contains the element which has the smallest value, and
lowest priority.

Page
Linked list
In this article, we will see the introduction of linked list.

Linked list is a linear data structure that includes a series of connected nodes. Linked list can be
defined as the nodes that are randomly stored in the memory. A node in the linked list contains
two parts, i.e., first is the data part and second is the address part. The last node of the list
contains a pointer to the null. After array, linked list is the second most used data structure. In a
linked list, every link contains a connection to another link.

Representation of a Linked list

Linked list can be represented as the connection of nodes in which each node points to the next
node of the list. The representation of the linked list is shown below -

Till now, we have been 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
that must be known to decide the data structure that will be used throughout the program.

Now, the question arises why we should use linked list over array?

Why use linked list over array?

Linked list is a data structure that overcomes the limitations of arrays. Let's first see some of the
limitations of arrays -

o The size of the array must be known in advance before using it in the program.

Page
 o Increasing the size of the array is a time taking process. It is almost impossible to expand
the size of the array at run time.
o All the elements in the array need to be contiguously stored in the memory. Inserting an
element in the array needs shifting of all its predecessors.

Linked list is useful because -

o It allocates the memory dynamically. All the nodes of the linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
o In linked list, size 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.

How to declare a linked list?

It is simple to declare an array, as it is of single type, while the declaration of linked list is a bit
more typical than array. Linked list contains two parts, and both are of different types, i.e., one is
the simple variable, while another is the pointer variable. We can declare the linked list by using
the user-defined data type structure.

The declaration of linked list is given as follows -

1. struct node
2. {
3. int data;
4. struct node *next;
5. }

In the above declaration, we have defined a structure named as node that contains two
variables, one is data that is of integer type, and another one is next that is a pointer which
contains the address of next node.

Now, let's move towards the types of linked list.

Types of Linked list

Linked list is classified into the following types -

o Singly-linked list - Singly linked list can be defined as the collection of an ordered set of
elements. A node in the singly linked list consists 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.
o Doubly linked list - Doubly linked list is a complex type of linked list in which a node
contains a pointer to the previous as well as the next node in the sequence. Therefore, in
a doubly-linked list, a node consists of three parts: node data, pointer to the next node in
sequence (next pointer), and pointer to the previous node (previous pointer).

Page
 o Circular singly linked list - In a circular singly linked list, the last node of the list
contains a pointer to the first node of the list. We can have circular singly linked list as well
as circular doubly linked list.
o Circular doubly linked list - Circular doubly linked list is a more complex type of data
structure in which a node contains pointers to its previous node as well as the next node.
Circular doubly linked list doesn't contain NULL in any of the nodes. The last node of the
list contains the address of the first node of the list. The first node of the list also contains
the address of the last node in its previous pointer.

Now, let's see the benefits and limitations of using the Linked list.

Advantages of Linked list

The advantages of using the Linked list are given as follows -

o Dynamic data structure - The size of the linked list may vary according to the
requirements. Linked list does not have a fixed size.
o Insertion and deletion - Unlike arrays, insertion, and deletion in linked list is easier.
Array elements are stored in the consecutive location, whereas the elements in the linked
list are stored at a random location. To insert or delete an element in an array, we have to
shift the elements for creating the space. Whereas, in linked list, instead of shifting, we
just have to update the address of the pointer of the node.
o Memory efficient - The size of a linked list can grow or shrink according to the
requirements, so memory consumption in linked list is efficient.
o Implementation - We can implement both stacks and queues using linked list.

Disadvantages of Linked list

The limitations of using the Linked list are given as follows -

o Memory usage - In linked list, node occupies more memory than array. Each node of the
linked list occupies two types of variables, i.e., one is a simple variable, and another one is
the pointer variable.
o Traversal - Traversal is not easy in the linked list. If we have to access an element in the
linked list, we cannot access it randomly, while in case of array we can randomly access it
by index. For example, if we want to access the 3rd node, then we need to traverse all the
nodes before it. So, the time required to access a particular node is large.
o Reverse traversing - Backtracking or reverse traversing is difficult in a linked list. In a
doubly-linked list, it is easier but requires more memory to store the back pointer.

Applications of Linked list

The applications of the Linked list are given as follows -

o With the help of a linked list, the polynomials can be represented as well as we can
perform the operations on the polynomial.
o A linked list can be used to represent the sparse matrix.

Page
 o The various operations like student's details, employee's details, or product details can be
implemented using the linked list as the linked list uses the structure data type that can
hold different data types.
o Using linked list, we can implement stack, queue, tree, and other various data structures.
o The graph is a collection of edges and vertices, and the graph can be represented as an
adjacency matrix and adjacency list. If we want to represent the graph as an adjacency
matrix, then it can be implemented as an array. If we want to represent the graph as an
adjacency list, then it can be implemented as a linked list.
o A linked list can be used to implement dynamic memory allocation. The dynamic memory
allocation is the memory allocation done at the run-time.

Operations performed on Linked list

The basic operations that are supported by a list are mentioned as follows -

AD
o Insertion - This operation is performed to add an element into the list.
o Deletion - It is performed to delete an operation from the list.
o Display - It is performed to display the elements of the list.
o Search - It is performed to search an element from the list using the given key.

Types of Linked list

The following are the types of linked list:

o Singly Linked list

o Doubly Linked list
o Circular Linked list
o Doubly Circular Linked list

Singly 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.

Page
Uses of Linked List
o The list is not required to be contiguously present in the memory. The node can reside any
where 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 not 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.

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.

Singly linked list or One way chain

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.

Page
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.

Insertion at beginning

Insertion at end of the list

Insertion after specified node

Deletion and Traversing

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.

Deletion at beginning

Page
Deletion at the end of the list

Deletion after specified node

Traversing

Searching

Linked List in C: Menu Driven Program

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\
n4.Delete from Beginning\n
5.Delete from last\n6.Delete node after specified location\n7.Search for an element\
n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();

Page
 break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
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;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

Page
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)
{
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");

}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);

Page
 ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;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");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_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 ...\n");
}

Page
 else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{

Page
 printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}

Page
Doubly linked list
Doubly linked list is a complex type of linked list in which a node contains a pointer to the
previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node
consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer
to the previous node (previous pointer). A sample node in a doubly linked list is shown in the
figure.

A doubly linked list containing three nodes having numbers from 1 to 3 in their data part, is
shown in the following image.

In C, structure of a node in doubly linked list can be given as :

struct node
{
struct node *prev;
int data;
struct node *next;
Page
 }

The prev part of the first node and the next part of the last node will always contain null
indicating end in each direction.

In a singly linked list, we could traverse only in one direction, because each node contains
address of the next node and it doesn't have any record of its previous nodes. However, doubly
linked list overcome this limitation of singly linked list. Due to the fact that, each node of the list
contains the address of its previous node, we can find all the details about the previous node as
well by using the previous address stored inside the previous part of each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following image. Generally, doubly
linked list consumes more space for every node and therefore, causes more expansive basic
operations such as insertion and deletion. However, we can easily manipulate the elements of
the list since the list maintains pointers in both the directions (forward and backward).

In the following image, the first element of the list that is i.e. 13 stored at address 1. The head
pointer points to the starting address 1. Since this is the first element being added to the list
therefore the prev of the list contains null. The next node of the list resides at address 4
therefore the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing null or -1 in its next part.

Page
Operations on doubly linked list
Node Creation

struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;

All the remaining operations regarding doubly linked list are described in the following table.

S Operation Description
N

1 Insertion at Adding the node into the linked list

beginning at beginning.

Page
2 Insertion at end Adding the node into the linked list
to the end.

3 Insertion after Adding the node into the linked list

specified node after the specified node.

4 Deletion at Removing the node from beginning

beginning of the list

5 Deletion at the Removing the node from end of the

end list.

6 Deletion of the Removing the node which is present

node having just after the node containing the
given data given data.

7 Searching Comparing each node data with the

item to be searched and return the
location of the item in the list if the
item found else return null.

8 Traversing Visiting each node of the list at least

once in order to perform some
specific operation like searching,
sorting, display, etc.

Menu Driven Program in C to implement all the operations of doubly

linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{

Page
 printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\
n4.Delete from Beginning\n
5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\
n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;

Page
 ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}

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

Page
 head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;

Page
 printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;

Page
 free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)

Page
 {
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

Circular Singly Linked List

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the
list. We can have circular singly linked list as well as circular doubly linked list.

We traverse a circular singly linked list until we reach the same node where we started. The
circular singly liked list has no beginning and no ending. There is no null value present in the
next part of any of the nodes.

The following image shows a circular singly linked list.

Page
Circular linked list are mostly used in task maintenance in operating systems. There are many
examples where circular linked list are being used in computer science including browser surfing
where a record of pages visited in the past by the user, is maintained in the form of circular
linked lists and can be accessed again on clicking the previous button.

Memory Representation of circular linked list:

In the following image, memory representation of a circular linked list containing marks of a
student in 4 subjects. However, the image shows a glimpse of how the circular list is being stored
in the memory. The start or head of the list is pointing to the element with the index 1 and
containing 13 marks in the data part and 4 in the next part. Which means that it is linked with
the node that is being stored at 4th index of the list.

However, due to the fact that we are considering circular linked list in the memory therefore the
last node of the list contains the address of the first node of the list.

Page
We can also have more than one number of linked list in the memory with the different start
pointers pointing to the different start nodes in the list. The last node is identified by its next part
which contains the address of the start node of the list. We must be able to identify the last node
of any linked list so that we can find out the number of iterations which need to be performed
while traversing the list.

Operations on Circular Singly linked list:

Insertion

S Operation Description
N

1 Insertion at Adding a node into circular singly

beginning linked list at the beginning.

Page
2 Insertion at the Adding a node into circular singly
end linked list at the end.

Deletion & Traversing

S Operation Description
N

1 Deletion at Removing the node from circular singly

beginning linked list at the beginning.

2 Deletion at Removing the node from circular singly

the end linked list at the end.

3 Searching Compare each element of the node with

the given item and return the location at
which the item is present in the list
otherwise return null.

4 Traversing Visiting each element of the list at least

once in order to perform some specific
operation.

Menu-driven program in C implementing all operations

on circular singly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();

Page
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\
n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete fro
m last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
Page
 if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
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 lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
Page
 temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}

printf("\nnode inserted\n");
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}

else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");

}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
Page
 head = NULL;
free(head);
printf("\nnode deleted\n");

}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");

}
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
Page
 else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}

void display()
{
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);
}

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in which a node contain
pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain
NULL in any of the node. The last node of the list contains the address of the first node of the list.
The first node of the list also contain address of the last node in its previous pointer.

Page
A circular doubly linked list is shown in the following figure.

Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it
demands more space per node and more expensive basic operations. However, a circular doubly
linked list provides easy manipulation of the pointers and the searching becomes twice as
efficient.

Memory Management of Circular Doubly linked list

The following figure shows the way in which the memory is allocated for a circular doubly linked
list. The variable head contains the address of the first element of the list i.e. 1 hence the
starting node of the list contains data A is stored at address 1. Since, each node of the list is
supposed to have three parts therefore, the starting node of the list contains address of the last
node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at address 8 and
containing data as 6, contains address of the first node of the list as shown in the image i.e. 1. In
circular doubly linked list, the last node is identified by the address of the first node which is
stored in the next part of the last node therefore the node which contains the address of the first
node, is actually the last node of the list.

Page
Operations on circular doubly linked list :
There are various operations which can be performed on circular doubly linked list. The node
structure of a circular doubly linked list is similar to doubly linked list. However, the operations
on circular doubly linked list is described in the following table.

S Operation Description
N

1 Insertion at Adding a node in circular doubly

beginning linked list at the beginning.

2 Insertion at Adding a node in circular doubly

end linked list at the end.

3 Deletion at Removing a node in circular doubly

Page
 beginning linked list from beginning.

4 Deletion at end Removing a node in circular doubly

linked list at the end.

Traversing and searching in circular doubly linked list is similar to that in the circular singly
linked list.

C program to implement all the operations on circular doubly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\
n5.Search\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:

Page
 deletion_beginning();
break;
case 4:
deletion_last();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;

Page
 ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("\nNode inserted\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nnode inserted\n");
}

void deletion_beginning()
{

Page
 struct node *temp;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;

Page
 free(ptr);
printf("\nnode deleted\n");
}
}

void display()
{
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);
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else

Page
 {
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}

Page