Data Structure

(CSC303)
Lecture 1
Shilpa Ingoley
Syllabus for DS
• Data Type
• A data type consists of two parts:
i) a set of data
ii) and the operations that can be performed on the data.

Data Type = Permitted Data Values + Operations

What is Data Structure?

• Data structure is a way to organize data in some way so that we can

perform the operations on this data in effective way.

• Examples: list, stack, queue, tree, graph, hash table, etc.

• We select these data structure depending upon which type of

operation is needed with data.
 What is Data Structures?
• Informally, a data structure is basically a group of data
elements that are put together under one name. Definition
• Formally, data structure is a particular way of storing
and organizing data in a computer so that it can be
used efficiently.
• They are essential ingredients of many efficient
algorithms as they enable the programmers to manage Efficient
huge amounts of data efficiently.
• The idea is to reduce the space and time
complexities of different tasks like storing and
searching.
Compiler Operating
DBMS Application
Design System
Artificial
Graph
Intelligence
ics 10
 Steps of selecting a data
structure
to solve a problem • Quantify the
resource constraints
Analysis for each operation. Selection
• Analysis of the • Each problem has
problem to constraint on space • Select the data
determine the and time structure that best
basic operations meets these
that must be
Constrain requirements.
supported ts
• For example, basic
operation may
include
inserting/deleting/
searching a data
 Elementary Data Structure
Organization
• Data structures are building blocks of a program.
• A program built using improper data structures may not work as
expected, hence choose most appropriate data structures for a
program.
• Value or set of values
Data • Value of a variable or
a constant

• composed of one or more

• Data item that does not have
Elementary Group subordinate data items
subordinate data items
• Eg. roll number Item Item • Eg. first name, middle name, and last
name

12
• Data structure is concerned with following:
o Organization of data

o Associativity among data elements.

o Accessing methods

o Operations on data
Data Structure Operations
Traversing
Searching
Insertion
Deletion
Creation
Sorting
Merging
 Insertion Deletion
Adding new data items to the Removing (deleting) a
given list of data items. particular data item from the
E.g. to add the details of a given collection of data
new student who has items.
recently joined the course. E.g.to delete the name of a
student who has left the
course.
Searching Sorting
Finding the location of one Data items can be arranged
or more data items that in some order (ascending
satisfy the given constraint. /descending order)
Such a data item may or E.g. arranging the names of
may not be present. students in a class in an
E.g. find the names of all alphabetical order, or
the students who secured calculating the top three
100 marks. winners

Traversin Merging
OPERATIONS
g
It means to access each Lists of two sorted data
data item exactly once
so that it can be
ON DATA items can be combined
to form a single list of
processed. E.g. to print
the names of all the
STRUCTURES sorted data items.

students in a class.
Applications
Airline/Train reservation
Address Book
Compiler Design
Operating System
Database Management Systems
Statistical Analysis Packages
Graphic Designs
Artificial Intelligence(AI)
Simulation
Communication Network Analysis
Classification of Data Structure
Classification of Data Structure
(Contd.)
• Primitive Data Structure
o These are basic structures which are directly operated by the machine
instructions.
o They have different internal representations on different machines
o Eg: int, float, char
• Non-Primitive Data Structure
o These type of data structures are derived from the primitive ones.
o These data structure emphasis on structuring of group of similar or different
data items.
o Eg: Arrays, list, files
Classification of Data Structure
(Contd.)
• Linear Data Structure:
• A data structure is said to be linear if its elements form sequence or linear list
• Eg: Arrays, linked list, stack, queue

• Non-linear Data Structure:

• Non Linear Data Structure is that if one element can be connected to more
than one adjacent element then it is non linear data structure.
• One-many or many-many relationships are handled through nonlinear data
structure.
• Eg: tree, graph
Some Data Structures
Abstract Data Type:
• An ADT is defined as a mathematical model of data objects that make
up a data type as well as the functions that operate on these objects.
• ADT is the structure considered without regard to its implementation.
• It can be thought of as a description of the data in the structure with
a list of operations that can be performed on the data within that
structure.
Abstract Data Types
• It is a type (or class) for objects whose behavior is defined by
a set of value and a set of operations.
• The definition of ADT only mentions what operations are to
be performed but not how these operations will be
implemented.
• It does not specify how data will be organized in memory and
what algorithms will be used for implementing the
operations.
• It is called “abstract” because it gives an implementation-
independent view. The process of providing only the
essentials and hiding the details is known as abstraction.
• For example, stacks and queues are perfect examples of an ADT.
These ADTs can be implemented using an array or a linked list.
 Abstract Data Types(1)

• Data type of a variable is the set of values that the variable can
take. E.g. int, char, float, and double.
• For primitive type (built-in data type), two things are considered:
• A data item with certain characteristics
• The permissible operations on that data.
• Eg. An int variable can contain any whole-number value from –
32768 to 32767 and can be operated with the operators +, –, *,
and /.
• In other words, the operations that can be performed on a data
type are an inseparable part of its identity.
• Therefore, ADT = Type of data + Operations
• Abstract means considered apart from the tailed specifications or
implementation.
25
 Abstract Data Types(3)

• Advantages of ADTs
• Code is easier to understand (e.g., it is easier to see "high-
level" steps being performed, not obscured by low-level code).
• Implementations of ADTs can be changed (e.g., for efficiency)
without requiring changes to the program that uses the ADTs.
• ADTs can be reused in future programs.

26
Homework

• Write a Menu-driven program in ‘C’ using functions to perform the

following :
o To find Factorial

o To generate Fibonacci series

o Reversing the number