Data Structures-

Introduction

Dr. Kumkum Saxena

Dr. Kumkum Saxena Data Structures-Introduction page 2
Dr. Kumkum Saxena Data Structures-Introduction page 3
Dr. Kumkum Saxena Data Structures-Introduction page 4
Dr. Kumkum Saxena Data Structures-Introduction page 5
Dr. Kumkum Saxena Data Structures-Introduction page 6
 Agenda
◼ What data structures are and why we study
them.
◼ How C language constructs support
implementing efficient data structures.
◼ Quick review of C Programming basics
◼ Functions in C
◼ Recursion
◼ Arrays-Organization in C

Dr. Kumkum Saxena Data Structures-Introduction page 7

 Agenda
◼ Pointers-Memory & Reference
◼ Structures in C
◼ Structures
◼ Structure with Pointer
◼ Abstract Data Type(ADT)
◼ ADT vs Data Structure

Dr. Kumkum Saxena Data Structures-Introduction page 8

 What data structures are and
why we study them
◼ Organize data efficiently
◼ Improve program performance
◼ Reduce time and memory usage

Essential for:
▪ Databases
▪ Operating Systems
▪ AI & ML
▪ Competitive programming

Dr. Kumkum Saxena Data Structures-Introduction page 9

 How C language constructs support
implementing efficient DS

◼ C provides low-level control, minimal

abstraction, and direct memory access,
which together make data structures fast,
compact, and predictable.

Dr. Kumkum Saxena Data Structures-Introduction page 10

 Quick Review of C Programming
Basics
Basic constructs used in Data Structures:

 Variables and data types

 Conditional statements (if, switch)

 Loops (for, while)

 Functions

 Arrays & pointers

Reminder:

“Data Structures is NOT a new language—it’s better use of C.”

Dr. Kumkum Saxena Data Structures-Introduction page 11

 Functions in C

What is a Function?

int add(int a, int b) { A block of code that performs a specific task

return a + b;
} Improves:

● Code reusability
● Readability
● Modularity

return_type function_name(parameters)
{
// body
}

12
Dr. Kumkum Saxena Data Structures-Introduction page 12
 Function Call Flow

● Main function calls other functions

● Control moves to function

● Returns back to caller

main() → add() → return value → main()

13
Dr. Kumkum Saxena Data Structures-Introduction page 13
 Concept of Recursion

A function calling itself is called

recursion.
Recursion is used in:

Two mandatory parts:

● Tree traversal
● Graph algorithms
● Divide and conquer techniques ● Base condition
● Recursive call
Without base condition → infinite
recursion
Example:

int fact(int n) {
if(n == 0)
return 1;
return n * fact(n-1);
}

14
Dr. Kumkum Saxena Data Structures-Introduction page 14
 Arrays — Organization in C

● Collection of similar data elements

● Stored in contiguous memory locations

● Syntax:
int arr[5] = {10, 20, 30, 40, 50};

● Memory Representation:
● Index: 0 1 2 3 4
● Value:10 20 30 40 50
● Basis for:
● Stacks
● Queues
● Matrices
● Fast access using index
● Fixed size limitation
15
Dr. Kumkum Saxena Data Structures-Introduction page 15
 Pointers

Pointer stores address of a variable

Example:
int a = 10;
int *p = &a;

a → value
&a → address
p → stores address
*p → value at address

16
Dr. Kumkum Saxena Data Structures-Introduction page 16
 Structures

User-defined data type

Groups different data types
Example:
struct Student {
int roll;
char name[20];
float marks;
};

Access:
struct Student s1;
[Link] = 1;

17
Dr. Kumkum Saxena Data Structures-Introduction page 17
 What is a Data Structure? Need for Data Structures

A data structure is a way of organizing, storing, and accessing data efficiently.

Example:
● Array of marks
● Linked list of students
● Tree of files

Need for Data Structures:

● Handling large data
● Efficient searching
● Faster processing
● Optimal memory usage

18
Dr. Kumkum Saxena Data Structures-Introduction page 18
 Abstract Data Type (ADT)

ADT focuses on:

● What operations are allowed
● Not how those operations are implemented
● Example: Stack ADT - Operations:
push() – insert element
pop() – remove element
peek() – view top element

Implementation may be:

● Using array
● Using linked list

19
Dr. Kumkum Saxena Data Structures-Introduction page 19
 Abstract Data Type (ADT)

ADT Data Structure

Logical or abstract view Physical or implementation

view

Defines what operations are Defines how operations are

possible performed

Independent of programming Language-dependent

language

Example: Stack, Queue Example: Array, Linked List

20
Dr. Kumkum Saxena Data Structures-Introduction page 20
 List ADT
The List ADT (Abstract Data Type) is a sequential collection of elements that supports a set of
operations without specifying the internal implementation. It provides an ordered way to store, access,
and modify data.
Operations:
The List ADT need to store the required data in the sequence and should have the
following operations:
● get(): Return an element from the list at any given position.
● insert(): Insert an element at any position in the list.
● remove(): Remove the first occurrence of any element from a non-empty list.
● removeAt(): Remove the element at a specified location from a non-empty list.
● replace(): Replace an element at any position with another element.
● size(): Return the number of elements in the list.
● isEmpty(): Return true if the list is empty; otherwise, return false.
● isFull(): Return true if the list is full, otherwise, return false. Only applicable in fixed-size
implementations (e.g., array-based lists)

21
Dr. Kumkum Saxena Data Structures-Introduction page 21
 Stack ADT

The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out) principle. It
allows elements to be added and removed only from one end, called the top of the stack.
Operations:
In Stack ADT, the order of insertion and deletion should be according to the FILO or LIFO
Principle. Elements are inserted and removed from the same end, called the top of the stack. It
should also support the following operations:
● push(): Insert an element at one end of the stack called the top.
● pop(): Remove and return the element at the top of the stack, if it is not empty.
● peek(): Return the element at the top of the stack without removing it, if the stack is not
empty.
● size(): Return the number of elements in the stack.
● isEmpty(): Return true if the stack is empty; otherwise, return false.
● isFull(): Return true if the stack is full; otherwise, return false. Only relevant for fixed-
capacity stacks (e.g., array-based).

22
Dr. Kumkum Saxena Data Structures-Introduction page 22
 Queue ADT

The Queue ADT is a linear data structure that follows the FIFO (First In, First Out)
principle. It allows elements to be inserted at one end (rear) and removed from the other
end (front).
Operations:
The Queue ADT follows a design similar to the Stack ADT, but the order of insertion and
deletion changes to FIFO. Elements are inserted at one end (called the rear) and
removed from the other end (called the front). It should support the following operations:
● enqueue(): Insert an element at the end of the queue.
● dequeue(): Remove and return the first element of the queue, if the queue is not
empty.
● peek(): Return the element of the queue without removing it, if the queue is not
empty.
● size(): Return the number of elements in the queue.
● isEmpty(): Return true if the queue is empty; otherwise, return false.

23
Dr. Kumkum Saxena Data Structures-Introduction page 23
 Difference Between ADT and Data Structure

Key Understanding: ADT Data Structure

● ADT = Concept Logical or abstract view Physical or

● Data Structure = implementation view
Implementation
Defines what operations Defines how operations
are possible are performed
“ADT is like a car’s
functionality; data structure is Independent of Language-dependent
the engine design.” programming language

Example: Stack, Queue Example: Array, Linked

List

24
Dr. Kumkum Saxena Data Structures-Introduction page 24
 Types of Data Structures

Linear Data Non- Linear Data

Structures Structures
Array Tree
Stack Graph
Queue
Linked List

Static Data Dynamic Data

Structures Structures
Array Linked List

This classification is based on: ● Arrangement of data

● Memory allocation
● Relationship among elements

25
Dr. Kumkum Saxena Data Structures-Introduction page 25
 Linear Data Structures

● A linear data structure stores data in a straight line.

● Each data element is connected to the next one.
● The elements are stored in a fixed order.
● Data is saved in continuous (one after another) memory locations.
● The memory size is decided in advance.
● Some memory may be wasted if all space is not used.
● Data elements are accessed one by one.
● To reach an element, we usually start from the beginning.
● Only one element can be accessed directly at a time.

26
Dr. Kumkum Saxena Data Structures-Introduction page 26
 Linear Data Structure – Real-Life Example

Example: Queue at a Ticket Counter

● Imagine people standing in a queue at a ticket counter.
● People stand one after another in a straight line.
● Each person knows who is in front and who is behind them.
● The first person in the line is served first (First Come, First Served).
● You cannot jump directly to the middle person without passing others.
● To reach someone at the end, you must move step by step from the front.
● If space is reserved for 10 people but only 6 are present, space is wasted.

27
Dr. Kumkum Saxena Data Structures-Introduction page 27
 Non-linear Data Structure

● Non-linear data structures do not arrange data consecutively.

● Data elements are arranged in a sorted or hierarchical manner, not in sequence.
● A data element can be connected to more than one element.
● They exhibit a hierarchical relationship involving:
○ Parent
○ Child
○ Grandparent
● Traversal of elements is not sequential.
● Insertion and deletion operations are not performed in a linear order.
● Non-linear data structures utilize memory efficiently.
● They do not require memory allocation in advance.
● Common examples of non-linear data structures include:
○ Tree
○ Graph

28
Dr. Kumkum Saxena Data Structures-Introduction page 28
 Non - Linear Data Structure – Real-Life Examples

Road Map / Google Maps Family Tree (Tree Data Structure)

(Graph Data Structure) ● One parent can have multiple
● Locations (nodes) are children.
connected by roads (edges). ● Each child may further have their
● A place can connect to many own children (grandchildren).
places at once. ● Data is not arranged in a single
● Multiple paths exist to reach line.
a destination. ● Relationships are hierarchical, not
● Traversal is non-linear. sequential.
● You cannot traverse the family
members in one straight order like
a queue.
● Just like in a tree data structure,
information flows from root →
branches → leaves.

29
Dr. Kumkum Saxena Data Structures-Introduction page 29
 Static and Dynamic Data Structures

● Static data structures are those which do not change in

size while the program is running. Most arrays are
static, once you declare them, they cannot change in
size.

● Dynamic data structures can increase and decrease in

size while the program is running.

30
Dr. Kumkum Saxena Data Structures-Introduction page 30
 31
Dr. Kumkum Saxena Data Structures-Introduction page 31
 A static data structure (like an array) can hold a dynamic structure. The static structure must be
big enough.

Stacks
● A stack is a last in first out (LIFO or FILO) data structure. The head pointer will point to the
most recent item of data which will be at the top. There are only two operations that can be
applied, inserting and deleting/reading.
Inserting Data into a Stack
● First check that the stack is not full. If it is stop, and return an error.
● Next, increment the stack pointer, so it will now be pointing to the next empty data location.
● Finally insert the data into the location pointed to by the stack pointer.
Deleting and Reading from a Stack
● Check to see if the stack is empty. If it is stop and return an error.
● Copy the data item in the cell pointed to be the stack pointer.
● Decrement the stack pointer and stop.

32
Dr. Kumkum Saxena Data Structures-Introduction page 32
 Operations on Data Structures

1. TraversalVisiting each element exactly once

2. InsertionAdding a new element at a specific
position
3. DeletionRemoving an existing element
4. SearchingFinding the location of an element
5. SortingArranging data in ascending or
descending order
6. MergingCombining two data structures

33
Dr. Kumkum Saxena Data Structures-Introduction page 33
 Possible Questions…
Define Data Structure.

What is a function?

Define recursion.

What is an array?

Define pointer.

What is a structure?

What is ADT?

Define linear data structure.

Dr. Kumkum Saxena Data Structures-Introduction page 34

 Possible Questions…
Explain functions in C with an example.

Explain recursion and its importance in data structures.

Explain arrays and their memory representation.

What is pointer? Explain with a diagram.

Explain structure with example.

Explain Abstract Data Type with suitable example.

Differentiate between ADT and Data Structure.

Explain linear and non-linear data structures.

Dr. Kumkum Saxena Data Structures-Introduction page 35
 Possible Questions…

Explain C programming constructs required for Data Structures.

Explain types of data structures with examples.

Explain operations performed on data structures.

Map real-life applications to different data structures and justify.

Dr. Kumkum Saxena Data Structures-Introduction page 36

 Lab Assignment 1
//Function to insert an element at a specific position
void insert(int arr[], int *n, int pos, int value)
{
if (*n >= MAX)
{
printf("Array is full. Cannot insert.");
return;
}
if (pos < 1 || pos > *n + 1)
{ // Check position validity
printf("Invalid position! Must be between 1 and %d.", *n + 1);
return;
}
// Shift elements to the right
for (int i = *n; i >= pos - 1; i--)
{
arr[i + 1] = arr[i];
}
arr[pos - 1] = value; // Insert the new element
(*n)++; // Increment the size of the array
}
Dr. Kumkum Saxena Data Structures-Introduction page 37
 #include <stdio.h> int main()
{
void insert(int arr[], int *n, int pos, int int arr[7] = {10, 20, 30, 40, 50};
val) {
int n = 5;
// Shift elements to the right int pos = 3;
for (int i = *n; i > pos; i--) int val = 25;
arr[i] = arr[i - 1];
// Insert the value at the specified
// Insert val at the specified position position
arr[pos] = val; insert(arr, &n, pos, val);

// Increase the current size

for (int i = 0; i < n; i++)
(*n)++;
printf("%d ", arr[i]);
}
return 0;
}
Dr. Kumkum Saxena Data Structures-Introduction page 38
 // Function to delete an element from a specific position
void delete(int arr[], int *n, int pos)
{
if (*n == 0)
{
printf("Array is empty. Cannot delete.");
return;
}
if (pos < 1 || pos > *n)
{ // Check position validity
printf("Invalid position! Must be between 1 and %d.", *n);
return;
}
// Shift elements to the left
for (int i = pos - 1; i < *n - 1; i++)
{
arr[i] = arr[i + 1];
}
(*n)--; // Decrement the size of the array
}
Dr. Kumkum Saxena Data Structures-Introduction page 39