Introduction To

Data Structure

Dr. Jyoti Srivastava

 Introduction
Course Name: Data Structures

Course Code: CS-306

Course Type: Open Elective-I/II

Contact Hours/Week: 3L

Course Credits: 03

Course Objectives
To impart knowledge about linear and non-linear data structures as the
foundational base for computer solutions to problems.
To introduce the fundamental concepts relevant to binary trees, binary tree
traversals, binary search trees and perform related analysis to solve problems.
To enable the students to understand various types of sorting algorithms.
 Syllabus
Unit Course Content Lectures
Number
UNIT-01 Introduction: Data types, data structures, abstract data types, the running time of 07L
a program, the running time and storage cost of algorithms, complexity,
asymptotic complexity, big O notation, obtaining the complexity of an algorithm.
UNIT-02 Development of Algorithms: Notations and Analysis, Storage structures for 10L
arrays - sparse matrices - structures and arrays of structures, Stacks and Queues:
Representations, implementations and applications. Linked Lists: Singly linked
lists, Linked stacks and queues, operations on Polynomials, Doubly Linked Lists,
Circularly Linked Lists, Operations on linked lists.
UNIT-03 Trees: Basic terminology, General Trees, Binary Trees, Tree Traversing: in-order, 07L
pre-order and post-order traversal, building a binary search tree, Operations on
Binary Trees.
UNIT-04 Graphs: Basic definitions, representations of directed and undirected graphs, the 06L
single-source shortest path problem, the all-pair shortest path problem, traversals
of directed and undirected graphs, directed acyclic graphs, strong components,
minimum cost spanning tress, articulation points and bi-connected components,
graph matching.
UNIT-05 Sorting and Searching Techniques: Bubble sorting, Insertion sort, Selection 06L
sort, Shell sort, Merge sort, Heap and Heap sort, Quick sort, Sequential searching,
Binary Searching, Index searching, Hash table methods.
 Syllabus
Course Outcomes
Upon successful completion of the course, the students will be able to
CO1: Interpret and compute asymptotic notations of an algorithm to analyze the time complexity.
CO2: Use of linear and non-linear data structures as the foundational base for computer solutions
to problems.
CO3: Demonstrate the ability to implement various types of static and dynamic lists.
CO4: Implement binary trees, binary tree traversals, and binary search trees and perform related
analysis to solve problems.
CO5: Implement various types of sorting algorithms.

Books and References

1. An Introduction to Data Structures with applications by J.P. Tremblay and P.G. Sorenson, Tata
McGraw Hill.
2. Data structures, Algorithms ad Applications in C++ by Sartaj Sahni, WCB/McGraw Hill.
3. Data Structures and Algorithms by Alfred V. Aho, Jeffrey D. Ullman and John E. Hopcroft,
Addison Wesley.
4. Data Structures using C by Y. Langsam, M. J. Augenstein and A. M. Tenenbaum, Pearson
Education.
5. Data Structures – A Pseudocode Approach with C by Richard F. Gilberg and Behrouz A.
Data Management Concepts

• A program should give correct results but along with

that it should run efficiently.

• Efficient program executes:

• Minimum time
• Minimum memory space

• To write efficient program we need to apply Data

management concepts.
 Data Management Concepts
Data Management concept includes,
• Data collection
• Organization of data in proper structure
• Developing and maintaining routines for quality assurance

“A data structure is a particular way of storing and

organizing data in a computer so that it can be used efficiently.”
Data Types
• A Data type refers to a named group of data which
share similar properties or characteristics and which
have common behaviour among them.

• Primitive data types (Built-in Data Type or Basic

Data Type) are predefined, supported by C
language.
• int, char, float, double, boolean
 Data Types
• Non-Primitive data types (Derived Data Type) are not
defined by C language, but are created by the
programmer using the built-in data types. These data
types are implementation independent as they can be
implemented in one or the other way.
• Example:
1. Arrays
2. Linked List
3. Stacks
4. Queue
5. Graph
Need for Data Structure
• Data Search − Consider an inventory of 1 million(106) items of
a store. If the application is to search an item, it has to search an
item in 1 million(106) items every time slowing down the search.
As data grows, search will become slower.
• Processor speed − Processor speed although being very high,
falls limited if the data grows to billion records.
• Multiple requests − As thousands of users can search data
simultaneously on a web server, even the fast server fails while
searching the data.
• Data can be organized in a data structure in such a way that all
items may not be required to be searched, and the required data
can be searched almost instantly.
 How to Select Data Structure
Data structures are the building blocks of a program. And hence
the selection of particular data structure stresses on the following
things :
1. Analysis of the problem to determine basic operations like
insert/delete/search a data in DS

2. Quantify the resource constraints for each operation

3. Select DS that best meets these requirements

4. The data structures must be rich enough in structure to

reflect the relationship existing between the data.

5. And the structure should be simple so that we can process

data effectively whenever required.
 Basic Operations
The data in the data structures are processed by certain
operations. The particular data structure chosen largely
depends on the frequency of the operation that needs to
be performed on the data structure.

• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging
Types of Data Structure
1. Linear Data Structure
• Elements are stored sequentially
• We can traverse either forward or backward
• Examples: Arrays, Stacks, Queues, Linked list
2. Nonlinear Data Structure
• Not stored in sequential order
• Branches to more than one node
• Can’t be traversed in a single run
• Examples: Tree, Graphs
Types of Data Structure
Types of Data Structure

1. Arrays
• An array is a data structure consisting of a
collection of similar data elements, each identified
by one array index.
• The elements in array are stored in consecutive
memory locations.
Arrays
• Array Syntax:
int Age[10];

• Limitations of Arrays:
• Fixed size
• Data elements are stored in continuous memory
locations which may not be available, always
• Adding and removing of elements is tough because
of shifting the elements from their positions
Types of Data Structure
2. Linked List
• Consisting of a group of nodes which together
represent a sequence.

• Under the simplest form, each node is composed of a

datum and a reference (in other words, a link) to the
next node in the sequence.

• This structure allows for efficient insertion or

removal of elements from any position in the
sequence.
Linked List

A linked list whose nodes contain two fields: an

integer value and a link to the next node. The last
node is linked to a terminator (NULL pointer) used
to signify the end of the list.
Linked List
• Advantage: Provides quick insert and delete
operations
• Disadvantage: Slow search operations and requires
more memory space.
Types of Data Structure
3. Stacks
• Stack can be represented as a linear array.

• Every stack has a variable TOP associated with

it, to store the address of the topmost element of
the stack.
Stacks
• A stack is a last in, first out (LIFO) data structure.
If TOP = NULL, then it indicates stack is empty
If TOP = MAX, then it indicates stack is full.
Stacks
• Elements are removed from the stack in the reverse
order to the order of their addition: therefore, the
lower elements are those that have been on the stack
the longest.

• Advantage: last-in first-out (LIFO) access.

• Disadvantage: Slow access to other elements.
Types of Data Structure
4. Queue
• Queue is a data structure in which data can be
added to one end and retrieved from the other.

• You can think of it as a line in a grocery store. The

first one in the line is the first one to be served. Just
like a queue.

• A queue is also called a FIFO (First In First Out) to

demonstrate the way it accesses data.
Queue
• Advantage: Provides first-in, first-out data access.
• Disadvantage: Slow access to other items.
Types of Data Structure
5. Trees
• A tree is a widely used data structure that simulates a
hierarchical tree structure with a set of linked nodes.

• Every node contains a left pointer, a right pointer and a

data element.

• Every tree has a root element pointed by a root pointer.

• If root = NULL, tree is empty.

 Trees
A simple unordered tree; in this diagram, the node
labelled 7 has two children, labelled 2 and 6, and one
parent, labelled 2. The root node, at the top, has no
parent.
Trees
• Advantage: Provides quick search, insert, delete
operations.

• Disadvantage: Complicated deletion algorithm.

• Example: Family Tree

Types of Data Structure
6. Graph
• A graph is a data structure that is meant to
implement the graph concepts from mathematics.

• It is basically a collection of vertices(nodes) and

edges that connect these vertices.

• A graph is often viewed as a generalization of the

tree structure, where complex relationship can be
represented.
Graph
• Advantage: Best models real-world situations.
• Disadvantages: Some algorithms are slow and very
complex.
Abstract Data Type
• ADT is the way we look at a Data Structure,
focusing on what is does and ignoring how it
does its job.

• Examples: Stack, Queue

• Whenever end user uses Queue, he is concerned

about only the type of data and operations that can
be performed on it.
Abstract Data Type
• Fundamentals of how the data is stored is invisible
to users.

• They will have push() and pop() functions only.

EXAMPLES & REAL LIFE APPLICATIONS

• A company contains employee file in which each record

contain the following data for a given employee :
• Name, Address, Telephone number, Employee age,
gender , employ number.

• Suppose the company wants to announce a meeting through a

mailing.
Then one would traverse the file to obtain employee
name and address for each member.
EXAMPLES & REAL LIFE APPLICATIONS
• A company contains employee file in which each record
contain the following data for a given employee :
• Name, Address, Telephone number, Employee age,
gender , employ number.
• Suppose one wants to find the name of all members living in a
certain area.
Again one would traverse the file to obtain the data.

• Suppose one wants to obtain address for the given employee

name.
Then one would search the file for the record containing
employee name.
EXAMPLES & REAL LIFE APPLICATIONS
• A company contains employee file in which each record
contain the following data for a given employee :
• Name, Address, Telephone number, Employee age, gender , employ
number.

• Suppose a new person joins the company.

Then one would insert his or her record into the file.

• Suppose an employee dies or resign.

Then one would delete his or her record from the file.
EXAMPLES & REAL LIFE APPLICATIONS

• A company contains employee file in which each record

contain the following data for a given employee :
• Name, Address, Telephone number, Employee age,
gender , employ number.

• Suppose an employee has moved and has a new address and

telephone number.
Given the name of the member, one would first need to
search for the record in the file. Then one would perform the
“update”- i..e., change items in the record with the new data.
EXAMPLES & REAL LIFE APPLICATIONS

• A company contains employee file in which each record

contain the following data for a given employee :
• Name, Address, Telephone number, Employee age,
gender , employ number.

• Suppose one wants to find the number of members 65 or

older.
Again one would traverse the file, counting such
members.
Call by value and call by
reference in C
 Call by Value
#include <stdio.h>
#include <conio.h>
void change(int num) {
printf("Before adding value inside function num=%d \n",num);
num=num+100;
printf("After adding value inside function num=%d \n", num);
}
Before function call x=100
int main() {
Before adding value inside function num=100
int x=100; After adding value inside function num=200
After function call x=100
clrscr();
printf("Before function call x=%d \n", x);
change(x);//passing value in function
printf("After function call x=%d \n", x);
getch();
return 0; }
Call by Reference
#include <stdio.h>
#include <conio.h>
void change(int *num) {
printf("Before adding value inside function num=%d \n",*num);
(*num) += 100;
printf("After adding value inside function num=%d \n", *num);
}
Before function call x=100
Before adding value inside function num=100
int main() { After adding value inside function num=200
int x=100; After function call x=200

clrscr();
printf("Before function call x=%d \n", x);
change(&x);//passing reference in function
printf("After function call x=%d \n", x);
getch();
return 0; }
Differences between call by value and
call by reference
S. No. Call by value Call by reference

1 A copy of value is passed to An address of value is passed

the function to the function

2 Changes made inside the Changes made inside the

function is not reflected on function is reflected outside the
other functions function also
Example using Call by Value
#include <stdio.h>
void swapByValue(int, int); /* Prototype */
int main() /* Main function */
{
int n1 = 10, n2 = 20;
/* actual arguments will be as it is */
swapByValue(n1, n2);
printf("n1: %d, n2: %d\n", n1, n2);
}
void swapByValue(int a, int b) OUTPUT
{ ======
int t; n1: 10, n2: 20
t = a; a = b; b = t;
}
Example using Call by Reference
#include <stdio.h>
void swapByReference(int*, int*); /* Prototype */
int main() /* Main function */
{
int n1 = 10, n2 = 20;
/* actual arguments will be altered */
swapByReference(&n1, &n2);
printf("n1: %d, n2: %d\n", n1, n2);
}
void swapByReference(int *a, int *b)
OUTPUT
{
======
int t;
n1: 20, n2: 10
t = *a; *a = *b; *b = t;
}