Data Structures made

Simple

Dr. V. Kabeer
CONTENTS

1 module 1 - introduction 5
1.1 Introduction 5
1.2 What is data structure? 5
1.2.1 Definition of Data Structure 7
1.3 Classification of Data Structures 7
1.4 Significance of Data Structures 7
1.5 Operations on Data Structure 8
1.6 What is mathematical modelling? 9
1.7 ADT - Abstract Data Types 10
2 module 2 - linear data structures 11
2.1 Introduction 11
2.2 Arrays 13
2.2.1 Definition 14
2.2.2 Memory storage & Index 15
2.2.3 Array Representation 16
3 module 3 - stack & queues 19
3.1 Stack 19
3.1.1 Implementation of stacks 20
3.1.2 Applications of Stack 22
3.1.3 Simulation of recursion using stack 23
3.2 Queues 26
3.2.1 Implementation of Queue Using Ar-
ray 27
3.2.2 Implementation of Queue Using Ar-
ray 29
3.3 Circular Queue 30
3.3.1 Priority Queues 32
4 module 4 - linked lists 35

3
 4.1 Lists 35
4.1.1 List versus Array 35
4.1.2 Implementation of linked lists 36
4.2 Doubly Linked List 40
4.3 Circular Linked List 41
5 module 5 - nonlinear data structures 47
5.1 Trees 47
5.1.1 Implementation of tree 49
5.2 Binary Trees 51
5.2.1 Implementation of Binary Tree 53
5.2.2 Binary Tree Traversals 55
5.3 Binary Search Trees (BST) 59
5.3.1 Insertion of a node into a Binary
Search Tree 61
5.3.2 Deletion of a node from a Binary
Search Tree 62
5.3.3 BST Searching 64
5.4 Searching 65
5.5 Sorting 69
5.5.1 Insertion Sort 70
5.5.2 Bubble Sort 71
5.5.3 Quick Sort 71

4
 1
MODULE 1 - INTRODUCTION

1.1 introduction

The role of computers in problem solving is well known.

Whenever we wanted to solve problems with the help of
computers we think about the programs and algorithms.
An algorithm is a step by step procedure to be followed
so as to solve certain task whereas programs are imple-
mentation of algorithms in a specific programming lan-
guage. Apart from algorithms data structure is another
entity which plays further role in design of solutions to
the problems. If one can design or choose an appropriate
data structure along with a suitable algorithm then the
programs become more efficient.

1.2 what is data structure?

what is actually data structure? How does it help in de-

signing better solutions?

To better learn what is data structure? We should under-

stand why it is required?. Let us understand it through
an example.

5
You think about locating a page in a text book contain-
ing 200 pages. How do you go to a particular page, say
137?
will you start from page 1 and turn over each page to
reach the page 137 ? Never!! you will simply divide the
book pages into two halves and look at the page number
and you decide whether it is the page you are looking for!
if it is, you are happy and stop searching. Otherwise, if
the page number at which you are now is below 137, you
simply skip the first half part of the book and and divide
the second part of the book similar to the fashion you
reached at the present page. This way, you will find any
page in the book within fractions of a minute.

How it was possible to do this kind of search operation

on the text book? Have you thought about it before? It
was possible only because of the fact that all the pages in
the book are arranged in an organized manner (ascend-
ing order).

From this example we understood the relevance of struc-

turing/organizing of data so as to make certain opera-
tions easy. The algorithm we have performed for search-
ing the book page is called ’binary search’ which is possi-
ble only when the data is organized either in ascending or
descending order. In other words, it is totally impossible
to apply binary search algorithm on a unordered set of
data items. The above example depicts the relationship
of operations with the organization of data.

In short, If you have a set of organized collection of data,

you can find out some set of operations which can effec-
tively be applied. Such, logically organized set of data

6
along with a set of operations applicable constitute data
structure.

1.2.1 Definition of Data Structure

definition:
Data structure is an organized set of data element(s)
in computer memory in a manner that is convenient to
perform operations on it.

example: int rollNo; int rollNos[10];

each data structure mainly specifies the following:

• representation of data element(s)

• relationship among data elements
• Access methods

1.3 classification of data structures

Data structures can be classified into primitive and non-

primitive. Primitive data structures are also called as ba-
sic or primitive or scalar data types. Non-primitive data
structures are called composite data structures having
multiple values. The figure 1.1 shows various classifica-
tion of data structures.

1.4 significance of data structures

We have already seen in the introduction part that data

structures are the building blocks of programs. Hence,
the selection of a particular data structure that best suits

7
 Figure 1.1: Classification of Data Structures

the requirement is most important step in the program

design. Its significance is clear the formula given below.

DataStructure + Algorithm = P rograms

1.5 operations on data structure

There are a set of operations defined on each data struc-

ture. These operations are categorized into two types
a. Generic Operations

b. Specialist/typical Operations

8
Generic operations are that type of operations which you
can find in any Data structure. i.e. they are invariably
available to all the data structures. For example, op-
erations like Create(), Initialize(), Destroy() etc.
are needed by all the data structures and their purpose
is same.
The operation used for accessing the data elements
in a data structure are different for each type of data
structure and are termed as Specialist/Typical opera-
tions. For example, the operation used for store an el-
ement in Stack is generally termed as Push() whereas
the operation used for storing an element in a Queue
data structure is termed as Add() operation. Similarly,
for deleting an element from the Stack we have Pop()
whereas that for Queue is Del() or Delete() operation.
In general, you can enlist the operations in a data struc-
ture in the following way:

• Create : Allocation of Memory

• Destroy : De-allocation of Memory

• Selection : Accessing data elements

• Updation : Store, Modify and delete

1.6 what is mathematical modelling?

Models describe our beliefs about how the world func-

tions. In mathematical modelling, we translate those
beliefs into the language of mathematics. This has many
advantages

9
 • Mathematics is a very precise language. This helps
us to formulate ideas and identify underlying as-
sumptions.

• Mathematics is a concise language, with well-defined

rules for manipulations.

• All the results that mathematicians have proved

over hundreds of years are at our disposal.

• Computers can be used to perform numerical cal-

culations.

We can use mathematical models for representing real

world situations first which can further be represented by
means of data structures for finding the solutions. For
example, many a time we have become part of various
Queues in the real world. We can mathematically define
the notion of Queue and its operation using mathemati-
cal concepts or tools of lists/sets.

1.7 adt - abstract data types

An Abstract Data Type (ADT) is a data type together

with the operations, whose properties are specified inde-
pendently of any particular implementation.

• ADT are set of definitions of operations

• Can have several different implementations

• Different implementations can have different effi-

ciency

10
 2
M O D U L E 2 - L I N E A R D ATA
STRUCTURES

2.1 introduction

There are variety of classifications to data structures

based on different criteria. Based on how the elements
in the data structure are organized or accessed - physi-
cally or logically - we have, Linear and Non-linear data
structures. If the elements stored, logically or physically,
adjacent we call them linear otherwise non-linear data
structure.

Figure 2.1: linear Data Structures

11
 Figure 2.2: Nonlinear Data Structure

For example, in array elements are stored physically

adjacent and can only be accessed sequentially. Simi-
larly, in Linked list elements are logically adjacent even
though they are physically spread over the memory and
are usually accessed sequentially. Therefore, both these
data structures are linear data structures. But, in the
case of tree or graph the element are need not be accessed
sequentially because there are more than one path from
a node. Therefore, they are Non-linear data structure.
Another classification to data structure is based on na-
ture of the elements in a data structure. Based on this
criteria, we have homogenous and non-homogeneous data
structure. In homogeneous data structure all the mem-
bers of the data structure are identical in nature. Exam-
ple, Array. Whereas in non-homogenous data structures
member elements are of different in nature. Example,
Structure.
Yet another classification to the data structure are
based on associated memory location and size. i.e., asso-

12
ciated memory location and size of a data structure can
be static & dynamic. In static data structure, the asso-
ciated memory location and size are fixed at compilation
time, whereas in dynamic data structures they vary at
run time.

example
• for static : Array,
• for dynamic : linked list, tree etc.

Figure 2.3: Data Memory Model

2.2 arrays

Array is a finite set of data items which are identical in

nature. Arrays are linear data structures and the ele-
ments in an array are physically adjacent. The elements

13
in an array are normally accessed using their subscripts
or indices. From the above definition it is clear it has
following characteristics

• Elements are linearly organized.

• Elements are homogeneous in nature.

• They are static - i.e., size and location are fixed at

compile time.

• Each element in the array has a positional number

called index or subscript.

• They exist in one dimensional or multi-dimensional

form.

2.2.1 Definition

The simplest form of array is a one-dimensional array

that may be defined as a finite ordered set of homoge-
neous elements, which is stored in contiguous memory
locations. For example, an array may contain all inte-
gers or all characters or any other data type, but may
not contain a mix of data types.

The general form for declaring a single dimensional ar-

ray is:

data_type array_name[size];

where data_type represents data type of the array. That

is, integer, char, float etc. array_name is the name of
array and expression which indicates the number of ele-
ments in the array.

14
For example,
int a[100];
It declares an array of 100 integers.

2.2.2 Memory storage & Index

The amount of storage required to hold an array is di-

rectly related to its type and size. For a single dimen-
sion array, the total size in bytes required for the array
is computed as shown below.

Memory required (in bytes) = size of (data type) X

length of array.

Each element in a array can be easly addressed by us-

Figure 2.4: Schematic representation of an Array with its

index

ing its index or key. The figure 2.4 shows the schematic
representation of a one dimensional array X with its in-
dices. It is clear from the figure 2.4 that the first el-
ement in the array has the index value 0, the seccond
has the index value 1 and so on. Thus, in general X[i],
i ≥ 0 and i < array_size, represents i + 1th element in
the array X. And, the variable i is called index variable.
Since array index is starting from 0, the data_type of
the index must be integer.

15
2.2.3 Array Representation

It is not uncommon to find a large number of programs

which process the elements of an array in sequence. But,
does it mean that the elements of an array are also stored
in sequence in memory. The elements of an array are
stored in sequence to the extent possible. If they are
being stored in sequence, then how are they sequenced. If
we are using one dimesional array, then it is easy to store
in memory sequencially. What about multi-dimensional
arrays? Is it that the elements are stored row wise or
column wise? The former is called row major order and
the later is called column major order.

Row Major Representation

The first method of representing a two-dimensional array

in memory is the row major representation. Under this
representation, the first row of the array is stored in the
first set of the memory location reserved for the array,
the second row occupies the next set, and so forth. it is
clearly shown in the figure 2.5given below.

Column Major Representation

The second method of representing a two-dimensional ar-

ray in memory is the column major representation. Un-
der this representation, the first column of the array is
stored in the first set of the memory location reserved for
the array, the second column occupies the next set, and
so forth. it is clearly shown in the figure 2.6given below.

16
Figure 2.5: (a)-Two dimesional array. (b) row-major
memory representation.

Figure 2.6: (a)-Two dimesional array. (b) column-major

memory representation.

Address calculation of array element A[j][k]

To compute the actual memory location of an element

in an array, the computer keeps track of Base(A), the
address of the first element A[0][0] of A[M][N], and com-
putes address Loc(A[j ][k ]) of A[M][N] using the follow-
ing formula in Row-major order:
Loc(A[j ][k ]) = Base(A) + S [N ∗ j + k ]
and for Column major order it uses the formula given
below:
Loc(A[j ][k ]) = Base(A) + S [M ∗ k + j ]

17
where S denotes the size of an element, i.e; number of
bytes per data element of the array A, M is total num-
bers of rows, and N is total number of columns in the
array.

18
 3
M O D U L E 3 - S TA C K & Q U E U E S

3.1 stack

One of the most useful concepts in computer science is

stack. In this unit, we shall examine this simple data
structure and see why it plays such a prominent role in
the area of programming. There are certain situations
when we can insert or remove an item only at the begin-
ning or the end of the list.
A stack is a linear structure in which items may be
inserted or removed only at one end called the top of the
stack. A stack may be seen in our daily life, for example,
Figure 3.2 depicts a stack of dishes. We can observe that

Figure 3.1: A Stack of dishes

any dish may be added or removed only from the top of

the stack. It concludes that the item added last will be
the item removed first. Therefore, stacks are also called

19
LIFO (Last In First Out) or FILO (First In Last Out)
lists. We also call these lists as ‘piles’ or ‘push-down list’.
Apart from generic operations, two special operations
are associated with the stacks named Push & Pop.

• Push is an operation used to insert an element at

the top.

• Pop is an operation used to delete an element from

the top

Figure 3.2: Stack operations

3.1.1 Implementation of stacks

• An array can be used to implement a stack.

• But since array size is defined at compile time, it

cannot grow dynamically at runtime, and there-
fore, an attempt to insert an element into a array
implementation of stack that is already full causes
a stack overflow.

• An ideal implementation of a stack is a linked list

that can dynamically grow and shrink at runtime.

20
 • We use a pointer which is called top to point the
first node in the stack.

• It is using top that a node will either be inserted

at the beginning or top of the stack(push a node
into the stack), or deleted from the stack(popping
a node at the top or beginning of the stack)

Algorithm for push operation

step 1: [Check for stack overflow]

if top >=MAXSTACK
print ”Stack overflow” and exit.

step 2: [Increment the pointer value by one]

top=top+1

step 3: [Insert the item]

arr[top]=value

step 4: Exit

Here, top is a pointer which denotes the position of top

most item in the stack. Stack is represented by the array
arr and MAXSTACK represents the maximum possible
number of elements in the stack. The algorithm given
below shows the pop operation. In the case of pop opera-
tion, after removal of top most value, top is decremented
by 1.

Algorithm for pop operation

step 1: [Check whether the stack is empty]

if top = 0
print ‘Stack underflow’ and exit exit.

21
step 2: [Remove the top most item]
value=arr[top]
top=top-1

step 3: [Return the item of the stack]

return(value)

To implement a stack using linked list we can use a node

structure of the following type.

s t r u c t stack_type
{
int info ;
s t r u c t stack_type ∗ next ;
};
typedef s t r u c t stack_type stack ;
s t a c k ∗ top=NULL, ∗new ;

The push() and pop() operations on a stack are analo-

gous to insert-first and delete-first operations(which will
be discussed later in the next module) on a linked list
that functions as a stack.

3.1.2 Applications of Stack

• Function Call

The figure 3.3 shows what happens when a function

calls are made. Each time a function is called it pushes
the return address to the stack and control is transferred
to the function called. Each time a return is met it pops
one address from the top of the stack and the control is
sent back to that address.

22
 Figure 3.3: Function calling

• Expression Evaluation

• Conversion from infix to postfix notion.

Example:-

Infix: A + B ∗ C
Prefix: +A ∗ BC
Postfix: ABC ∗ +

Prefix form is called the polish notation of the expression,

and postfix is called reverse polish notation.

3.1.3 Simulation of recursion using stack

There are cases where we prefer to use recursive func-

tions such as sort (Merge Sort) or tree operations (heapify
up / heapify down). However, if the recursive function
goes too deep in some environments, an unwanted result

23
might occur such as a stack-overflow. There are meth-
ods to replace recursive functions to avoid stack-overflow
problems in advance by replacing with iterative function
or using stack (heap stack) and while - loop (recursive
simulation function). Let us discuss some general meth-
ods (or guidelines) to replace the recursive functions us-
ing stack (heap stack) and while-loop to avoid the stack-
overflow to help novice developers. For example,
A factorial is a number that is defined as
n! = n ∗ (n − 1) ∗ (n − 2) ∗ .... ∗ 1
or
n! = n ∗ (n − 1)!, for n > 0
We can write a function that is closer to the definition of
a factorial by having our function call itself, like this:

int fact_recursive ( int i )

{
if ( i > 0 )
return i ∗ f a c t _ r e c u r s i v e ( i − 1 ) ;
return 1 ;
}

Notice that fact_recursive calls itself with (i - 1) and

then multiplies the return value by i. This function is
very similar to the factorial definition given above, and
that makes it easier to check for errors.

Base case

Notice that a test for i > 0 is made before the function

is called again. This is called the base case, and it is

24
required for every recursive function. Without a base
case, the function would not know when to stop calling
itself, and you would have an infinite recursion (or until
you ran out of stack space). Speaking of stack space, how
does recursion work anyway? Good question.
Every time you call a function, a thingy (very tech-
nical term) called an activation record is pushed onto
the stack. The activation record, also known as a stack
frame, contains things such as local variables for the func-
tion, arguments, and the address of the previous activa-
tion record so that it knows how to return from whence
it came. Because of these activation records, two calls
to the same function aren’t actually the same activation
record, that’s why recursion works. Each new call to
fact_recursive has its own memory, its own argument
copies, its own everything.
Because this all works like a stack, each new activation
record covers up the previous record. When the function
finally reaches the base case and returns, each activation
record is popped from the stack until execution finally
leaves the first call to fact_recursive.

Simulating Recursion

Any operation that can be carried out with recursion can

also be carried out with an explicit stack, that is, a stack
that you write can be used to simulate recursion.
In the case of factorial example we could come up with
something like follows:

25
int fact_stack ( int i )
{
i n t s t a c k [ 5 ] ; /∗ Assume f a c t _ s t a c k ( 5 ) ∗/
i n t top = 0 ;
int ret = 1;
while ( i > 0 )
s t a c k [ top++] = i −−;
w h i l e ( top > 0 )
r e t ∗= s t a c k [−−top ] ;
return r e t ;
}

3.2 queues

Queue is a linear data structure used in various applica-

tions of computer science. Like people stand in a queue
to get a particular service, various processes will wait in
a queue for their turn to avail a service. It is also called
a FIFO (first in first out) list. In this section, we will
study about various types of queues.
A physical analogy for a queue is a line at a booking
counter. At a booking counter, customers go to the rear
(end) of the line and customers are attended to various
services from the front of the line. Unlike stack, cus-
tomers are added at the rear end and deleted from the
front end in a queue (FIFO).
An example of the queue in computer science is print
jobs scheduled for printers. These jobs are maintained in
a queue. The job fired for the printer first gets printed

26
first. Same is the scenario for job scheduling in the CPU
of computer.
Like a stack, a queue also (usually) holds data elements
of the same type. We usually graphically display a queue
horizontally. Figure 3.4 depicts a queue of integers.

Figure 3.4: (a) Queue containing three elements.

(b)When a new element 4 is added(see rear
end). (c) When an element deleted from the
queue.

Apart from generic operations, two special operations

are associated with the queue are AddQ() & DelQ().
• AddQ() is an operation used to add an element at
the rear end of the queue.
• DelQ() is an operation used to delete an element
from the front end of the queue.

3.2.1 Implementation of Queue Using Array

• An array can be used to implement a queue.

• But since array size is defined at compile time, it
cannot grow dynamically at runtime, and therefore,

27
 an attempt to insert an element into a array imple-
mentation of queue that is already full causes a
queue full.

Algorithm for AddQ() operation

step 1: [Check for queue fullness]

if rear >=MAXQ
print ”Queue full” and exit.

step 2: [Increment the rear pointer value by one]

rear=rear+1

step 3: [Insert the item]

Q[rear]=value

step 4: Exit

Here, rear is a pointer which denotes the position of last

item in the queue. Queue is represented by the array Q
and MAXQ represents the maximum possible number of
elements in the queue. To add element the rear pointed
is incremented first and the element is inserted at this
position. Please note that initial condition for the queue
is f ront = rear = −1.

Algorithm for DelQ() operation

step 1: [Check for queue emptiness]

if rear = = front
print ”Queue empty” and exit.

step 2: [Increment the front pointer value by one]

front=front+1

28
step 3: [Take the item at front]
value=Q[front]

step 4: Exit

The above algorithm shows the DelQ() operation. In

the case of DelQ() operation, front is incremented by 1,
then the element is removed at this position. So that,
the element first inserted is deleted first.

3.2.2 Implementation of Queue Using Array

• An ideal implementation of a queue is a linked list

that can dynamically grow and shrink at runtime.

• Queue functionality of a linked list can be achieved

by having two pointers front and and rear, pointing
to the first element, and last element of the queue
respectively.

• The figure 3.5 is a visual depiction of linked list

implementation of a queue.

Figure 3.5: Queue using linked list

To implement a queue using linked list we can use a node

structure of the following type.

29
s t r u c t queue_type
{
int info ;
s t r u c t queue_type ∗ n e x t ;
};
t y p e d e f s t r u c t queue_type Queue ;
Queue ∗ f r o n t , ∗ r e a r , ∗new ;

Here the AddQ() and DelQ() operations on a queue are

analogous to insert-first and delete-last operations(as dis-
cussed later in the next module) on a linked list that
functions as a queue.

3.3 circular queue

One of the major problems with the linear queue is the

lack of proper utilisation of space. Suppose that the
queue can store 100 elements and the entire queue is
full. So, it means that the queue is holding 100 elements.
In case, some of the elements at the front are deleted, the
element at the last position in the queue continues to be
at the same position and there is no efficient way to find
out that the queue is not full. In this way, space utili-
sation in the case of linear queues is not efficient. This
problem is arising due to the representation of the queue.
The alternative representation is to depict the queue
as circular. In case, we are representing the queue using
arrays, then, a queue with n elements starts from index
0 and ends at n-1. So, clearly , the first element in the
queue will be at index 0 and the last element will be at
n-1 when all the positions between index 0 and n-1(both
inclusive) are filled. Under such circumstances, front will
point to 0 and rear will point to n-1. However, when a

30
new element is to be added and if the rear is pointing to
n-1, then, it needs to be checked if the position at index
0 is free. If yes, then the element can be added to that
position and rear can be adjusted accordingly. In this
way, the utilisation of space is increased in the case of a
circular queue.
In a circular queue, front will point to one position less
to the first element. So, if the first element is at position
4 in the array, then the front will point to position 3.
When the circular queue is created, then both front and
rear point to index 0, i.e, circular queue is empty. Figure
3.6 depicts a circular queue.

Figure 3.6: Circular Queue(Front = 0, Rear = 4)

Algorithm for AddCQ() operation

step 1: [Check for circular queue fullness]

if (rear + 1)% MAXCQ = = front, then print ”Cir-
cular Queue full” and exit.

31
step 2: [Increment the rear pointer value by one circu-
larly]
rear=rear+1% MAXCQ

step 3: [Insert the item]

CQ[rear]=value

step 4: Exit

Here, rear pointer is incremented using modulo divi-

sion operator, rear = rear + 1%M AXCQ, where MAXCQ
is the maximum size of the circular queue array CQ.
Please note that initial condition for the circular queue
is f ront = rear = 0.

Algorithm for DelCQ() operation

step 1: [Check for circular queue emptiness]

if rear = = front, then print ”Queue empty” and
exit.

step 2: [Increment the front pointer value by one cicu-

larly]
front=front + 1 % MAXCQ

step 3: [Take the item at front]

value=CQ[front]

step 4: Exit

3.3.1 Priority Queues

In our daily life, for example, there are ‘very urgent’,

‘normally urgent’ and ‘less urgent’ tasks, which must be
finished in the order of their urgency or priority. The

32
most urgent task is always to be finished next. Finishing
a task, however, may create new tasks to be finished, with
priorities of their own. Moreover, the priority of a task
absolutely may change before the task was finished if this
task is suddenly classified as important or less important
because of outer circumstances.
In an ordinary queue(as of that we discussed), things
are stored ordered by the time of their insertion; they
are taken out of the queue in this order again (FIFO
principle). Often, however, one wants to store things
ordered by a priority different from the entry time, and
take them out again according to this ordering. Then,
between two things with different priority p1 and p2, a
new thing may have to be inserted, with a priority p in
between p1 and p2 - in contrast to an ordinary queue, in
which insertions can be carried out at the end only. This
type queue is known as priority queue.
Implementation of a priority queue can be achieved by
modifying either the AddQ() or DelQ() operation slightly.
If we are modifying AddQ() operation then we are sup-
posed to re-order the elements in the priority queue when-
ever we make an insertion of element. On the other hand,
if we modify DelQ() operation, then we must ensure re-
ordering of elements in the priority queue before we make
a delete operation.
Another effective method to implement a priority queue
is to use a heap tree to implement the functionality. In a
heap tree the element that come at root will be the one
with maximum value. Therefore, the element deleted
from the root will be having the maximum value.

33
 4
MODULE 4 - LINKED LISTS

4.1 lists

In module 2, we have discussed arrays. Arrays are data

structures of fixed size. Insertion and deletion involves
reshuffling of array elements. Thus, array manipulation
is time-consuming and inefficient. In this module, we will
see various types of linked lists and their applications.
As we found in the previous modules array is a useful
data structure which can access any element of an array
directly. And, it is useful in creating data structures like
queues, stacks etc. Also, it is found that array is light
on memory usage compared to other structures. How-
ever, it is a rigid and hard structure to do operations
like adding/removal of elements. The major drawback
of array is that it cannot be dynamically resized. To
overcome these limitations we can use linked list.

4.1.1 List versus Array

The principal benefit of a linked list over a conventional

array is that

35
 • The data items need not be stored contiguously in
memory or on disk.

• Therefore, the list elements can easily be inserted

or removed without reallocation or reorganization
of the entire structure.

• Linked lists allow insertion and removal of nodes

at any point in the list.

• Operations can be done with a constant number

of operations if the link previous to the link being
added or removed is maintained during list traver-
sal.

• On the other hand, simple linked lists by them-

selves do not allow random access to the data, or
any form of efficient indexing.

• Thus, many basic operations - such as obtaining

the last node of the list (assuming that the last
node is not maintained as separate node reference
in the list structure), or finding a node that con-
tains a given datum, or locating the place where a
new node should be inserted - may require scanning
most or all of the list elements.

4.1.2 Implementation of linked lists

The Linked list is a chain of structures in which each

structure consists of data as well as pointer, which stores
the address (link) of the next logical structure in the list.
A linked list is a data structure used to maintain a
dynamic series of data. Think of a linked list as a line

36
of compartments/bogies of train where each bogie is con-
nected on to the next bogie. If you know where the first
bogie is, you can follow its link to the next one. By follow-
ing links, you can find any bogie of the train. When you
get to a bogie that is not holding (linked) on to another
bogie, you know you are at the end.
Linked lists work in the same way, except programmers
usually refer to nodes instead of bogies. A single node is
defined in the same way as any other user defined type or
object, except that it also contains a pointer to a variable
of the same type as itself.
We will be seeing how the linked list is stored in the
memory of the computer. In the Figure 4.1, we can see
that head is a pointer which is pointing to the node which
contains data as Anoop and the node Anoop is pointing
to the node vivek and the last node deepu is not pointing
to any node. 100,250,400 and 475 are memory addresses.

Figure 4.1: A singly linked list

struct linked_list
{
i n t data ;
s t r u c t l i n k e d _ l i s t ∗ next ;
};
typedef struct l i n k e d _ l i s t l i s t ;

37
The definition given above can be used to create a list
node.
Once you have a definition for a list node, you can
create a list simply by declaring a pointer to the first
element, called the ‘head’. A pointer is generally used
instead of a regular variable. List can be defined as
l i s t ∗ head ;
In figure 4.1 the pointer which points to the node deepu
is the tail pointer of the list. It is defined in the similar
way that we defined head pointer.

Algorithm for insertion of a node into the linked list

step 1: Begin

step 2: if the list is empty or a new element comes

before the start (head) element, then insert the new
element as start element.

step 3: else, if the new element comes after the last

element, then insert the new element as the end
element.

step 4: else, insert the new element in the list by using

the find function, find function returns the address
of the found element to the insert_list function.

step 5: End.

Figure 4.2 depicts the scenario of a linked list of two

elements and a new element which has to be inserted
between them. Figure 4.3 depicts the scenario of a linked
list after insertion of a new element into the linked list
of Figure 4.2.

38
 Figure 4.2: A linked list - before insertion

Figure 4.3: A linked list - after insertion

Algorithm for deletion of a node from the linked list

step 1: Begin

step 2: if the list is empty, then element cannot be

deleted.

step 3: else, if element to be deleted is first node, then

make the start (head) to point to the second ele-
ment.

step 4: else, delete the element from the list by calling

find function and returning the found address of
the element.

step 5: End.

39
 Figure 4.4 depicts the process of deletion of an element
from a linked list.

Figure 4.4: Linked list - Deletion Process

4.2 doubly linked list

In a singly linked list, each element contains a pointer

to the next element. We have seen this before. In single
linked list, traversing is possible only in one direction.
Sometimes, we have to traverse the list in both directions
to improve performance of algorithms. To enable this, we
require links in both the directions, that is, the element
should have pointers to the right element as well as to its
left element. This type of list is called doubly linked list.
Doubly linked list (Figure 4.5) is defined as a collection
of elements, each element consisting of three fields:

• pointer to left element,

• data field, and

40
 Figure 4.5: Doubly Linked List

• pointer to right element.

Left link of the leftmost element is set to NULL which

means that there is no left element to that. And, right
link of the rightmost element is set to NULL which means
that there is no right element to that. Node structure for
the doubly linked list is given below.

struct dl_list
{
i n t data ;
struct dl_list ∗ right ;
struct dl_list ∗ l e f t ;
};
typedef struct d l _ l i s t d l i s t ;

4.3 circular linked list

A linked list in which the last element points to the first

element is called CIRCULAR linked list. The chains do
not indicate first or last element; last element does not
contain the NULL pointer. The external pointer provides
a reference to starting element. The figure 4.6 shows a
circular linked list. The possible operations on a circular
linked list are:

• Insertion,

41
 Figure 4.6: Circular Linked List

• Deletion, and

• Traversing

Note that there is no difference in the node structure of

singly linked list to convert it as a circular liked list. i.e,
singly linked list and circular list have the same node
structures.

Algorithm for Insertion of an element into a Circular

Linked List

step 1: Begin

step 2: if the list is empty or new element comes be-

fore the start (head) element, then insert the new
element as start element.

step 3: else, if the new element comes after the last

element, then insert the new element at the end
element and adjust the pointer of last element to
the start element.

step 4: else, insert the new element in the list by using

the find function. find function returns the address
of the found element to the insert_list function.

42
 Figure 4.7: Circular Linked List - before insertion

step 5: End.

The figure 4.7 depicts the Circular linked list with a new
element that is to be inserted. If new item is to be in-
serted after an existing element, then, call the find func-
tion recursively to trace the ‘key’ element. The new ele-
ment is inserted before the ‘key’ element by using above
algorithm. The figure4.8 depicts a Circular linked list

Figure 4.8: Circular Linked List - after insertion

with the new element inserted between first and second

nodes of figure 4.7.

Algorithm for deletion of an element from a Circular

Linked List

step 1: Begin

43
step 2: if the list is empty, then element cannot be
deleted.

step 3: else, if element to be deleted is first node, then

make the start (head) to point to the second ele-
ment.

step 4: else, delete the element from the list by calling

find function and returning the found address of
the element.

step 5: End.

Figure 4.9 depicts a Circular linked list from which an

element was deleted.

Figure 4.9: Deletion of a node from a Circular Linked

List

In the similar way, we have created circular single list

from linear single list we can create Circular Double List
from Linear Double Linked list.

44
Figure 4.10: Deletion of a node from a Circular Double
Linked List

45
 5
M O D U L E 5 - N O N L I N E A R D ATA
STRUCTURES

We have learned various data structures i previous mod-

ules. We observed that linear data structures have prop-
erties of ordering relationship. But, in some data struc-
tures it is hard to find first node or last node i.e., elements
with no ordering. Data structures where there is no or-
dering relationship among elements are called Nonlinear
Data structures.

5.1 trees

Have you ever thought how does the operating system

manage our files? Why do we have a hierarchical file
system? How do files get saved and deleted under hier-
archical directories?
Tree is a data structure which allows you to associate a
parent-child relationship between various pieces of data
and thus allows us to arrange our records, data and files
in a hierarchical fashion. Consider a Tree representing
your family structure. Let us say that we start with
your grand parent; then come to your parent and finally,
you and your brothers and sisters. In this section, we
will go through the basic tree structures first (general

47
trees), and then go into the specific and more popular
tree called binary trees.
we can define a tree T as a finite set of one or more
nodes such that there is one designated node r called the
root of T, and the remaining nodes in (T − {r}) are par-
titioned into n > 0 disjoint subsets T1 , T2 , ..., Tn each of
which is a tree, and whose roots r1 , r2 , ..., rk , respectively,
are children of r. The general tree is a generic tree that
has one root node, and every node in the tree can have
an unlimited number of child nodes. One popular use of
this kind of tree is a Family Tree. A tree is an instance
of a more general category called graph.
• A tree consists of nodes connected by edges/branches.

• A root is a node without parent.

• Leaves are nodes with no children.

• The root is at level 1.

• The child nodes of root are at level 2.

• The child nodes of nodes at level 2 are at level 3

and so on.

• The depth (height) of a Binary tree is equal to the

number of levels in it.

• Branching factor defines the maximum number of

children to any node.

• So, a branching factor of 2 means a binary tree.

• Breadth defines the number of nodes at a level.

• The depth of a node M in a tree is the length of

the path from the root of the tree to M.

48
 • A node in a Binary tree has at most 2 children.

The following are the properties of a Tree.

Full Tree :

A tree with all the leaves at the same level, and all the
non-leaves having the same degree

• Level h of a full tree has dh − 1 nodes.

• The first h levels of a full tree have 1 + d + d2 + d3 +

d4 + ... + dh−1 = (dh − 1)/(d − 1) nodes where d
is the degree of nodes.

• The number of edges = the number of nodes -

1(Why? Because, an edge represents the relation-
ship between a child and a parent, and every node
has a parent except the root).

• A tree of height h and degree d has at most dh − 1

elements.

Complete tree

A complete tree is a k-ary position tree in which all lev-

els are filled from left to right. There are a number of
specialized trees.

5.1.1 Implementation of tree

The most common way to add nodes to a general tree

is to first find the desired parent of the node you want
to insert, then add the node to the parent’s child list(see

49
 Figure 5.1: A general tree

figure 5.1). The most common implementations insert

the nodes one at a time, but since each node can be
considered a tree on its own, other implementations build
up an entire sub-tree before adding it to a larger tree. As
the nodes are added and deleted dynamically from a tree,
tree are often implemented by linked lists. However, it
is simpler to write algorithms for a data representation
where the numbers of nodes are fixed. Figure 5.2 depicts
the structure of the node of a general k − ary tree.

Figure 5.2: Node structure of a general tree

Figure 5.3 depicts a tree with one data element and

three pointers. The number of pointers required to im-

50
plement a general tree depend of the maximum degree of
nodes in the tree.

Figure 5.3: A linked list representation of tree (3-ary

tree)

5.2 binary trees

A binary tree is a special tree where each non - leaf node

can have atmost two child nodes. It is a most important
type of a tree which is used to model yes/no, on/off,
higher/lower, i.e., binary decisions.

Recursive Definition:

A binary tree is either empty or a node that has left and

right sub-trees that are binary trees.
In a formal way, we can define a binary tree as a finite
set of nodes which is either empty or partitioned in to
sets of T0 , Tl , Tr , where T0 is the root and Tl and Tr

51
are left and right binary trees, respectively. Figure 5.4
shows an example for a binary tree.

Figure 5.4: A binary tree

Properties of a binary tree

• If a binary tree contains n nodes, then it contains

exactly n − 1 edges;

• A Binary tree of height h has 2h − 1 nodes or less.

• If we have a binary tree containing n nodes, then

the height of the tree is at most n and at least
ceiling log2 (n + 1).

• If a binary tree has n nodes at a level l then, it has

at most 2n nodes at a level l + 1

• The total number of nodes in a binary tree with

depth d (root has depth zero) is
N = 20 + 21 + 22 + ... + 2d − 1 = 2d+1

52
Full Binary Trees:

A binary tree of height h which had 2h − 1 elements is

called a Full Binary Tree.

Complete Binary Trees:

A binary tree whereby if the height is d, and all levels,

except possibly level d, are completely full. If the bottom
level is incomplete, then it has all nodes to the left side.
That is the tree has been filled in the level order from
left to right.

5.2.1 Implementation of Binary Tree

Using Linked List

Like general tree, binary trees are implemented through

linked lists. A typical node in a Binary tree has a struc-
ture as follows (refer to Figure 5.5):

Figure 5.5: Node structure of a binary tree

s t r u c t NODE
{
s t r u c t NODE ∗ l e f t c h i l d ;

53
 i n t n o d e v a l u e ; /∗ t h i s can be o f any d a t a t y p
s t r u c t NODE ∗ r i g h t c h i l d ;
};

Using Array

Consider a complete binary tree T having n nodes where

each node contains an item (value). Label the nodes of
the complete binary tree T from top to bottom and from
left to right 0, 1, ..., n-1. Associate with T the array A
where the ith entry of A is the item in the node labelled
i of T, i = 0, 1, ..., n-1. Figure 5.6 depicts the array

Figure 5.6: Node structure of a binary tree

representation of a Binary tree of Figure 5.4 Given the

54
index i of a node, we can easily and efficiently compute
the index of its parent and left and right children:
• Index of Parent: ⌊(i − 1)/2⌋,
• Index of Left Child: 2i + 1,
• Index of Right Child: 2i + 2.

5.2.2 Binary Tree Traversals

There are three types of tree traversals, namely, Preorder,

Postorder and Inorder.

Preorder traversal:

Each node is visited before its children are visited; the

root is visited first.

Figure 5.7: A expression binary tree

55
Algorithm for pre order traversal:

1. visit root node

2. traverse left sub-tree in preorder

3. traverse right sub-tree in preorder

For example, consider the tree in figure 5.7. When we per-

form preorder traversal on this expression tree we have
the output as follows:
preorder Traversal : + ∗ / 4 2 7 − 3 1

Algorithm : Non-recursive preorder binary tree traversal

Stack S
push r o o t onto S
r e p e a t u n t i l S i s empty
{
v = pop S
i f v i s not NULL
visit v
push v ‘ s r i g h t c h i l d onto S
push v ‘ s l e f t c h i l d onto S
}

In Order Traversal

The left sub tree is visited, then the node and then right
sub-tree.

Algorithm for inorder traversal:

1. traverse left sub-tree

56
 2. visit node

3. traverse right sub-tree

When we perform inorder traversal on the expression

tree shown in 5.7 we have the output as follows:
in-order sequence : (((4 / 2) ∗ 7) + (3 − 1))
The recursive algorithm for in-order traversal is given
by the following algorithm.

i n o r d e r ( s t r u c t NODE ∗ c u r r )
{
i f ( c u r r −> l e f t != NULL)
i n o r d e r ( c u r r −> l e f t ) ;

p r i n t f ( ‘ ‘% d ‘ ‘ , c u r r −>v a l u e ) ;

i f ( c u r r −>r i g h t != NULL)
i n o r d e r ( c u r r −>r i g h t ) ;
}

Algorithm : Non-recursive inorder binary tree traversal

Stack S
push r o o t onto S
r e p e a t u n t i l S i s empty
{
v = pop S
i f v i s not NULL
push v ‘ s r i g h t c h i l d onto S
visit v
push v ‘ s l e f t c h i l d onto S
}

57
Postorder traversal

In a preorder traversal, the root is visited first (pre) and

then the left and right subtrees are traversed. In a pos-
torder traversal, the left sub-tree is visited first, followed
by right sub-tree which is then followed by root. In an
inorder traversal, the left subtree is visited first, followed
by root, followed by right sub-tree.

Algorithm for postorder traversal:

1. traverse left sub-tree

2. traverse right sub-tree

3. visit node

When we perform postorder traversal on the expres-

sion tree shown in 5.7 we have the output as follows:
post-order sequence : 4 2 / 7 ∗ 3 1 − +
The recursive algorithm for post-order traversal is given
by the following algorithm.

p o s t o r d e r ( s t r u c t NODE ∗ c u r r ) {
i f ( c u r r −> l e f t != NULL)
i n o r d e r ( c u r r −> l e f t ) ;

i f ( c u r r −>r i g h t != NULL)
i n o r d e r ( c u r r −>r i g h t ) ;

p r i n t f ( ‘ ‘% d ‘ ‘ , c u r r −>v a l u e ) ;
}

58
Level order traversal

There is another tree traversal (of course, not very com-

mon) is called level order, where all the nodes of the
same level are travelled first starting from the root (refer
to Figure 5.8).

Figure 5.8: Level order tree traversal

5.3 binary search trees (bst)

Data structures organised as trees have a wide range of

advantages in various applications and it is best suited for
the problems related to information retrieval. These data
structures allow the searching, insertion and deletion of
node in the ordered list to be achieved in the minimum
amount of time.
A Binary Search Tree is a binary tree that is either
empty or a node containing a key value, left child and
right child.

59
 By analyzing the above definition, we note that BST
comes in two variants namely empty BST and non-empty
BST.
The empty BST has no further structure, while the
non-empty BST has three components.
A non-empty Binary Search Tree (BST) is a binary
tree with the following properties:
a) The key in the left child of a node (if exists) is less
than the key in its parent node.
b) The key in the right child of a node (if exists) is
greater than the key in its parent node.
c) The left and right subtrees of the root are again bi-
nary search trees.
Figure 5.9 shows an example for BST. It may be seen that

Figure 5.9: A Binary Search Tree

when nodes of a BST are traversed by inorder traversal,

the keys appear in sorted order.

60
 The following are some of the operations that can be
performed on Binary search trees:

• Creation of an empty tree

• Traversing the BST

• Counting internal nodes (non-leaf nodes)

• Counting external nodes (leaf nodes)

• Counting total number of nodes

• Finding the height of tree

• Insertion of a new node

• Searching for an element

• Finding smallest element

• Finding largest element

• Deletion of a node.

5.3.1 Insertion of a node into a Binary Search Tree

A binary search tree is constructed by the repeated in-

sertion of new nodes into a binary tree structure.
Insertion must maintain the order of the tree. The
value to the left of a given node must be less than that
node and value to the right must be greater.
In inserting a new node, the following two tasks are
performed :

• Tree is searched to determine where the node is to

be inserted.

61
 • On completion of search, the node is inserted into
the tree

Example: Consider the BST of Figure 5.10 After inser-

tion of a new node consisting of value 5, the BST of
Figure 5.11 results.

Figure 5.10: An example BST for insertion

5.3.2 Deletion of a node from a Binary Search Tree

The algorithm to delete a node with key from a binary

search tree is not simple where as many cases needs to
be considered.

• If the node to be deleted has no sons, then it may

be deleted without further adjustment to the tree.

• If the node to be deleted has only one subtree, then

its only son can be moved up to take its place.

62
 Figure 5.11: Figure 5.10 after insertion of 5

• The node p to be deleted has two subtrees, then

its inorder successor s must take its place. The
inorder successor cannot have a left subtree. Thus,
the right son of s can be moved up to take the place
of s.

Example: Consider the following cases in which node 5

needs to be deleted.
1. The node to be deleted has no children.

2. The node has one child

3. The node to be deleted has two children. This case

is complex. The order of the binary tree must be kept
intact.

63
 Figure 5.12: Deletion of 5

Figure 5.13: Deletion of 5

5.3.3 BST Searching

Searching a key in BST is very easy. And, it is fast also.

The following recursive algorithm gives this operation.

Algorithm : BST Searching

s e a r c h ( t r e e ∗ node , key )
{
i f ( node !=NULL)
{
i f ( node−>data == key )

64
 {
print ‘ ‘ Element found ‘ ‘ ;
}
e l s e i f ( key < node−>data )
{
s e a r c h ( node−>l e f t , key )
}
e l s e i f ( key > node−>data )
{
s e a r c h ( node−>r i g h t , key )
}
else
p r i n t ‘ ‘ Element not found ‘ ‘
}
}

5.4 searching

Searching is the process of looking for something: Find-

ing one piece of data that has been stored within a whole
group of data. It is often the most time-consuming part
of many computer programs. There are a variety of
methods, or algorithms, used to search for a data item,
depending on how much data there is to look through,
what kind of data it is, what type of structure the data
is stored in, and even where the data is stored - inside
computer memory or on some external medium.
Till now, we have studied a variety of data structures,
their types, their use and so on. In this section, we will
concentrate on some techniques to search a particular
data or piece of information from a large amount of data.

65
There are basically two types of searching techniques,
Linear or Sequential Search and Binary Search.
Searching is very common task in day-to-day life, where
we are involved some or other time, in searching either
for some needful at home or office or market, or search-
ing a word in dictionary. In this section, we see that
if the things are organized in some manner, then search
becomes efficient and fast.

Linear Search

Linear search is not the most efficient way to search for an

item in a collection of items. However, it is very simple to
implement. Moreover, if the array elements are arranged
in random order, it is the only reasonable way to search.
In addition, efficiency becomes important only in large
arrays; if the array is small, there aren’t many elements
to search and the amount of time it takes is not even
noticed by the user. Thus, for many situations, linear
search is a perfectly valid approach.
The Linear Search is applicable to a table which it
should be organised in an array. Let us assume that a
file contains ‘n’ records and a record has ‘a’ fields but
only one key. The values of key are organised in an array
say ‘m’. As the file has ‘n’ records, the size of array will
be ‘n’ and value at position R(i) will be the key of record
at position i. Also, let us assume that ‘el’ is the value for
which search has to be made or it is the search argument.
The following is a simple algorithm for Linear Search.
Here,
m - represents the unordered array of elements
n - represents number of elements in the array and
el - represents the value to be searched in the list

66
step 1 [Initialize]
k=0, flag=1

step 2 Repeat step 3 for k=0,1,2 . . . n-1

step 3 if (m[k]=el )then

flag=0
print ‘Search is successful and element is found at
location (k+1), and stop’
endif

step 4 if (flag=1) then

print ‘Search is unsuccessful’
endif

step 5 stop

Binary Search

An unsorted array is searched by linear search that scans

the array elements one by one until the desired element is
found. The reason for sorting an array is that we search
the array “quickly“. Now, if the array is sorted, we can
employ binary search, which brilliantly halves the size of
the search space each time it examines one array element.
An array-based binary search selects the middle ele-
ment in the array and compares its value to that of the
key value. Because, the array is sorted, if the key value
is less than the middle value then the key must be in
the first half of the array. Likewise, if the value of the
key item is greater than that of the middle value in the
array, then it is known that the key lies in the second
half of the array. In either case, we can, in effect, “throw
out“ one half of the search space or array with only one
comparison.

67
 Now, knowing that the key must be in one half of
the array or the other, the binary search examines the
mid value of the half in which the key must reside. The
algorithm thus narrows the search area by half at each
step until it has either found the key data or the search
fails.
As the name suggests, binary means two, so it divides
an array into two halves for searching. This search is
applicable only to an ordered list (in either ascending or
in descending order).

Algorithm: Binary Search

step 1 Declare an array ‘k’ of size ‘n‘ i.e. k(n) is an

array which stores all the keys of a file containing
‘n’ records

step 2 i=0

step 3 low = 0, high=n-1

step 4 while (low <= high) do

mid = (low + high)/2
if (key=k[mid]) then write ‘record is at position’,
mid+1 //as the array starts from the 0th position
else
if(key < k[mid]) then
high = mid - 1 else low = mid + 1
endif
endif
endwhile

step 5 Write ‘Sorry, key value not found’

step 6 Stop

68
5.5 sorting

Retrieval of information is made easier when it is stored

in some predefined order. Sorting is, therefore, a very
important computer application activity. Many sorting
algorithms are available. Different environments require
different sorting methods. Sorting algorithms can be
characterized in the following two ways:

1. Simple algorithms which require the order of n 2

(written as O(n2 ))comparisons to sort n items.

2. Sophisticated algorithms that require the O(n log

n)comparisons to sort n items.

The difference lies in the fact that the first method

moves data only over small distances in the process of
sorting, whereas the second method moves data over
large distances, so that items settle into the proper order
sooner, thus resulting in fewer comparisons. Performance
of a sorting algorithm can also depend on the degree of
order already present in the data.
There are two basic categories of sorting methods: In-
ternal Sorting and External Sorting. Internal sorting is
applied when the entire collection of data to be sorted is
small enough so that the sorting can take place within
the main memory. The time required to read or write
is not considered to be significant in evaluating the per-
formance of internal sorting methods. External sorting
methods are applied to larger collection of data which re-
side on secondary devices. Read and write access times
are a major concern in determining sorting performances
of such methods.

69
5.5.1 Insertion Sort

This is a naturally occurring sorting method exemplified

by a card player arranging the cards dealt to him. He
picks up the cards as they are dealt and inserts them into
the required position. Thus at every step, we insert an
item into its proper place in an already ordered list.
We will illustrate insertion sort with an example (refer
to Figure 5.14) before presenting the formal algorithm.
Example : Sort the following list using the insertion sort
method: Thus to find the correct position search the list

Figure 5.14: Insertion Sort

till an item just greater than the target is found. Shift

all the items from this point one down the list. Insert
the target in the vacated slot. Repeat this process for all
the elements in the list. This results in sorted list.

70
5.5.2 Bubble Sort

In this sorting algorithm, multiple swappings take place

in one pass. Smaller elements move or ‘bubble’ up to the
top of the list, hence the name given to the algorithm.
In this method, adjacent members of the list to be
sorted are [Link] the item on top is greater than
the item immediately below it, then they are swapped.
This process is carried on till the list is sorted.
The detailed algorithm given in the figure5.15 :

Figure 5.15: Bubble Sort

Total number of comparisons in Bubble sort :

= (N − 1) + (N − 2)... + 2 + 1
= (N − 1) ∗ N /2 = O (N 2 )
This inefficiency is due to the fact that an item moves
only to the next position in each pass.

5.5.3 Quick Sort

This is the most widely used internal sorting algorithm.

In its basic form, it was invented by C.A.R. Hoare in
1960. Its popularity lies in the ease of implementation,

71
moderate use of resources and acceptable behaviour for
a variety of sorting cases. The basis of quick sort is the
divide and conquer strategy i.e. Divide the problem [list
to be sorted] into sub-problems [sub-lists], until solved
sub problems [sorted sub-lists] are found. This is imple-
mented as follows: Choose one item A[I] from the list A[
].
Rearrange the list so that this item is in the proper
position, i.e., all preceding items have a lesser value and
all succeeding items have a greater value than this item.

1. Place A[0], A[1] .. A[I-1] in sublist 1

2. A[I]

3. Place A[I + 1], A[I + 2] ... A[N] in sublist 2

4. Repeat steps 1 & 2 for sublist1 & sublist2 till A[ ]

is a sorted list.

As can be seen, this algorithm has a recursive structure.

The ‘divide’ procedure is of utmost importance in this
algorithm. This is usually implemented as follows:

1. Choose A[I] as the dividing element.

2. From the left end of the list (A[O] onwards) scan

till an item A[R] is found whose value is greater
than A[I].

3. From the right end of list [A[N] backwards] scan

till an item A[L] is found whose value is less than
A[1].

4. Swap A[R] & A[L].

72
 5. Continue steps 2, 3 & 4 till the scan pointers cross.
Stop at this stage.

6. At this point, sublist1 & sublist are ready.

7. Now do the same for each of sublist1 & sublist2.

Program in figure 5.16 gives the program segment for

Quick sort. It uses recursion.

73
 Figure 5.16: Quick Sort

74