Module 1:
Introduction to Data Structures
● Introduction to Data Structures
● Types of Data Structures-Linear and
Nonlinear
● Operations on Data Structures.
● Concept of ADT
S. P. Bansu/DS/III/2022-23 2
Data Structures
Definition
● Data structure is representation of the logical
relationship existing between individual elements of
data.
● In other words, a data structure is a way of
organizing all data items that considers not only the
elements stored but also their relationship to each
S. P. Bansu/DS/III/2022-23 3
other
Data Structures
● Data Structure can be defined as the group of data
elements which provides an efficient way of storing and
organising data in the computer so that it can be used
efficiently.
● Data Structures helps the programmers to handle the
data in an efficient way S. P. Bansu/DS/III/2022-23 4
5
S. P. Bansu/DS/III/2022-23
Classification of Data Structure
Data structure are normally divided into two
broad categories:
1. Primitive Data Structure
2. Non-Primitive Data Structure
S. P. Bansu/DS/III/2022-23 6
Primitive Data Structures
● Primitive Data Structures are the basic data
structures that directly operate upon the machine
instructions. OR
● A primitive data structure is generally a basic
structure that is usually built into the language.
● For ex: int,float,char etc S. P. Bansu/DS/III/2022-23 7
S. P. Bansu/DS/III/2022-23 8
Non-primitive Data Structures
● Non-primitive data structures are more complicated data
structures and are derived from primitive data structures.
● They emphasize on grouping same or different data items
with relationship between each data item.
● For Ex: array, int a[10]
S. P. Bansu/DS/III/2022-23 9
Linear Data Structures
● Data elements arranged in sequential manner and
each member element is connected to its previous
and next element.
● Traverse a linear data structure in a single level and
in single run.
● For Ex: Link List, Queue, Stack, Array etc
S. P. Bansu/DS/III/2022-23 10
Non-linear Data Structures
● Data elements arranged in non sequential manner
and each element can have multiple paths to connect
to other elements.
● Such data structures supports multi-level storage and
often cannot be traversed in single run.
● For Ex: Tree, Graphs etc.
S. P. Bansu/DS/III/2022-23 11
Static Allocation:
● Allocation is done before program execution(at compile
time)
● Fixed memory, waste memory
● Ex: Array
Dynamic Allocation
● Allocation is done during program execution(at run time)
● Memory can be changed.
S. P. Bansu/DS/III/2022-23 12
● Ex: Link List
S. P. Bansu/DS/III/2022-23 13
Stack
● A stack is also an ordered collection of elements like
arrays, but it has a special feature that deletion and
insertion of elements can be done only from one
end called the “top “of the stack (TOP)
● Due to this property it is also called as last in first
out type of data structure (LIFO).
S. P. Bansu/DS/III/2022-23 14
Queue
● Queue are first in first out type of data structure
(i.e. FIFO)
● In a queue new elements are added to the queue
from one end called REAR end and the element are
always removed from other end called the FRONT
end S. P. Bansu/DS/III/2022-23 15
Trees
● A tree can be defined as finite set of data items (nodes).
Tree is non-linear type of data structure which represents
the hierarchical relationship between various elements
● There is a special data item at the top of hierarchy called
the Root of the tree.
S. P. Bansu/DS/III/2022-23 16
Graph
● Graph is a mathematical non-linear data
structure capable of representing many kind
of physical structures.
● Definition: A graph G(V,E) is a set of vertices
V and a set of edges E.
S. P. Bansu/DS/III/2022-23 17
Operations on Non-Primitive Data Structures
The most commonly used operation on data structure are broadly categorized
into following types:
1. Create [Link]
3. Display [Link]
5. Updating [Link]
7. Sorting 8. Merging
9. Destroy or Delete
S. P. Bansu/DS/III/2022-23 18
Abstract Data Type (ADT): OPN
● ADT only mentions :
- what operations are to be performed
- but not how these operations will be
Implemented.
● For EX: Arithmetic Operation S. P. Bansu/DS/III/2022-23
19
University Questions
1. Explain Linear and non linear data structures with example?
….. 5 marks
2. Explain different types of Data Structures with example?
5Mks
3. What is data structures? List out the areas in which data
structures are extensively applied….5 Mks
4. Define ADT with an example. …. 5 Mks
5. Explain ADT. List Linear and Non Linear Data Structures with
S. P. Bansu/DS/III/2022-23
example…… 5 mks 20
