Data Structure

(PCC2011)
Module 1
INTRODUCTION
Prof. Rahulkumar P. Tivarekar
 Definition
• A data structure is a way of organizing, storing, and managing data in a
computer so that it can be accessed, modified, and processed efficiently.
• It defines not only how data is stored, but also the operations that can be
performed on it, such as insertion, deletion, searching, and sorting.
• Mathematical and logical model of organizing the interrelated data.

Pre-defined structure to Logical operations on

organize data e.g. data like push pop sort
sequential, ordered, linear
etc.
 Introduction

• An algorithm is a set of instruction written to carry out certain tasks & the
data structure is the way of organizing the data with their logical
relationship retained.
• Program=algorithm + Data Structure
• Select a Data Structure that can solve a problem optimally. i.e. less time,
less space, less complexity.
Data Structures : Arrays
• An array is defined as a set of finite number of homogeneous elements or same
data items.
• It means an array can contain one type of data only, either all integer, all float-
point number or all character.
• e.g. int arr[10]

• Where int specifies the data type or type of elements that arrays store.

• “arr” is the name of array & the number specified inside the square brackets is the
number of elements an array can store, this is also called size or length of array.
• The elements of array will always be stored in the consecutive (continues)
memory location.
Arrays
• For the following array 2 is the lower bound of array and 6
is the upper bound of array.
• Therefore,
Size of array = (Upper Bound- Lower Bound)+1
=(6-2)+1= 5

• Array can always be read or written through loop.

25 18 90 12 6
Index → 2 3 4 5 6
Arrays
• If we are reading or writing two-dimensional array it
would require two loops. And similarly the array of a N
dimension would required N loops.
• Some common operation performed on array are:
✓ Creation of an array
✓ Traversing an array
✓ Insertion of new element
✓ Deletion of required element
✓ Modification of an element
✓ Merging of arrays
Arrays
int arr[10]

• For reading (input) an array

for(i=0; i<=9; i++)
scanf(“%d”, &arr[i]);
• For writing an array (by traversing)
For(i=0; i<=9; i++)
printf(“%d”, arr[i]);
• Location of element(A[i]) = Base address+ (Size of every
element)*Relative index of A[i]
Location (address) of the element in array

w = Size of every element

QUIZ ?
Classification of Data Structure
Data structure

Primitive DS
Non-Primitive DS
Integer Float Character Pointer
Linear Non-Linear

Array Queue Graph Trees Hash Table

Link List Stack

Primitive Data Structure
• These are basic structures and directly operated upon by the machine
instructions.
Non-Primitive Data Structure
• These are more sophisticated data structures derived from the
primitive data structures.
• The non-primitive data structures emphasize on structuring of a group
of homogeneous (same type) or heterogeneous (different type) data
items.
Linear Data Structure

• In linear data structures, elements are arranged sequentially one

after another. Each element has a unique predecessor and successor
(except the first and last).
• Characteristics:
o Sequential arrangement
o Easy traversal (one element after another)
o Simple implementation
o Used when data processing is in a sequence
• Examples: Array, Linked list, Stack, Queue
Non-Linear Data Structure

• In non-linear data structures, elements are not arranged sequentially.

One element can be connected to multiple elements.
• Characteristics:
o Hierarchical or network structure
o Efficient for complex relationships
o Faster searching in large datasets
o Used in AI, databases, networking, file systems
• Examples: Trees, Graphs, Heaps
Static Data Structures
• In static data structures, memory size is fixed before execution. It cannot
grow or shrink during runtime.
• Characteristics:
o Fixed memory allocation
o Faster access
o Less flexible
o Memory wastage possible
• Example:
• Arrays with fixed size such as, int A[10];
• If only 6 elements are used, 4 spaces are wasted.
Dynamic Data Structures
• In dynamic data structures, memory is allocated and deallocated during
runtime as needed.
• Characteristics:
o Flexible size
o Efficient memory utilization
o Slightly slower than static due to dynamic memory management
o More complex implementation
• Examples:
• Linked Lists, Trees, Graphs
• Dynamic arrays (like ArrayList in Java, vector in C++)
• Example: 10 → 20 → 30 → 40 (Nodes are created as required).
 Basis Type Examples
Linear Array, Stack, Queue, Linked List
Arrangement
Non-Linear Tree, Graph, Heap
Static Fixed-size Array
Memory
Dynamic Linked List, Tree
Operations on Data Structure
• The most commonly used operation on data structures are
broadly categorized into following types:
• Creating a DS
• Selecting a DS
• Traversing through a DS
• Insertion of element in DS
• Destroy or Delete element from DS
• Searching elements in DS
• Sorting elements of DS
• Merging
• Updating
• Accessing
 Operations on Data Structure continued…
1. Traversing: Visiting every element atleast and atmost once
2. Insertion: Adding an element in a data structure. Where to insert, how to
insert etc. depends on data structure.
✓ Overflow: Error, when trying to insert element in D.S. which is full
3. Deletion: Removing an element from a data structure
✓ Underflow: Error, when trying to delete an element from a D.S. which is
empty
4. Searching: Finding an element in a data structure.
✓ If search is successful, then outcome will be location/address of
element.
✓ If search is unsuccessful then outcome will be (lower bound-1) or NULL.
 Operations on Data Structure continued…
5. Sorting: Arranging the elements in ascending or descending order.
6. Merging: Combining two data structures of same type into one.
7. Updating: Modifying an existing element from a data structure.
8. Accessing: Retrieving an element from a data structure.
 Concept of ADT
• Data types such as int, float, double, long, etc. are considered to be in-
built data types and we can perform basic operations with them such as
addition, subtraction, division, multiplication, etc.
• Now there might be a situation when we need operations for our user-
defined data type that have to be defined.
• These operations can be defined only as and when we require them.
• So, in order to simplify the process of solving problems, we can create
data structures along with their operations, and such data structures
that are not built-in are known as Abstract Data Type (ADT).
 Concept of ADT continued…
• An Abstract Data Type (ADT) is a logical description of a data
structure that defines what operations can be performed on the data
and what those operations do, without specifying how they are
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. i.e. the process of providing only the essentials
and hiding the complex details is known as abstraction.
 Features of ADT
• Abstraction: The user does not need to know the actual
implementation of the data structure.
• Better Conceptualization: ADT gives us a better conceptualization of
the real world.
• Robust: The program is robust and has the ability to catch errors.