UNIT–III

QUEUES
Introduction
 Queue is a simple but powerful data structure to solve numerous computer applications.
 It is a linear data structure.

Definition
 A queue is a linear list of elements in which deletion can take place at one end called
FRONT and insertion takes place at the other end called REAR.
 Queues are also called FIFO (First In First Out), since the first element in the queue will
be the first element out of the queue.
 Example  people waiting in queue in a ticket counter

REPRESENTATION OF QUEUES
 Queues may be represented in computer in various ways usually by means of one-way list
or linear arrays.
 We have two pointer variables:
 FRONT  containing location of first element
 REAR  containing location of last element
Example
34 12 56 61 -8

FRONT REAR

Representation of Queue using Arrays

 Array is a data structure that stores a fixed number of elements.
 The size of the array should be fixed prior to using it.
 But the size of the queue keeps on changing as the element are either removed from the
front end or added at the back end.
Array representation of a queue
a[0 a[1 a[2 a[3 a[4 a[5
] ] ] ] ] ]
10 20 30 40 50 60

Size = 6
front back t
t
Representation of Queue using Linked List
 The linked list representation of a queue does not have any restrictions on the number of
elements it can hold.
 The elements in a linked list are allocated dynamically; hence it can grow in size.
 The queue is made empty by assigning NULL to FRONT and BACK.
Linked list representation of a queue
10 20 30

START
front back

OPERATIONS ON QUEUES
 The two basic operations associated with queues are :
1. En-queue operation.
2. De-queue operation.
1
Algorithm for Array Representation of Queue
 In an array with n elements, the array locations are indexed from 0 to n – 1.
 The condition (front = –1) will indicate an empty queue.
 The condition (back = n – 1) will indicate a full queue.
 The front and back are integer variables which stores array index from front end of the
queue and back end of the queue respectively.

Algorithm for ENQ Operation

 The steps in inserting an ITEM at the BACK pointer of the queue (Q) are :
1) If (queue is not full) then
a) Add 1 to BACK pointer
BACK = BACK + 1
b) Store ITEM at BACK pointer location
Q[BACK] = ITEM
2) Otherwise Print “Queue Overflow"
3) Stop.
Algorithm for DEQ Operation
 The steps in deleting an ITEM from the FRONT pointer of the queue (Q) are :
1) If (queue is not empty) then
a) Read ITEM at FRONT pointer location; ITEM = Q[FRONT]
b) Add 1 to FRONT pointer
FRONT = FRONT + 1
2) Otherwise Print “Queue Underflow"
3) Stop.
An empty queue After inserting 3 element

a[0] a[1] a[2] a[3] a[4] a[5] a[ a[ a[ a[ a[ a[

0] 1] 2] 3] 4] 5]
1 2 3
0 0 0
front = –1
back = –1
fro bac
After deleting an element nt k
t
a[0] a[1] a[2] a[3] a[4] a[5]

40 50 60

front back
Algorithm for Linked List Representation of t
Queue
Algorithm for ENQ Operation
 The steps in inserting an ITEM at the BACK pointer of the queue (Q) are :
1) Allocate memory for the new node named TEMP.
2) Store the ITEM in the allocated memory.
TEMP->DATA = ITEM
TEMP->LINK = NULL
3) Setup the BACK pointer.
BACK->LINK = TEMP;
BACK = BACK->LINK;
4) Stop.

Algorithm for DEQ Operation

 The steps in deleting an ITEM from the FRONT pointer of the queue (Q) are :
2
 1) If (FRONT = NULL) then
a) Print “Queue is empty” and Exit
2) Otherwise
a) Create a new node named as TEMP.
b) Assign TEMP = FRONT
c) Store ITEM = TEMP->DATA
d) Assign FRONT = FRONT->LINK
3) Delete TEMP node.
4) Stop.
Before insertion
10 20

START
front back
After insertion temp
10 20 30

After deletion of 30START

front back
20 30

START
front back

VARIOUS QUEUE STRUCTURE

 There are 3 types of various queue structures as:
1. Circular Queue
2. DeQue
3. Priority Queue
CIRCULAR QUEUES
Definition
 Circular queues are the queues implemented in circular form.
 In circular queue, the insertion of a new element is done at the very first location of the
queue, if the last location of the queue is full.
Algorithm for Insertion Operation
 The steps in inserting an ITEM at the BACK pointer of the queue (Q) are :
1) If (FRONT = (BACK % n) + 1 then
a) Print “Queue Overflow”
b) Exit
2) If (FRONT = –1) then Set FRONT = BACK = 0
3) Otherwise BACK = (BACK % n) + 1
4) Store ITEM at BACK pointer location
5) Stop.
Algorithm for Deletion Operation
 The steps in deleting an ITEM from the FRONT pointer of the queue(Q) are :
1) If (FRONT = –1) then
a) Print “ Queue underflow”
b) Exit
2) Read ITEM at FRONT pointer location
3) If (FRONT = BACK) then Set FRONT = BACK = –1
4) Otherwise Set FRONT = ( FRONT % n) + 1
5) Stop.

3
Advantage
 They overcome the problem of unutilized space in linear queue implemented as an array.

Example
Before insertion After insertion
a[0] a[1] a[2] a[3] a[4] a[5]
a[ a[ a[ a[ a[ a[
20 30 40 50 60 0] 1] 2] 3] 4] 5]
7 2 3 4 5 6
0 0 0 0 0 0

front back
bac fro
t
k nt
Before deletion t
After deletion
a[0] a[1] a[2] a[3] a[4] a[5] a[ a[ a[ a[ a[ a[
0] 1] 2] 3] 4] 5]
70 20 30 40 50 60 7 3 4 5 6
0 0 0 0 0

back front bac fro

t k nt
DOUBLE-ENDED QUEUE (DEQUE) t
Definition
 Double-ended queue is also called as deque.
 Deque is a linear list of elements in which insertion and deletion operations are performed at
both the ends.
Representation of Deque
 Deque is maintained by a circular array with pointers LEFT and RIGHT.
Deque representation
q[0] q[1] q[2] q[3] q[4] q[5]
Deletion Insertion
20 30 40
Insertion Deletion

left right
t
 While inserting or deleting elements into the queue, two possibilities that must be
considered are :
1. When an attempt is made to insert an element in a deque which is already full, an
overflow occurs.
2. When an attempt is made to delete an element from a deque which is empty, an
underflow occurs.
Algorithm for Insertion Operation
 The steps in inserting an ITEM into the deque are :
1) If (deque is full) then
a) Print “Deque overflow”
b) Exit
2) If (LEFT = –1 and RIGHT = –1) then Assign LEFT = 0 and RIGHT = 0
3) Otherwise Add 1 to RIGHT pointer
4) Store ITEM at RIGHT pointer location
5) Stop.
Algorithm for Deletion Operation
 The steps in deleting an ITEM into the deque are :
1) If (deque is empty) then
a) Print “Deque underflow”
4
 2) Read the element at LEFT pointer location.
3) Add 1 to LEFT pointer.
4) Stop.

Example
Fig(a) : After insertion of first element Fig(b) : Inserting element at LEFT pointer

q[0] q[1] q[2] q[3] q[4] q[5] q[ q[ q[ q[ q[ q[

0] 1] 2] 3] 4] 5]
10 2 1
0 0

left right left righ

t t
t
Fig(c) : Inserting element at RIGHT pointer Fig(d) : Deleting element at LEFT pointer

q[0] q[1] q[2] q[3] q[4] q[5] q[ q[ q[ q[ q[ q[

0] 1] 2] 3] 4] 5]
20 10 30 1 3
0 0

left right left righ

t t
Types of Deque t
 The two types of deques are:
1. Input-restricted deques
2. Output-restricted deques
 An input-restricted deque is a deque which allows insertions at only one end of the list, but
allows deletions at both ends of the list.
 An output-restricted deque is a deque which allows deletions at only one end of the list, but
allows insertions at both ends of the list.
Representation of input-restricted deque
q[0] q[1] q[2] q[3] q[4] q[5]
Insertion
Deletion 10 20 30 40 50 60
Deletion

left right
t
Representation of output-restricted deque
q[0] q[1] q[2] q[3] q[4] q[5]
Insertion
Insertion 10 20 30 40 50 60
Deletion

left right
t
PRIORITY QUEUE
Definition
 A priority queue is another variation of queue structure. Here, each element has been
assigned a value, called priority of the element, and an element can be inserted or deleted
not only at the ends but at any position on the queue.
 It is used in the batch scheduling applications.
 Model of priority Queue:
5
 1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which
they were added to the queue.

 There are various ways of implementing the structure of a priority queue:

1. Using a simple/circular array
2. Multi-Queue implementation
3. Using a Double Linked list
4. Using a heap tree

Array Representation
 The elements of the array are of struct data type, holding information about the
1. Job to be processed
2. Priority of the job
3. Order in which the elements will be added.
Example
 Let B be the Job with Priority value 3 and Order value 2 and A be the Job with priority
value 4 and order number 1.
q[0] q[1] q[2] q[3] q[4] q[5]

B, 3, 2 A, 4, 1

front back
t
 With this representation, the element will be inserted at the REAR end as usual.
 The deletion operations will be performed in 2 ways:
1. Starting from the FRONT pointer, traverse the array for an element of the highest
priority. Delete this element from the queue. If this is not the FRONT most element,
then it will shift all its trailing elements after the deleted element one stroke each to
fill up the vacant position.
2. Add the element as the REAR. Using a stable sorting algorithm, it sorts the elements
of the Queue so that the highest priority element is at the FRONT end. When a
deletion is required, delete it from the FRONT end only.
Linked List Representation
 Priority queue can be represented by single linked list.
 Each node in the single linked list contains 3 items of information :
1. Information field
2. Priority number field
3. Link field.
Example
 Let B be the Job with Priority value 3 and Order value 2 and A be the Job with priority
value 4 and order number 1.
START
B 3 A 4

Multi-queue Implementation
 The multi-queue implementation assumes N different priority values.
 For each priority PI, there are two pointers FI and BI corresponding to FRONT and BACK
pointer respectively.
 The elements between FI and BI are all of the equal priority value PI.
 In multiple-queue with simple queues representation, for each priority value a simple queue
is to be maintained. The element will be added into a particular queue depending on its
priority.
6
 Representation of multiple-queue with simple queues

F1 B1
t
…

Priority P1
F2 B2
t
…

Priority P2
Fn Bn
t
…

Priority Pn

APPLICATION OF QUEUES
 There are various applications of Queues as:
1. CPU Scheduling in Multiprogramming
2. Round Robin Algorithm
3. Simulation
SIMULATION
 Simulation is a modeling of a real life situation in the form of a computer program.
 The main objective of a simulation program is to study the real life situation under the
control of various parameters which affect the real problem.
 Based on the result of simulation, actual problem can be solved in an optimized way.
 An Advantage of simulation is that, Simulation is to experiment the danger area.
System
 Any process or simulation that is to be simulated is called a System.
 A System is a collection of interconnected objects which accepts zero or more inputs and
produces at least one output.
 The outline of the system and classification of systems is as follows:

Input Interconnected Objects to Output

provide Functionality

Classification of Systems
Discrete System
 A system is discrete, if the input and output parameters are of discrete values.
Continuous System
 A system is continuous, if the input and output parameters are of continuous values.
Deterministic System
 A system is deterministic, if from a given set of input and initial condition of the system
final outcome can be predicted.
Stochastic System
 It is based on the randomness: its behavior cannot be predicted.
Simulation Model
Event-Driven Simulation
 In Event-Driven Simulation, system changes its state whenever a new event arrives to the
system or exists from the system.
Time-Driven Simulation
 In Time-Driven Simulation, system changes its states with the change of time.

7
 CPU SCHEDULING IN MULTIPROGRAMMING ENVIRONMENT
 In this, a single CPU has to server more than one program simultaneously.
 Consider a multiprogramming environment where possible jobs to the CPU are categorized
into 3 groups:
1. Interrupt to be serviced
2. Interactive users to be serviced
3. Batch jobs to be serviced
 One way to implement complex scheduling is to classify the workload according to its
characteristics and to maintain separate process queues.
 This process is called Multi-Level Queues Scheduling.
 Process will be assigned to their respective queues.
 CPU will then service the process as per the priority of the queues.
 The process from the highest priority Queue is serviced until the queue becomes empty.
 Then CPU switches to the Queue of interactive processes which is medium-priority.
 A lower-priority process may be pre-empted by a higher-priority arrival in one of the upper-
level Queues.
 Multi-Level feedback Queue strategy allows a process to move between Queues.
 Example  Consider a multi-level feedback queue strategy with 3 Queues Q1, Q2 and Q3.

Q1
t=10

t=20
Q2

FCFS
Q3 To Q1
Description
 A process entering the system is put in Queue Q1.
 A process in Q1 is given a time quantum T of 10ms.
 If it does not finish within this time, it is moved to the tail of Queue Q2.
 If Q2 is empty, the process at the FRONT of Queue Q2 is given a time quantum t of 20ms.
 If it does not complete within this time quantum, it is pre-empted and put into Queue Q3.
 Processes in Queue Q3 are serviced only when Queues Q1 and Q2 are empty.
 CPU first executes all processes in Queue Q1.
 Only when Q1 is empty, it will execute all processes in Queue Q2.
 Processes which need more than 10ms, but less than or equal to 20ms are also served
quickly.
Drawback
 Higher-Priority Queue is very high.
 Lower-Priority Queue may starve for a long time.

ROUND ROBIN ALGORITHM

 Round-robin (RR) algorithm is designed for time-sharing systems.
 It uses circular queue.
 Consider there are n processes P1, P2, …, Pn required to be executed by the CPU.
 Different processes require different execution time.
 RR algorithm first decides a small unit of time called a time quantum or time slice.
 CPU starts executing the process P1.
 Afterwards CPU switches to P2 and so on.
 When the CPU reaches the end of time quantum of Pn, it returns to P1 and the same process
will be continued with its execution.

8
  Turn around time of a process is the time of its completion minus the time of its arrival.
 In time-sharing system, any process may arrive at any instant of time.
 All the processes currently under executions are maintained in a queue.
 When a process finishes its execution, that process is deleted from the queue and whenever
a new process arrives, it is inserted at the tail of the queue
and waits for its turn. Process Execution time
Example P1 10 Sec
 Consider the table with 3 processes P1, P2 and P3 with their P2 15 Sec
execution time. P3 5 Sec
 The total CPU time required is 30 Seconds.
 Let us assume a time quantum of 4 Seconds.
 The RR scheduling is as follows :
P3 finished
P1 finished

P1 P2 P3 P1 P2 P3 P1 P2 P3

Time 0 4 8 12 16 20 21 23 27 30
(Sec)
Advantage
 Reduce the average turn around time.

LINKED LIST
Definition
 A linked list is an ordered collection of finite, homogeneous data elements called nodes
where the linear order is maintained by means of links or pointers.
 The general representation of a linked list is as follows:

NODE
DATA LINK Link to the next node

 The structure definition for a single linked list is

struct node
{
int data ;
struct node *link ;
};
 The pointer of the last node contains a special value called the null pointer.
 The null pointer is denoted by a slash ( / ) in the diagram.
 The linked list contains a list pointer variable called START (or head node), which contains
the address of the first node in the list.
 Depending on the requirements the pointers are maintained, the linked list can be
categorized as:
1. Single linked list
2. Circular linked list
3. Double linked list
SINGLE LINKED LIST
Definition
 In a single linked list, each node contains data and a single link which attaches it to the next
node in the [Link] is also called as one-way list.
Example START node 0 node 1 node 2
10 20 30
9
 REPRESENTATION OF A LINKED LIST IN MEMORY
 There are two ways to represent a linked list in memory :
1. Static representation using arrays.
2. Dynamic representation using free pool of storage.

STATIC REPRESENTATION OF LINKED LIST

 The static representation of a single linked list maintains two arrays:
a. One array for data (DATA).
b. Another array for links (LINK).
 List also requires variables such as:
1. START  Contains address of first node in the list.
2. NULL  Indicates the end of the list (NULL = 0).
Example
 Three data values (10, 29 and 30) are stored in the linked list.
 The value 10 is stored at memory address 104H, 20 at 100H and 30 at 106H.
 The START node points to the first node in the list, which points to the address 104H.

Static representation of linked list

START DATA LINK
100H 20 106
102H –
104H 10 100
106H 30 NULL
108H … …
Array of pointers
Memory location

DYNAMIC REPRESENTATION OF LINKED LIST

 The efficient way of representing a linked list is using free pool of storage.
 In this method, there is
a. A memory bank, which is a collection of free memory spaces.
b. A memory manager, which is a program.
 Whenever a new node is to be created in a linked list,
1) The request is placed to the memory manager.
2) The memory manager will search the memory bank for the block of memory
requested.
3) If found, the memory manager grants the block to the linked list.
 A program called garbage collector is used to return the unused node to the memory bank.
 This type of memory management is known as dynamic memory management.
Example
Dynamic representation of linked list
START node 0 node 1 node 2
10 20 30

15

new node

10
 OPERATIONS ON A SINGLE LINKED LIST
 The operations on single linked list are :
1. Traversing a list.
2. Insertion of a node into a list.
3. Deletion of a node into a list.
4. Copy a linked list to make a duplicate list.
5. Merging two linked list into a larger list.
6. Searching for an element in a list.

TRAVERSING
 To traverse a single linked list, every node in the list starting from the first node to the last
node to be visited.
Algorithm
1. ptr = [Link]
2. While (ptr ≠ NULL) do
(a) PROCESS (ptr)
(b) ptr = [Link]
3. Endwhile
4. Stop

Example
HEADER node 0
10
node 1 node 2
15 20
node 3
30
INSERTION
 Insertion of a node into a single linked list can be done in three ways :
a. Insertion of a node at the beginning of a list.
b. Insertion of a node at the end of a list.
c. Insertion of a node at the middle of a list.

Insertion of a Node at the Beginning of a List

 Let ITEM be the element to be inserted at the beginning of the list.
Algorithm
 The steps in insertion of a node at the beginning of a linked list are :
1) Allocate memory for a new node named TEMP.
2) Store TEMP–>DATA = ITEM
3) Assign TEMP–>LINK = START
4) Assign START = TEMP
5) Stop.
Example
 Let 50 be the element to be inserted at the beginning of the list.
Before insertion
START node
0
10

After insertion
START node 0 node 1
50 10

11
Insertion of a Node at the End of a List
 Let ITEM be the element to be inserted at the end of the list.
Algorithm
 The steps in insertion of a node at the end of a linked list are :
1) Traverse to the last node in the list and store the address of the last node in Q.
2) Allocate memory for a new node named TEMP.
3) Store TEMP–>DATA = ITEM
4) Assign TEMP–>LINK = NULL
5) Assign Q–>LINK = TEMP
6) Stop.
Example
 Let 30 be the element to be inserted at the end of the list.
Before insertion
START node 0 node 1
50 10

After insertion
START node 0 node 1 node 2
50 10 30

Insertion of a Node at the Middle of a List

 Let ITEM be the element to be inserted at the middle of the list at position (POS).
Algorithm
 The steps to insert a node at the middle of a linked list are :
1) Traverse to the node at specified position POS in the list and store address of this
node in Q.
2) Allocate memory for a new node named TEMP.
3) Store TEMP–>DATA = ITEM
4) Store TEMP–>LINK = Q–>LINK
5) Assign Q–>LINK = TEMP
6) Stop.
Example
 Let 75 be the element to be inserted at the middle of the list at position POS = 2.
Before insertion
START node 0 node 1 node 2
50 10 30

After insertion
START node 0 node 1 node 2 node 3
50 10 75 30

DELETION
 Like insertions, there are also various cases of deletion:
i. Deletion at the front of the list
ii. Deletion at the end of the list
iii. Deletion at any position of the list
Deletion at front
 The following algorithm is used to delete a node from a single linked list at the front:
1. Ptr = [Link]
2. If (ptr = NULL)

12
 i. Print “The list is empty: No Deletion”
ii. Exit
3. Else
i. Ptr1 = [Link]
ii. [Link] = ptr1
iii. RETURNNODE (ptr)
4. End if
5. Stop
Deletion at end
 The following algorithm is used to delete a node from a single linked list at the end:
1) Ptr = HEADER
2) If ([Link] = NULL)
i) Print “The list is empty: No Deletion”
ii) Exit
3) Else
4) While ([Link] ≠ NULL) do
i) ptr1 = ptr
ii) ptr = [Link]
5) End while
6) [Link] = NULL
7) RETURNNODE (ptr)
8) End if
9) Stop
Deletion at any specified point
 The following algorithm is used to delete a node from a single linked list at any position in
the list:
1) Ptr1 = HEADER
2) Ptr = [Link]
3) While (ptr ≠ NULL) do
a) If ([Link] ≠ KEY) then
i) Ptr1 = ptr
ii) Ptr = [Link]
b) Else
i) [Link] = [Link]
ii) RETURNNODE (ptr)
iii) Exit
c) End if
4) End while
5) If (ptr = NULL) then
a) Print “Node with KEY does not exist: No deletion”
6) End if
7) Stop
COPYING
Algorithm
 The steps in copying a single linked list are :
1. Ptr = HEADER
2. HEADER1 = GETNODE (NODE)
3. Ptr1 = HEADER1
4. [Link] = NULL
5. While (ptr ≠ NULL) do
i. New = GETNODE (NODE)
ii. [Link] = [Link]
iii. [Link] = new
iv. [Link] = NULL
v. Ptr1 = new
13
 vi. Ptr = [Link]
6. End while
7. Stop
Example
Original linked list
START node 0 node 1
50 10

Copied linked list

START node 0 node 1
50 10

MERGING
 Merging can be done as follows :
1. Ptr = HEADER1
2. While ([Link] ≠ NULL) do // Move to the last node in the list L1
i. Ptr = [Link]
3. End while
4. [Link] = [Link] // Last node in L1 points to the first node in L2
5. RETURNNODE (HEADER2) // Return the header node to the memory bank
6. HEADER = HEADER1 // HEADER becomes the header node of the merged list
7. Stop
Example
First linked list
START node 0 node 1
10 20

Second linked list

START node 0 node 1
50 60

After merging
START node 0 node 1 node 2 node 3
10 20 50 60

SEARCHING
 Searching means finding information in a given linked list.
o Ptr = [Link] // Start from the first node
o Flag = 0, LOCATION = NULL
o While (ptr ≠ NULL) and (flag = 0) do
 If ([Link] = KEY) then
 Flag = 1
 LOCATION = ptr
 Return (LOCATION)
 Else
 Ptr = [Link] // Move to the next node
 End if
o End while
o If (ptr = NULL) then
14
  Print “Search is unsuccessful”
o End if
o Stop
Example
 Let 20 be the element to be searched in a list.
Linked list
START node 0 node 1
10 20

After searching
Search successful

DOUBLE LINKED LIST (DLL)

Definition
 In doubly linked list, each node contains data and two links, one pointing to the previous
node and one pointing to the next node. It is also called as two-way list.
 It can be traversed in two directions :
1. From the beginning of the list to the end of the list in forward direction.
2. From the end of the list to the beginning of the list in backward direction.
 Each node contains three parts :
1. An information (DATA) field, which contains the data.
2. A pointer field RLINK, which contains the location of the next node in the list.
3. A pointer field LLINK, which contains the location of the preceding node in the
list.

Structure of a node in a DLL

llink data rlink

Previous Data field Next pointer

pointer field field
Example
HEADER node 0 node 1 node 2
10 20 30

Operations on a Double Linked List

 All the operations of a single-linked list can be implemented on double linked list
efficiently.
INSERTION
 Insertion of a node into a double linked list can be done in three ways :
1. Insertion of a node at the beginning of a list.
2. Insertion of a node at the end of a list.
3. Insertion of a node at the middle of a list.
Insertion of a Node at the Beginning of a List
 The following algorithm illustrates insertion of a node at the front in the double linked list:
1. ptr = [Link]
2. new = GETNODE(NODE)
3. If (new ≠ NULL) then
a. [Link] = HEADER
b. [Link] = new
c. [Link] = ptr
d. [Link] = new
e. [Link] = X

15
 4. Else
a. Print “unable to allocate memory: Insertion is not possible”
5. End if
6. Stop
Example
 Let 50 be the element to be inserted at the beginning of the list.
Before insertion
START Ptr
node 0
10

After insertion
START New Ptr
node 0 node 1
50 10

Insertion of a Node at the End of a List

 The following algorithm illustrates insertion of a node at the end in the double linked list:
1. ptr = HEADER
2. While ([Link] ¿ NULL) do
 ptr = [Link]
3. End While
4. new = GETNODE(NODE)
5. If (new ≠ NULL) then
 [Link] = ptr
 [Link] = new
 [Link] = NULL
 [Link] = X
6. Else
 Print” Unable to allocate memory: Insertion is not possible”
7. End if
8. Stop
Example
 Let 30 be the element to be inserted at the end of the list.
Before insertion
START node 0 node 1
50 10

After insertion
START node 0 Ptr node New
1 node 2
50 10 30

Insertion of a Node at the Middle of a List

The following algorithm illustrates insertion of a node at the middle in the double linked list:
1. ptr = HEADER
2. While ([Link] ¿ KEY) and ([Link] ¿ NULL) do
 ptr = [Link]
3. End While
4. new = GETNODE(NODE)
5. If (new = NULL) then
 Print “Memory not available”
 Exit
6. Endif
7. If ([Link] = NULL)
16
  [Link] = ptr
 [Link]= new
 [Link] = NULL
 [Link] = X
8. else
 ptr1 = [Link]
 [Link] = ptr
 [Link] = ptr1
 [Link] = new
 [Link]= new
 ptr = new
 [Link] = X
9. Endif
10. Stop
Example
 Let 75 be the element to be inserted at the middle of the list at position POS = 1.
Before insertion
START node 0 Ptr1
node 1
50 10

After insertion
START Ptr node node 1 Ptr
0 1node 2
50 75 10

DELETION
 The three cases of deletion are:
Deletion of a Node at the Beginning of a List
 The steps in deleting a node from a double linked list are :
1) Store the address of first node in P
2) If (P–>DATA = ITEM) then
a) The first node is made to point to the second node
P = P–>RLINK
b) The value NULL is stored in the LLINK part of the second node
P–>LLINK = NULL
3) Stop.
Example
 Let 50 be the element to be deleted from the list.
Before deletion
START node 0 node 1 node 2
50 75 10

After deletion
START node 0 node 1
70 10

Deletion of a Node at the End of a List

 The steps in deleting a node from a double linked list are :
1) Traverse to the last node in the list and store the address of the last node in Q
2) If (Q–>DATA = ITEM) then
a) The value NULL is stored in RLINK part of the second last node
(Q–>LLINK)–>RLINK = NULL
3) Stop.
17
Example
 Let 10 be the element to be deleted from the list.
Before deletion
START node 0 node 1 node 2
50 75 10

After deletion
START node 0 node 1
50 75

Deletion of a Node at the Middle of a List

 The steps in deleting a node at the middle of a double linked list are :
1) Traverse to the node to be deleted in the list and store address of this node in Q.
2) If (Q–>DATA = ITEM) then
a) The address of the next node is stored in RLINK part of the previous node.
(Q–>LLINK)–>RLINK = Q–>RLINK
b) The address of the previous node is stored in LLINK part of the next node.
(Q–>RLINK)–>LLINK = Q–>LLINK
3) Stop.
Example
 Let 75 be the element to be deleted from the list.
Before deletion
START node 0 Q node node 2
1
50 75 10

After deletion
START node 0 node 1
50 10

CIRCULAR DOUBLE LINKED LIST

 The advantages of both double linked list and circular linked list are incorporated into
another list structure which is called circular double linked list and it is known to be the best
of its kind.
 A circular Double linked list is a linked list, where
1. The RLINK pointer of the last node will point to the head node of the list.
2. The LLINK pointer of the first node will point to the last node of the list.
Example

START node 0 node 1 node 2

10 20 30

 In case of empty list, both LLINK and RLINK of the header point to itself.

Operations on Circular Double Linked list

 All regular operations can be implemented very easily with circular double linked list.
 The algorithm to sort a circular double linked list is as follows:
1. ptr_beg = [Link]

18
 2. ptr_end = [Link]
3. While (ptr_beg ¿ ptr_end) do
i. ptr1 = ptr_beg
ii. ptr2 = [Link]
iii. While (ptr2 ¿ ptr_end) do
1. If ORDER ([Link], [Link]) = FALSE Then
a. SWAP (ptr1, ptr2)
2. End If
3. ptr1 = [Link]
4. ptr2 = [Link]
iv. End While
v. Ptr_end = ptr_end.LLINK
4. End While
5. Stop
APPLICATIONS OF LINKED LISTS
 The common applications of linked list include:
1. Sparse matrix manipulation
2. Polynomial representation
3. Dynamic storage management
SPARSE MATRIX MANIPULATION
 A sparse matrix is a two-dimensional array having the value of majority
elements as null.
 Linked lists are the best data structure to store sparse matrix manipulation.
Structure of a node to represent sparse matrices
Rowlink
i j

DATA

ROWLINK
Collink

 The field ‘i’ and ‘j’ store the row and column numbers for a matrix element
respectively.
 ‘DATA’ field stores the matrix element at the i-th row and j-th column
 The ‘ROWLINK’ points to the next node in the same row and ‘COLLINK’ points to the
next node in the same column.
 A sparse matrix and its linked list representation is as follows:
Example
 Consider the following sparse matrix of order 0 10 0 0 4 x 4.
0 0 20 30
0 0 0 0
10 50 0 0
 The multiple linked list representing the sparse matrix is

0 1 10
NULL

1 2 20 1 3 30
NULL NULL NULL

19

NULL
 3 0 10 3 1 50
NULL NULL NULL

 In the above diagram, there are four pointers to the first elements of each column and four
pointers to the first elements of each row. Each non-zero element is represented by a node.
 A node is connected with the next element in the same column and also the next element in
the same row.
 In case if all the elements of a tow/column are zero, the corresponding pointers to the first
element will be NULL.
POLYNOMIAL REPRESENTATION
 An important application of linked list is to represent polynomials and their manipulations.
 Main advantage of linked list for polynomial representation is that it can accommodate a
number of polynomials of growing sizes so that their combined size does not exceed the
total memory available.
 It contain more than one term.
 Linked lists are widely used to represent and manipulate polynomials.
 Polynomials are the expressions containing number of terms with non-zero co-efficient and
exponents.
 In the linked list representation of polynomials, each term is considered as node.
 Each node contains 3 fields as:
1. Co-Efficient holds the value of the co-efficient of a term.
2. Exponent Field  contains the expression value of that term
3. Link Field  contains the address of the next term in the
polynomial.

 The Polynomial node COEFF EXP LINK structure is:

Example
 Consider the following polynomial  5x3 – 10x2 + 3x + 12
 Here, (5, –10, 3, 12) are the coefficients and (3, 2, 1, 0) are the exponents.
 In data structure, a polynomial can be represented as a list of nodes, where each node
consists of a coefficient and an exponent.
Representation of Polynomials
 Polynomials can be represented in two ways : Using arrays, Using linked list.

POLYNOMIAL ADDITION
 Let P1 and P2 be the two given polynomials to be added and P3 be the resultant polynomial.
Algorithm
 The steps in performing addition of the two given polynomials are :
1) Traverse the linked list till the end of any one of the polynomial is reached.
2) While doing this traversal, the polynomials are compared on term-by-term basis.
a) If the exponents of two terms being compared are equal, then their
coefficients are added and their result is stored in polynomial P3.
b) If the exponents of two terms are not equal, then the term with bigger
exponent is stored in the polynomial P3.
3) While traversing, if the end of one of the polynomial list is reached, then the
control breaks out of the loop.
4) The remaining terms of other list are added to the resultant polynomial P3.
5) Stop.
Example
 Consider the first polynomial P1  5x2 + 3x + 6
 Its linked list representation is

20
 START
5 2 3 1 6 0

 Consider the second polynomial P2  2x3 + 2x2 – x – 3

 Its linked list representation is:
START
2 3 2 2 –1 1 –3 0

 The resultant polynomial P3 is  2x3 + 7x2 + 2x + 3

 Its linked list representation is
START
2 3 7 2 2 1 3 0

DYNAMIC STORAGE MANAGEMENT

Discuss about the storage management in detail. (10 marks)
 Basic task of any program is to manipulate data.
 These data should be stored in memory during their manipulation.
 There are two memory management schemes for the storage allocation of data:
1. Static storage management
2. Dynamic storage management
Static Memory Management
 In case of static storage management, the net amount of memory required for various data
for a program is allocated before the starting of the execution of the program.
 Once the memory is allocated, it neither can be extended nor can be returned to the memory
bank for the use of other programs at the same time.
Dynamic Memory Management
 The dynamic storage management allows the user to allocate and deallocate the memory as
per the necessity during the execution of the programs.
 It is suitable in multiprogramming as well as single-user environment
 Operating system generally provides the service of Dynamic Memory Management. The
data structure for implementing such a scheme is linked list.

Principles of dynamic memory management schemes

 The principles of dynamic memory management scheme are :
1. Allocation schemes
 It describes how a request for a memory block will be serviced.
 There are two methods :
a) Fixed block allocation
b) Variable block allocation
i) First-fit method
ii) Next-fit method
iii) Best-fit method
iv) Worst-fit method.
2. Deallocation schemes
 It describes how to return a memory block to the memory bank, whenever
it is no more required.
 There are two methods :
a) Random deallocation
b) Ordered deallocation.

21