BCA 3rd Sem ( Data Structure)

Syllabus Of Data Structure

Detailed Contents
Unit -I
Introduction to Data Structures:
Algorithms and Flowcharts, Basics Analysis on Algorithm, Complexity of Algorithm,
Introduction and Definition of Data Structure, Classification of Data, Arrays, Various
types of Data Structure, Static and Dynamic Memory Allocation, Function,
Recursion.

Arrays, Pointers and Strings:

Introduction to Arrays, Definition, One Dimensional Array and Multidimensional
Arrays, Pointer, Pointer to Structure, various Programs for Array and Pointer. Strings.
Introduction to Strings, Definition, Library Functions of Strings.
Unit-II
Stacks and Queue :-
Introduction to Stack, Definition, Stack Implementation, Operations of Stack,
Applications of Stack and Multiple Stacks. Implementation of Multiple Stack Queues,
Introduction to Queue, Definition, Queue Implementation, Operations of Queue,
Circular Queue, De-queue and Priority Queue.
Unit-III
Linked Lists and Trees
Introduction, Representation and Operations of Linked Lists, Singly Linked List,
Doubly Linked List, Circular Linked List, And Circular Doubly Linked List.

Trees
Introduction to Tree, Tree Terminology Binary Tree, Binary Search Tree, Strictly
Binary Tree, Complete Binary Tree, Tree Traversal, Threaded Binary Tree, AVL
Tree B Tree, B+ Tree.
Unit -IV
Graphs, Searching, Sorting and Hashing Graphs:
Introduction, Representation to Graphs, Graph Traversals Shortest Path Algorithms.
Searching and Sorting:
Searching, Types of Searching, Sorting, Types of sorting like quick sort, bubble sort,
merge sort, selection sort.
Hashing:
Hash Function, Types of Hash Functions, Collision, Collision Resolution Technique
(CRT), Perfect Hashing

1
BCA 3rd Sem ( Data Structure)

INDEX

S.No Contents Page No

1 Introduction to Data Structures 5-30

2 Arrays, Pointers and Strings: 30-36

3 Stacks and Queue 38-81

4 Linked Lists and Trees 83-102

5 Trees 102-142

6 Graphs, Searching, Sorting and Hashing Graphs 144-160

7 Searching and Sorting 160-171

8 Hashing 171-179

2
BCA 3rd Sem ( Data Structure)

UNIT I

3
BCA 3rd Sem ( Data Structure)

 Introduction to Data Structures

Basicconceptofdata
Data
Data is a raw and unorganized fact that required to be processed to make it
meaningful. Data can be simple at the same time unorganized unless it is
organized. Generally, data comprises facts, observations, perceptions numbers,
characters, symbols, image, etc. Data is always interpreted, by a human or
machine, to derive meaning. So, data is meaningless. Data contains numbers,
statements, and characters in a raw form.

Examples of data are weights, prices, costs, numbers of items sold, employee
names, product names, addresses, tax codes, registration marks etc

Information
Information is a set of data which is processed in a meaningful way according to
the given requirement. Information is processed, structured, or presented in a given
context to make it meaningful and useful.

It is processed data which includes data that possess context, relevance, and
purpose. It also involves manipulation of raw data.

Information assigns meaning and improves the reliability of the data. It helps to
ensure undesirability and reduces uncertainty. So, when the data is transformed
into information, it never has any useless details.

Example :- Information is data that has been converted into a more useful or
intelligible form.

4
BCA 3rd Sem ( Data Structure)

Difference between Data and Information

Data Information

Data is in the form of numbers, letters, Ideas and inferences

or a set of characters.

It can be structured, tabular data, graph, Language, ideas, and thoughts based on
data tree, etc. the given data.
Data does not have any specific It carries meaning that has been
purpose. assigned by interpreting data.
Data that is collected Information that is processed.
Data is a single unit and is raw. It alone Information is the product and group of
doesn't have any meaning. data which jointly carry a logical
meaning.
It never depends on Information It depended on Data.
Measured in bits and bytes. Measured in meaningful units like time,
quantity, etc.
It can't be used for decision making It is widely used for decision making.

It is low-level knowledge. It is the second level of knowledge.

Data depends upon the sources for Information depends upon data.
collecting data.

 Problem Analysis

5
BCA 3rd Sem ( Data Structure)

Problem Analysis: Identify the issues. Be clear about what the problem is. ...

Understand everyone's interests. ...

List the possible solutions (options) ...

Evaluate the options.

Select an option or options. ...

Document the agreement(s). ...

Agree on contingencies, monitoring, and evaluation.

Algorithm Development

An algorithm in general is a sequence of steps to solve a particular problem.

Algorithms are universal. The algorithm you use in C programming language is
also the same algorithm you use in every other language. An algorithm produces
the same output information given the same input information, and several short

6
BCA 3rd Sem ( Data Structure)

algorithms can be combined to perform complex tasks such as writing a computer

program.

Flow Chart

A flowchart is a formalized graphic representation of a logic sequence, work or

manufacturing process, organization chart, or similar formalized structure. The
purpose of a flow chart is to provide people with a common language or reference
point when dealing with a project or process. Flowcharts use simple geometric
symbols and arrows to define relationships.

Program Coding

A Programming (or coding) language is a set of syntax rules that define how code
should be written and formatted. Thousands of different programming languages
make it possible for us to create computer software, apps and websites.

Compile and Execution

Compilation

First, the source ‘.java’ file is passed through the compiler, which then encodes the
source code into a machine independent encoding, known as Bytecode. The
content of each class contained in the source file is stored in a separate ‘.class’ file.
While converting the source code into the bytecode.

Execution

The class files generated by the compiler are independent of the machine or the
OS, which allows them to be run on any system. To run, the main class file (the
class that contains the method main) is passed to the JVM, and then goes through
three main stages before the final machine code is executed.

Debugging and testing

Testing means verifying correct behavior. Testing can be done at all stages of
module development: requirements analysis, interface design, algorithm design,
implementation, and integration with other modules. In the following, attention

7
BCA 3rd Sem ( Data Structure)

will be directed at implementation testing. Implementation testing is not restricted

to execution testing. An implementation can also be tested using correctness
proofs, code tracing, and peer reviews, as described below.

Debugging is a cyclic activity involving execution testing and code correction. The
testing that is done during debugging has a different aim than final module testing.
Final module testing aims to demonstrate correctness, whereas testing during
debugging is primarily aimed at locating errors. This difference has a significant
effect on the choice of testing strategies.

Documentation

The documentation section contains a set of comment including the name of the
program other necessary details. Comments are ignored by compiler and are used
to provide documentation to people who reads that code.

 Algorithm
An algorithm is defined as a step-by-step procedure or method for solving a
problem by a computer in a finite number of steps. Steps of an algorithm definition
may include branching or repetition depending upon what problem the algorithm is
being developed for. While defining an algorithm steps are written in human
understandable language and independent of any programming language. We can
implement it in any programming language of our choice.
Besides merely being a finite set of rules which gives a sequence of operations for
solving a specific type of problem, a well defined algorithm has five important

Features:

Finiteness. An algorithm must always terminate after a finite number of steps.

Definiteness. Each step of an algorithm must be precisely defined; the actions to

be carried out must be rigorously and unambiguously specified for each case.

Input. An algorithm has zero or more inputs, i.e, quantities which are given to it
initially before the algorithm begins.
8
BCA 3rd Sem ( Data Structure)

Output. An algorithm has one or more outputs i.e, quantities which have a
specified relation to the inputs.

Effectiveness. An algorithm is also generally expected to be effective. This means

that all of the operations to be performed in the algorithm must be sufficiently
basic that they can in principle be done exactly and in a finite length of time.

Characteristics of an Algorithm
An algorithm must follow the mentioned below characteristics:

Input: An algorithm must have 0 or well defined inputs.

Output: An algorithm must have 1 or well defined outputs, and should match with
the desired output.

Feasibility: An algorithm must be terminated after the finite number of steps.

Independent: An algorithm must have step-by-step directions which is

independent of any programming code.

Unambiguous: An algorithm must be unambiguous and clear. Each of their steps

and input/outputs must be clear and lead to only one meaning.

Qualities of a good algorithm

Input and output should be defined precisely.

Each steps in algorithm should be clear and unambiguous.

Algorithm should be most effective among many different ways to solve a

problem.

An algorithm shouldn't have computer code. Instead, the algorithm should be

written in such a way that, it can be used in similar programming languages.

Write an algorithm to add two numbers entered by user.

Step 1: Start

9
BCA 3rd Sem ( Data Structure)

Step 2: Declare variables num1, num2 and sum.

Step 3: Read values num1 and num2.

Step 4: Add num1 and num2 and assign the result to sum.

sum←num1+num2

Step 5: Display sum

Step 6: Stop

Write an algorithm to find the largest among three different numbers entered
by user.

Step 1: Start

Step 2: Declare variables a,b and c.

Step 3: Read variables a,b and c.

Step 4: If a>b

If a>c

Display a is the largest number.

Else

Display c is the largest number.

Else

If b>c

Display b is the largest number.

Else

Display c is the greatest number.

Step 5: Stop

10
BCA 3rd Sem ( Data Structure)

Advantages of Algorithms:

 It is a step-wise representation of a solution to a given problem, which

makes it easy to understand.
 An algorithm uses a definite procedure.
 It is not dependent on any programming language, so it is easy to understand
for anyone even without programming knowledge.
 Every step in an algorithm has its own logical sequence so it is easy to
debug.
 By using algorithm, the problem is broken down into smaller pieces or steps
hence, it is easier for programmer to convert it into an actual program.

Disadvantages of Algorithms:

 Alogorithms is Time consuming.

 Difficult to show Branching and Looping in Algorithms.
 Big tasks are difficult to put in Algorithms.

 Big O
For any monotonic functions f(n) and g(n) from the positive integers to the positive
integers, we say that f(n) = O(g(n)) when there exist constants c > 0 and n0 > 0
such that

f(n) ≤ c * g(n), for all n ≥ n0

Intuitively, this means that function f(n) does not grow faster than g(n), or that
function g(n) is an upper bound for f(n), for all sufficiently large n→∞

Here is a graphic representation of f(n) = O(g(n)) relation:

11
BCA 3rd Sem ( Data Structure)

Examples:

1 = O(n)

n = O(n2)

log(n) = O(n)

Constant Time: O(1)

An algorithm is said to run in constant time if it requires the same amount of time
regardless of the input size. Examples:

array: accessing any element

fixed-size stack: push and pop methods

fixed-size queue: enqueue and dequeue methods

Linear Time: O(n)

An algorithm is said to run in linear time if its time execution is directly

proportional to the input size, i.e. time grows linearly as input size increases.
Examples:

array: linear search, traversing, find minimum

ArrayList: contains method

queue: contains method

12
BCA 3rd Sem ( Data Structure)

Logarithmic Time: O(log n)

An algorithm is said to run in logarithmic time if its time execution is proportional

to the logarithm of the input size. Example:

Binary Search

Recall the "twenty questions" game - the task is to guess the value of a hidden
number in an interval. Each time you make a guess, you are told whether your
guess iss too high or too low. Twenty questions game imploies a strategy that uses
your guess number to halve the interval size. This is an example of the general
problem-solving method known as binary search:

locate the element a in a sorted (in ascending order) array by first comparing a with
the middle element and then (if they are not equal) dividing the array into two
subarrays; if a is less than the middle element you repeat the whole procedure in
the left subarray, otherwise - in the right subarray. The procedure repeats until a is
found or subarray is a zero dimension.

Note, log(n) < n, when n→∞. Algorithms that run in O(log n) does not use the
whole input.

 Flowchart
Flowchart is a diagrammatic representation of sequence of logical steps of a
program. Flowcharts use simple geometric shapes to depict processes and arrows
to show relationships and process/data flow.

Flowchart Symbols

Here is a chart for some of the common symbols used in drawing flowcharts.

Symbol Symbol Name Purpose

Start/Stop Used at the beginning and end of the

algorithm to show start and end of the

13
BCA 3rd Sem ( Data Structure)

program.

Indicates processes like mathematical

Process
operations.

Used for denoting program inputs and

Input/ Output
outputs.

Stands for decision statements in a program,

Decision where answer is usually Yes or No.

Shows relationships between different

Arrow shapes.

Connects two or more parts of a flowchart,

On-page Connector which are on the same page.

Connects two parts of a flowchart which are

Off-page Connector spread over different pages.

Guidelines for Developing Flowcharts

These are some points to keep in mind while developing a flowchart −

Flowchart can have only one start and one stop symbol

On-page connectors are referenced using numbers

Off-page connectors are referenced using alphabets

14
BCA 3rd Sem ( Data Structure)

General flow of processes is top to bottom or left to right

Arrows should not cross each other

Example Flowcharts

Here is the flowchart for going to the market to purchase a pen.

Here is a flowchart to calculate the average of two numbers.

15
BCA 3rd Sem ( Data Structure)

 Analysis of Algorithms
The term analysis of algorithms is used to describe approaches to the study of the
performance of algorithms. In this course we will perform the following types of
analysis:

the worst-case runtime complexity of the algorithm is the function defined by the
maximum number of steps taken on any instance of size a.

the best-case runtime complexity of the algorithm is the function defined by the
minimum number of steps taken on any instance of size a.

the average case runtime complexity of the algorithm is the function defined by an
average number of steps taken on any instance of size a.

the amortized runtime complexity of the algorithm is the function defined by a

sequence of operations applied to the input of size a and averaged over time.

Example. Let us consider an algorithm of sequential searching in an array.of size

n.

Its worst-case runtime complexity is O(n)

Its best-case runtime complexity is O(1)
Its average case runtime complexity is O(n/2)=O(n)

Algorithm Complexity

Algorithm Complexity are two types

1) Time complexity of an algorithm signifies the total time required by the

program to run till its completion.

The time complexity of algorithms is most commonly expressed using the big O
notation. It's an asymptotic notation to represent the time complexity.

Time Complexity is most commonly estimated by counting the number of

elementary steps performed by any algorithm to finish execution.

Three cases are consider while calculating Time complexity

16
BCA 3rd Sem ( Data Structure)

Worst case: An algorithm takes more time to execution is called the worst case, it
is mostly in cases of loops where execution time is depends upon the number of
input size.

Average case: An algorithm takes time between the best and worst case to
execution is called the Average case.

Best case: An algorithm takes expected to execution is called the best case.

2) Space Complexity of Algorithms

Whenever a solution to a problem is written some memory is required to complete.

For any algorithm memory may be used for the following:

Variables (This include the constant values, temporary values)

Program Instruction

Execution

Space complexity is the amount of memory used by the algorithm (including the
input values to the algorithm) to execute and produce the result.

Sometime Auxiliary Space is confused with Space Complexity. But Auxiliary

Space is the extra space or the temporary space used by the algorithm during it's
execution.

Space Complexity = Auxiliary Space + Input space

Memory Usage while Execution

While executing, algorithm uses memory space for three reasons:

Instruction Space

It's the amount of memory used to save the compiled version of instructions.

Environmental Stack

Sometimes an algorithm(function) may be called inside another

algorithm(function). In such a situation, the current variables are pushed onto the

17
BCA 3rd Sem ( Data Structure)

system stack, where they wait for further execution and then the call to the inside
algorithm(function) is made.

For example, If a function A() calls function B() inside it, then all th variables of
the function A() will get stored on the system stack temporarily, while the
function B() is called and executed inside the function A().

Data Space

Amount of space used by the variables and constants.

Calculating the Space Complexity

For calculating the space complexity, we need to know the value of memory used
by different type of data type variables, which generally varies for different
operating systems, but the method for calculating the space complexity remains the
same.

Type Size

bool, char, unsigned char, signed char, __int8 1 byte

__int16, short, unsigned short, wchar_t, __wchar_t 2 bytes

float, __int32, int, unsigned int, long, unsigned long 4 bytes

double, __int64, long double, long long 8 bytes

 Data Structure and Types

Data Structure can be defined as the group of data elements which provides an
efficient way of storing and organizing data in the computer so that it can be used
efficiently. Some examples of Data Structures are arrays, Linked List, Stack,
Queue, etc. Data Structures are widely used in almost every aspect of Computer

18
BCA 3rd Sem ( Data Structure)

Science i.e. Operating System, Compiler Design, Artifical intelligence, Graphics

and many more.

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

Basic Terminology

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

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

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

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

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

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

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

an entity.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data structures.
For example: suppose, we have some data and we need to perform the search for a
perticular record. In that case, if we organize our data in an array, we will have to
search sequentially element by element. hence, using array may not be very
19
BCA 3rd Sem ( Data Structure)

efficient here. There are better data structures which can make the search process
efficient like ordered array, binary search tree or hash tables.

Reusability: Data structures are reusable, i.e. once we have implemented a

particular data structure, we can use it at any other place. Implementation of data
structures can be compiled into libraries which can be used by different clients.

Abstraction: Data structure is specified by the ADT which provides a level of

abstraction. The client program uses the data structure through interface only,
without getting into the implementation details.

Characteristics of data structures

Data structures are often classified by their characteristics. Possible characteristics

are:

Linear or non-linear: This characteristic describes whether the data items are
arranged in chronological sequence, such as with an array, or in an unordered
sequence, such as with a graph.

Homogeneous or non-homogeneous: This characteristic describes whether all

data items in a given repository are of the same type or of various types.

Static or dynamic: This characteristic describes how the data structures are
compiled. Static data structures have fixed sizes, structures and memory locations
at compile time. Dynamic data structures have sizes, structures and memory
locations that can shrink or expand depending on the use.

 A DEFINITION OF DATA CLASSIFICATION

Data classification is broadly defined as the process of organizing data by relevant
categories so that it may be used and protected more efficiently. On a basic level,
the classification process makes data easier to locate and retrieve. Data
classification is of particular importance when it comes to risk management,
compliance, and data security.

20