Dequeue Operation:

The steps of dequeue operation are given below:

First, we check whether the Queue is empty or not. If the queue is empty, we cannot perform the dequeue
operation.
When the element is deleted, the value of front gets decremented by 1.
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]
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

Double Ended Queue

A double-ended queue is a queue where items can be inserted & deleted at either end. That is, we
can insert elements from both rear & front ends. Again there are 2 types of double-ended queues.
They are:
An input-restricted deque is one where deletion can be made from both ends, but insertion can be
made at one end only.
An output-restricted deque is one where insertion can be made at both ends, but deletion can be
made from one end only.

Initializing a DeQue: Consider the DeQueue with size is 5

Step1: Empty DeQueue

Inserting Using Rear:

Step2:Inserting ‘10’ element into Queue
Step3: Inserting the ‘20’ element into Queue

Step4: Inserting the ‘30’ element into Queue

Step5: Inserting the ‘40’ element into Queue

Step6: Inserting the ‘50’ element into Queue

Removing values using Front:

Step1:Removing ‘10’ element from the Queue
Step2:Removing ‘20’ element from the Queue

The above insertions and deletions are done as like normal QUEUE. Now we can see the
insertions and deletions are not doing by the normal QUEUE….they are:
Inserting using Front:
Step1: inserting ‘60’ element using Front

Step2: inserting ‘70’ element using Front

Deletion from Rear:

Step1:Deleting ‘50’ element from Rear

Step2: Deleting ‘40’ and ‘30’ elements from Rear

Priority Queue
Often the items added to a queue have a priority associated with them; this priority determines the
order in which they are removed from the queue. Higher priority items are removed first. Such a
queue is said to be priority queue. Priority queues are used in Process Control Systems.

Applications:
Band width management: pq can be used to manage the limited resources such as band width on
transmission line from a network router
Discrete event simulation: pq is to manage events in a discrete event simulation. The events are
added to the queue with their simulation time used as priority
Relationship to store the algorithms: the semantics of pq naturally suggested to storing methods (heap
sort)

LINKED LIST:-
DEF:-”Linked list is a dynamic and linear data structure”. A linked list is a list of elements in which the elements
of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit
link field, that is, by storing the address of the next element in the link field of the previous element.
Dynamic Allocation:-
The process of allocating memory at runtime is known as dynamic allocation.
Dynamic memory management techniques allow us to allocate additional memory space or to release unwanted
space at run time.
Linked list is one of the basic types of dynamic data structures.
It provides flexibility in adding, deleting or rearranging data items at runtime.
Dynamic memory management techniques use the memory management functions which are used for
allocating and freeing memory during program execution.
Types of linked list:-
Singly Linked List
Doubly Linked List
Circular Linked List

There are three common types of Linked List.

Singly linked list:-
In this type of linked list two nodes are linked with each other in sequential linear manner. Movement in
forward direction is possible. Hence it is also called as linear linked list or one way list.
The diagrammatic representation of a single linked list is as follows:

Double linked list: -

A double linked list is one in which all nodes are linked together by multiple links. Each node in a double linked
list has three parts. Two pointers one which points to left and other which points to right and third part is a data
part. In this list we can traverse in forward and backward direction.
The diagrammatic representation of this list is as follows.
Circular linked list :-Circular linked list is one which has no beginning and no end. A single linked list can be
made a circular linked list by simply storing the address of last node to the first node of the list.
The diagrammatic representation of this list is as follows.

Advantatages of linked list:-

Some of the advantages of linked list are in the following ways.
Linked list can be increased or decreased because of dynamic data structure.
Linked list have efficient memory utilization (dynamic memory allocation)
Insertion and deletion easily performed.
Many complex applications can be easily carried out with linked list.

Faster Access time, can be expanded in constant time without memory overhead

Disadvantages of linked list:-

It occupy more space because every node contain a pointer to share the address of next node
Searching a particular element in a list is a time consuming one.
Applications of linked list:-
Linked list are used to implement data structures such as stacks, queues, trees and
graphs
Linked list are used to represent very large numbers and operations of large number.
Linked list are used to represent to represent manipulate polynomial.
Array VS. LinkedList
ARRAY LINKED LIST
1. An array is a collection of elements having 1. Linked List is an ordered collection of
same data type with common name. elements which are connected by links
or pointers.
2. In Array, elements can be accessed using 2. In Linked List, elements can be
index or subscript value i.e., elements can accessed accesses sequentially and
be accessed randomly. So array provides accessing element takes order of n
fasterrandom access. O(n) times.

3. In Array, elements are stored in consecutive 3. In Linked List, elements can be stored
memory locations. at any available place as address of
node is stored in previous node.
4. Insertion & Deletion takes more time in array 4. Insertion & Deletions are fast and easy
as elements are stored in consecutive memory in linked list as only value of pointer is
locations. needed to change.
5. In Linked List memory is allocated at
5. In Array memory is allocated at compile time runtime i.e., Dynamic Memory
i.e., static memory allocation. Allocation.
6. Linked List can be single, double or
6. Array can be single dimensional, two circular linked list.
dimensional or multi-dimensional. 7. In Linked List location or address is
7. In Array each element is independent, no stored in the link part of previous
connection with previous element or with its element or node.
location. 8. In Linked List, adjacency between the
8. In Array no pointers are used like linked list. elements is maintained using pointers
So, no need of extra space in memory for or links. So pointers are used for that
pointer. extra memory space is needed.

Singly linked list:

A single linked list is a very flexible dynamic data structure. Here items can be added or deleted from any
position. A simple way to represent a linked list to expand each node that contains link or pointers to the next
node. Each node consists of TWO parts Namely link part and Data part

Operations on a single linked list:-

The operations that are performing on a single linked list are in the following ways.
.Create a list
.Insert an element into the list
.Delete an element from the list
.Traverse a list
Create a list: -To create a linked list first of all we have to check whether the list is empty or not. Initially the
value of a header will be null. If the header is null then create new node and assign the address of the node to
header. If the header is not null then established the links between last existing and the new node.
Algorithm:-
Step 1:- start
Step 2:- Create a node New node->data=element
New node->next=null
Step 3:- if (header ==null) then
Header=new node else
Step 4:-p=header
Step 5:-repeat
step 6 until p->next=null
Step 6:-p=p->next
Step 7:- p->next=new node
Step 8:- End
Inserting an element into the list:-
Insertion in a linked list can be placed at three positions in a list. While inserting a node into the list we have to
know the location where the node is to be inserted
i . Insertion at the front of list.
ii.Insertion in the middle of the list
iii.Insertion at the end of the list.

Inserting an elemnent at front of the list:-Insertion of a node can be placed at the beginning of the list which
in turn header points to this node. Before inserting a node we have to check whether header is null or not. If it is
null then new node itself is the first node .Otherwise we can place new node just before existing nodes.

Algorithm:- Step 1:- start

Step 2:-Create a newnode Newnode->data=element
Newnode->next=null
Step 3:-if (head ==null) then Head=newnode
else
Step 4:-Newnode ->next=head Step 5:-Head=newnode
Step 6:- End

Insertion at the end of the list:-

Insertion at the end of the list is very simple just locate the last node pointer and place the node in the
pointer->next. If the list is empty then the new node becomes first node. If the list is non- e mpty then the last
node pointer contains the address of new node & new node next contains null value.
Algorithm:-
Step 1:-start
Step 2:-Create a new node
New node->data=element New node->next=null
Step 3:-if( head==null) then
Head=new node else
Step 4:- p=head
Step 5:- repeat
step 5 until p->next=null
Step 6:- p=p->next
Step 7:-p->next=new node
Step 8:- End
Insertion of the node middle position:-
Inserting an element in a list after a specified position of a node then we have to find out the location of the
specified node or element. If the node which you are going to place is at the beginning then header points to the
new node or if the position you specified is the last node then place new node and it becomes last node.
If not, place it at the middle of the list.
Algorithm:- Step 1:- start
Step 2:-Create a new node
New node->data=element New node->next=null
Step 3:-if (head==null) then
Header=new node else
Step 4:-p=head
Step 5:-repeat
step 6 until p->next=null
Step 6:-if (p->data==element))then
New node->next=p->next
P ->next =new node
Step 7:-p=p ->next
Step 8:- End
Deletion of a node from a list:-

Node can be deleted in THREE places. They are

i .Deletion at beginning of the list.
ii. Deletion at the middle of the list.
iii. Deletion at the end of the list.
Deletion of a node requires a location in the list and disconnecting the address of the node to be deleted.
Suppose we want to delete an element from any position first of all we have to check whether the list is
empty or not.
i. Deletion at beginning of the list:-

Step 1:- start

Step 2:- p=head
Step 3:- head=head->next step 4:- free p
Step 5:- stop
Deletion at the middle of the list:-

Algorithm:- Step 1: Start

Step 2:-p=head , q=head
Step 3:-repeat steps 4 and 5 until ( p->data !=x)Step 4:-q=p Step 5:-p=p->next
Step 6:-q->next = p->next Step 7:-free p;
Step 8:-stop
Deletion at the end of the list:-
Deletion at the end of the list:-Algorithm:-
Step 1:- Start
Step 2:- p=head , q=head
Step 3:-repeat steps 4 and 5 until (p->next != NULL) Step 4:-q=p;
Step 5:-p=p->next Step 6:-free p
Step 7:- q->next=NULL Step 8:-Stop

Traversing of a linked list:-

Traversing a node in the list is possible only in one direction. Traversing of a linked list begins at the first node of
the list. To traverse a linked list we have to create a temporary variable of type node to hold the address of the first
node after compilation of the node it points to next node. It will be continued until the address of the last node
becomes null
Step 1:- start
Step 2:- p=head
Step 3:- repeat the steps 4 & 5 until p! =null Step 4:- print “p->data”;
Step 5:- p=p->next
Step 6:- end
Double linked list
Double linked list is a list in which all the nodes have multiple links that are linked together in some order these
multiple l inks helps us in accessing both previous and successive nodes. Each node in a double linked list has
3 parts.
1. Left pointer(link1) 2. Data part 3. Right pointer(link2)

In double linked list we can insert in both directions.

The pointer pointing to the preceded node is called left link. The pointer pointing the nextnode is called right
link.Structure of double linked list is as follows:
The diagrammatic representation of double linked list is:

Operations on a Double linked list:-

The operations that are performing on a double linked list are in the following ways.

Create a list
Insert an element into the l i s t
Delete an element from the Traverse a list
To create a double linked list first of all we have to check whether the list is empty or not, if it is empty assign a
new node to the header otherwise establish the links between existing and the new node.
Algorithm:-

Step 1:- start

Step 2:- create a node
New node->data=num; New node->left link=null;
New node->right link=null;
Step 3:- if (head = = null) then
head= new node Return;
Step 4:- p=head
Step 5:- Repeat step 6 until p->next=null
Step 6:- p=p->right link

Step 7:- p->right link=new node

New node->left link=p;
Step 8:- end

Insertion in doubly linked list:-

There are three ways for inserting element in list.
1. Insertion at the front of list.
2. Insertion in the middle of the list.
3. Insertion at the end of the list.

a. Insertion of a node at the beginning of the list:-

Elements can be inserted at the beginning. Before insertion we have to check whether the header is empty or
not, if it is empty assigned the new node to the header otherwise assign the starting node address to the new
node and the new node left link address to the starting node. Finally the new node assign with pointers.
Algorithm:-
Step 1:-start
Step 2:-create a new node New node->data=value;

New node->left link=null;

New node->right link=null;
Step 3:-if (head = = null) then
head=New node
Step 4:- else
New node->right link=head head->left ink=new node head=new node
step 5:- stop

a. Insertion of a node at end of the list:-

Elements can be inserted at the end. Before insertion we have to check whether the headeris empty or not,
if it is empty assigned the new node to the header otherwise assign the last node address to the new node and the
new node left link address to the previous node.

Algorithm- Step 1:- start

Step 2:- Create a node
New node->data=num;
New node->left link=null;
New node->right link=null
Step 3:-if( header ==null) then
Header=new node else
Step 4:-p=header
Step 5:-repeat step 6 until p -> right link=null
Step 6:-p=p -> right link
Step 7:-p -> right link =new node
newnode -> left link =p newnode -> rightlink=NULL
Step 8: End
c) Insertion of a node at the Middle of the list:-
In this we first search element is there or not. It is Found then insert a new node and assign that address to the
previous node and next node. Otherwise to display element not found.

Step 1:- start

Step 2:- Create a node
New node->data=element
New node->left link=null newnode->right link =NULL
Step 3:- if (head==null) then
Head=new node
else
Step 4:- p=head:
step 5:-Repeat step 6 until (p->data!= item)
Step 6:- p=p->rightlink
step 7:-newnode->right link=p->right link newnode->leftlink =p
newnode->rightlink->leftlink=newnode
Step 8:- End

Deletion:-
In a double linked list, the deletion operation can be performed in three ways as follows...
Deleting from Beginning of the list
Deleting from End of the list
Deleting a Specific Node
a.Deleting from Beginning of the list:-
Node can be deleted from the front. Replace the START pointer to next node and release the links
from the first node.
Algorithm :-
Start
If (head==null)
print “no nodes in doubly linked list”
p=head
head =head->rightlink
free p
head ->leftlink=NULL
Stop

b)Deleting from End of the list:

Node can be deleted at the end of the list. Make last node left link as NULL

Algorithm:-

Start
if(head == null)
print “ D.L.L is empty”
else
p=head
repeat steps 5 until ( p->rightlink !=null) 5.p=p->rightlink
6.p->rightlink->leftlink=null
7.free p 8.Stop

Traversing:- In this we visit each and every element from first element to last element
Algorithm: - Step 1:- START
Step 2:- set p=head;
Step 3:- repeat the step 4 until p!= null Step 4:- print (p->data)
Step 5:- p=p->rightlink
Step 4:- STOP

Advantages:
We can traverse in both directions i.e. from starting to end and as well as from end to starting.
It is easy to reverse the linked list.
If we are at a node, then we can go to any node. But in linear linked list, it is not possible to reach the
previous node.
Disadvantages:
It requires more space per space per node because one extra field is required for pointer to previous
node.
 Insertion and deletion take more time than linear linked list because more pointer operations are
required than linear linked list.

Circular linked list

Circular linked list is a sequence of elements in which every element has link to its next element in the sequence
where the last node points to first node. That means circular linked list is similar to the single linked list except
that the last node points to the first node in the list
Circular linked list of two types
i .Single circular linked list ii.Double circular linked list
i.Single circular linked list:-
Example:-

Double circular linked

list:-example:-
Operations on Single circular linked list:-
In a circular linked list, we perform the following operations...
Insertion
Deletion
Display
insertion:-
In a circular linked list, the insertion operation can be performed in three ways. They are as follows...
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list
Inserting At Beginning of the list
Algorithm:-
Create new node PTR
Set the INFO field of PTR
If list have no node i.e. [TAIL == NULL]
TAIL = PTR
PTR->NEXT = PTR [PTR will point to itself]
Else
PTR->NEXT = TAIL->NEXT [PTR’s next will point to first node]
TAIL->NEXT = PTR [TAIL’s next pointer will point to PTR]

Inserting At End of the list:-

Node can be added at the end of the list.
Create new node PTR
Set the INFO field of PTR
If list have no node i.e. [TAIL == NULL]
TAIL = PTR
PTR->NEXT = PTR [PTR will point to itself]
Else
PTR->NEXT = TAIL->NEXT [PTR will point to first node]
TAIL->NEXT = PTR [last node will point to PTR]
TAIL = PTR [TAIL will point to PTR which is now last node]
Inserting At Specific location in the list:-
Node can be inserted at any specified position. First of all we have to check the element in the list
whether it is there or not.

Algorithm:-
Create new node PTR
Set the info field of PTR
If list have no nodes i.e. (TAIL == NULL)
If (POS == 1)
Set PTR->NEXT = PTR
Set TAIL = PTR
Else
Invalid POS. Node can’t be inserted

Else if (POS == 1) (Now list is not empty also)

Set PTR->NEXT = TAIL->NEXT
Set TAIL->NEXT = PTR
Else

Set TEMP = TAIL->NEXT

Traverse the list for (POS-1)th node of list into TEMP
If TEMP == TAIL
Set PTR->NEXT = TAIL->NEXT Set
TAIL->NEXT = PTR
Set TAIL = PTR
Else
Set PTR->NEXT = TEMP->NEXT
Set TEMP->NEXT = PTR
End If;
End If;
1) Deletion:-
Elements can be deleted in the following ways. First of all we have to check whether the given element is existed
or not. There are three positions to delete an element.
i .Deletion at beginning of the Circular linked list.
ii.Deletion at the middle of the Circular linked list.
iii.Deletion at the end of the Circular linked list.
i. Deletion at beginning of the Circular linked list:- Element can be deleted at thebeginning
Algorithm:-

Declare TEMP
If list have only one node
FREE (TAIL)
TAIL = NULL
else
TEMP = TAIL->NEXT [TEMP will point to first node]
TAIL->NEXT = TAIL->NEXT->NEXT [TAIL’s next will now point to second node]
Free (TEMP) [free the first node]

ii. Deletion at the end of the Circular linked list:-

Element can be deleted at the end of the list.
Algorithm:-
Set TEMP1 = START
If START != NULL
If START->NEXT == NULL
START=START->NEXT
FREE (TEMP1)
Else
Traverse the list so that TEMP1 points to last node andTEMP2 points second last node
TEMP2->NEXT = NULL
FREE (TEMP1)

End If;
iii. Deletion at the s p e c i f i c p o s i t i o n of the Circular linked list:-
Element can be deleted at the end of the list.
Algorithm:-
Set TEMP1 = START
If START != NULL
If START->NEXT == NULL
START=START->NEXT
FREE (TEMP1)
Else
Traverse the list so that TEMP1 points to last node andTEMP2 points second last node
TEMP2->NEXT = NULL
FREE (TEMP1)
End If;

Displaying a circular Linked List

We can use the following steps to display the elements of a circular linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
 Step 5 - Finally display temp
 → data with arrow pointing to head → data.