Data Structures
Unit 1: Introduction to Data Structures
Introduction, Types of Data Structures –
Linear and Nonlinear, Concept of ADT
Pre-requisite
3 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
What is a Computer Program?
• To exactly know, what is data structure? We must know:
• What is a computer program?
Some mysterious
processing Output
Input
4 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
What a Program consists of??
Program = Algorithm + Data
Algorithm is a set of
??????????
instruction written to carry
out certain tasks
Find the requirements and suggest data type.
To store marks => ?????
To store names => ?????
To store names, marks, address, [Link] => ?????
5 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
What a Program consists of??
Program = Algorithm + Data Structures
Algorithm is a set of
Data structures is a way to
instruction written to carry
store and organise data
out certain tasks
in a computer, so that it can
be used efficiently.
6 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Structure……
▪ Defines how the object or thing is kept and organized
▪ Which structure is better for keeping books?
vertical Horizonal storing
7 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Introduction to Data Structure
▪ We have seen the structure, defines the way object/thing/data:
▪ stored
▪ organised
▪ Data structures: Data structures is a systematic way of organizing and storing
data in a computer, so that it can be accessed and modified efficiently.
▪ Instead of storing data randomly, data structures arrange data logically to
▪ Selecting proper structure, makes data to be used and processed efficiently
▪ Also the choice of data structure is application specific
8 Concept of ADT
Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear,
Why Data Structure are important?
DS are important because they directly effect the efficiency of the program.
▪ It improves performance
▪ Reduce processing time
▪ Simplify program logic
▪ Efficient memory usage
▪ Helps in problem solving
▪ It is essential for algorithm
Choosing the wrong data structure can make a program slow and inefficient.
9
Classification of Data Structure
Data
Structures
Non-
Primitive
Primitive
Fundamental
Linear Non-Linear
Datatypes
Array Linked List Stack Queue Trees Graphs
10 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Classification of Data Structure
▪ Depending on the way, the elements in data structures mentioned previously can
be classified into :
▪ Primitive Data Structures : It is basic data type that stored the simple
values. It is a datatype supported by programming language.
e.g. int , float , character, Boolean, etc
These data types occupied fixed memory and are directly supported by
programming language.
▪ Non-primitive Data Structures: It stored multiple values and derived from
the data types. These can be further classified as:
▪ Linear:
▪ Non-linear :
11 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Classification of Data Structure
▪ Linear: Elements of the data structure forms linear relationship or sequential
order.
▪ Non-linear : Elements of this data structure are stored/accessed in a non-
linear order
12 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Classification of Data Structure
• Linear data structure –
- Element are arranged sequentially.
- Traversal is straight forward.
- Single level.
- e.g. array, linked list, stack, queue.
• Non-Linear data structure –
- Element are arranged hierarchically.
- Traversal is complex.
- Multiple level.
- e. g. Tree, Graph.
13 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Classification of Data Structure
▪ Depending on memory allocated, data structures mentioned previously
can be classified into :
▪ Static Data Structures : memory is allocated at compile time
(fixed size) - array
▪ Dynamic Data Structures: memory is allocated at execution time
(size can be changed) - linked list
14 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Data Abstraction
ADT : Abstract Data Type
Let’s break ADT:
▪ Data type:
▪ A data type represents a set of possible values
▪ such as {..., -2, -1, 0, 1, 2, ...}, or {true, false}
▪ are categorization of data in every programming language
▪ Examples: integer, float, character etc.
▪ Abstract (Abstraction) : The process of providing only essentials and hiding the
details is known as abstraction.
15 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Concept of ADT
• Abstract:
• To abstract is to leave out information, keeping (hopefully) the more
important parts
• Why Abstract?
• e.g. C language pre-defined functions
• An Abstract Data Type (ADT) is:
• a set of values
• a set of operations, which can be applied uniformly to all these values
16 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Concept of ADT
▪ ADT enables us to specify the general operations w.r.t to data structures, we
use as per application requirements.
▪ In short enable us to emphasize what need to be done, rather than how it
needs to be done.
So now lets move to type of data structures, then we see
how ADT helps us define operation with out bothering about
type of data we store.
17 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Concept of ADT
Example:
Seat Reservation System
Data
• Number of seats
• Seats reserved
• Seats available
Set of operations
• Book a seat
• Cancel a seat
• Find available seat
18 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Concept of ADT
Example:
Library Management System
Data
• Number of books
• Book title, author, year....
• Book is available
• Issue date and return date.....
Set of operations
• Issue a book
• Return a book
• Pay fine
• Add a new book
• Remove any book........
19 Lecture 1– Introduction, Types of Data Structures – Linear and Nonlinear, Concept of ADT
Operations on Data Structures
Operation on Data Structures
▪ Operation below can be performed on various data structures shown previously.
▪ Insert : Add the data item.
▪ Delete : Remove the data item
▪ Search: locate a particular item, from given set of data
▪ Sort : Sort the data on the given parameter
▪ Merge : combine the data from different source/set.
▪ If you see, all these above operations are probably in most of applications we are
using in day to day life for managing our information/data.
21 Lecture 2 – Operations on Data Structures, Arrays
Thank You