Introduction to Data Structures

Presented By
[Link]
Asst Prof/IT Dept
 What is Data Structure?

Data structures are a specific way of

organizing data in a specialized format on a
computer so that the information can be
organized, processed, stored, and retrieved
quickly and effectively.
 Linear Data Structure
Linear data structures are structures where data elements are
arranged sequentially, one after another.

Examples: Array, Linked List, Stack, Queue

 Array
Stores elements in contiguous memory locations

Fixed size

Fast access using index

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

 Types of array
One Dimensional Array Two Dimensional Array Multi dimensional Array
data_type data_type array_name[rows] data_type array_name[size1]
array_name[size]; [columns]; [size2][size3];

int arr[5]; int arr[3][4]; int arr[2][3][4];

int arr[5] = {1, 2, 3, 4, 5}; int arr[2][3] = { int arr[2][2][2] = {

{1, 2, 3}, {
{4, 5, 6} {1, 2},
}; {3, 4}
},
{
{5, 6},
{7, 8}
}
};
printf("%d", arr[2]); printf("%d", arr[2][2]); printf("%d", arr[1][0][0]);
// Accesses the third //Access 2nd row 2nd column //print 5
element, which is 3 element which is 6
 Example: Accessing Array Elements
Program:
#include <stdio.h>
int main() {
Array element can be accessed by
int arr[] = {2, 4, 8, 12, 16, 18}; index value
int n = sizeof(arr)/sizeof(arr[0]);
// Printing array elements
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Output:
2 4 8 12 16 18
Advantages and Disadvantages
of Array
Advantages
Fast access (O(1))

Disadvantages
Size cannot change

Insertion/deletion is costly
 Linked List
 A linked list is a linear data structure which can store a collection of "nodes" connected

together via links i.e. pointers.

 Linked lists nodes are not stored at a contiguous location, rather they are linked using

pointers to the different memory locations.

 A node consists of the data value and a pointer to the address of the next node within

the linked list.

 A linked list is a dynamic linear data structure whose memory size can be allocated or

de-allocated at run time based on the operation insertion or deletion, this helps in using

system memory efficiently.

 Linked List
Example:

Node Declaration:
struct node
{
int data;
struct node *next;
};
 Comparison of Linked List and
Arrays

Linked List:
 Data Structure: Non-contiguous
 Memory Allocation: Typically allocated one by one to individual elements
 Insertion/Deletion: Efficient
 Access: Sequential
Array:
 Data Structure: Contiguous
 Memory Allocation: Typically allocated to the whole array
 Insertion/Deletion: Inefficient
 Access: Random
Creation of simple Linked List

we have created a simple linked list

with three nodes
Types of Linked List

It is the most common. Each node has

data and a pointer to the next node.

We add a pointer to the previous node in

a doubly-linked list. Thus, we can go in
either direction: forward or backward.

A circular linked list is a variation of a

linked list in which the last element is
linked to the first element. This forms a
circular loop.
 Advantages of Linked List
 Dynamic data structure: it can grow and shrink at runtime by allocating and deallocating memory.

 No memory wastage: the size of the linked list increase or decrease at run time so there is no memory

wastage and there is no need to pre-allocate the memory.

 Implementation: Linear data structures like stacks and queues are often easily implemented using a linked

list.

 Insertion and Deletion Operations: Insertion and deletion operations are quite easier and no need to shift

elements after the insertion or deletion .

 Flexible: This is because the elements in Linked List are not stored in contiguous memory locations unlike

the array.

 Efficient for large data: When working with large datasets linked lists play a crucial role as it can grow and

shrink dynamically.

 Scalability: Contains the ability to add or remove elements at any position.

 Disadvantages of Linked List
• Memory usage: More memory is required in the linked list as compared to an array.

Because in a linked list, a pointer is also required to store the address of the next

element and it requires extra memory for itself.

• Traversal: In a Linked list traversal is more time-consuming as compared to an array.

Direct access to an element is not possible in a linked list as in an array by index. For

example, for accessing a node at position n, one has to traverse all the nodes before it.

• Random Access: Random access is not possible in a linked list due to its

dynamic memory allocation.

• Lower efficiency at times: For certain operations, such as searching for an element

or iterating through the list, can be slower in a linked list.

 Stack
• It is an ordered group of homogeneous items of
elements.
• Elements are added to and removed from the top of the
stack (the most recently added items are at the top of
the stack).
• The last element to be added is the first to be removed
(LIFO: Last In, First Out).
 Stack
A stack is a linear data structure which satisfies the
following properties at any time:
• Allocations and de-allocations are performed in a last-in-first-
out (LIFO) manner i.e. amongst all existing entries at any time,
the last entry to have been allocated is the first entry to be
de-allocated
• only the last entry is accessible
 Operations performed on Stack

push(): It inserts an element to the top of the stack. It

takes O(1) time, as each node is inserted at the head/top of the
linked list.
pop(): It removes an element from the top of the stack. It
takes O(1) time, as the top always points to the newly inserted
node.
peek(): It returns the top element of the stack.
size(): It returns the size of the stack, i.e., the total number of
items in a stack.
isEmpty(): Returns a boolean value. It returns true if the stack is
empty. Else, it returns false.
 REPRESENTATION OF STACK

Stack can be represented in computer in the following

two ways: –

 Array Representation

 Linked Representation
REPRESENTATION OF STACK
REPRESENTATION OF STACK
 Application of Stack
 Function Calls (Call Stack):

 Expression Evaluation and Conversion:

 Parentheses/Bracket Balancing:

 Memory Management:

In Real-World Software Applications

 "Undo" and "Redo" Features: Most applications, such as text editors and design software, use

stacks to implement the undo (Ctrl+Z) and redo functionality. Each action is pushed onto a

stack, and pressing "undo" pops the last action, restoring the previous state.

 Web Browser History: Browsers use a stack to store the history of visited web pages. Clicking

the "back" button pops the current page's URL from the stack and loads the previous one.
 Queue
• A queue in data structures is a linear collection of
elements that operates under the First In, First Out
(FIFO) principle. This means that the first element
added to the queue will be the first one removed.
 Operation on Queue
 Enqueue
The enqueue operation involves adding an element to the rear of the queue
 Dequeue
The dequeue operation removes an element from the front of the queue.
 Peek or Front
This operation allows you to look at the front element of the queue without
removing it
 IsEmpty
The isEmpty operation checks if the queue is empty.
 IsFull (for fixed-size queues)
This operation checks if the queue has reached its maximum capacity.
Operation on Queue
 Applications of Queue

 Operating Systems: Queues are used to manage processes in multitasking environments.

 Printing and Task SchedulingJobs are processed in the order they are received unless priorities are

assigned.

 Web Server Request Management: Web servers use queues to manage incoming client requests.

Requests are stored in a queue and processed sequentially, ensuring that resources are allocated fairly

and efficiently.

 Call Centers: In customer service call centers, incoming calls are held in a queue until an operator is

available, ensuring that calls are answered in the order they arrive.

 Banking Services: Banks use queues to manage customer transactions at branches, where customers

take a number and wait to be served in order.

 Healthcare Systems: In hospitals and clinics, queues are used to manage patient appointments and

treatments in an orderly system.

 Non Linear Data Structure

Data structures where data elements are not arranged

sequentially or linearly are called non-linear data
structures.
In a non-linear data structure, data elements are attached in
hierarchically manner.
multiple levels are involved.

Example: Tree and Graph

 Tree Data Structure
A tree is a hierarchical data structure used to organize
and represent data in a parent–child relationship.
It consists of nodes, where the topmost node is called
the root, and every other node can have one or more
child nodes.
Basic Terminologies In Tree Data
Structure:
 Parent Node: A node that is an immediate predecessor of another node.
Example: 35 is the parent of 3 and 6.
 Child Node: A node that is an immediate successor of another node.
Example: 3 and 6 are children of 35.
 Root Node: The topmost node in a tree, which does not have a parent.
Example: 15 is the root node.
 Leaf Node (External Node): Nodes that do not have any children.
Example: 1, 10, 12, 5, 7, 7 are leaf nodes.
 Sibling: Nodes that share the same parent.
Example: 1 and 10 are siblings, and 5 and 7 are siblings.
 Level of a Node: The number of edges in the path from the root to that
[Link] root node is at level 0.
 Internal Node: A node with at least one child.
 Types of Tree
Binary Tree : Every node has at most two children
Ternary Tree : Every node has at most three children
N-ary Tree : Every node has at most n children.
 Binary Tree

A particular type of tree where every node can have at

most 2 children, left and right.
 Types of Binary Tree
 Full Binary Tree:
Every node has either 0 or 2 children
No node has only one child

• Complete Binary Tree:

All levels are completely filled except
possibly the last level The last level is
filled from left to right
Example: Binary Heaps (Min Heap,
Max Heap)

• Perfect Binary Tree:

A special case of a complete tree.
All internal nodes have 2 children.
All leaf nodes are at the same level.
 Representation of binary tree

A binary tree in a data structure can be represented in

two primary ways:
• array representation (using a sequential array)

• linked-node representation (using pointers)

 Array Representation of Binary
Tree
• In array representation of a binary tree, we use one-
dimensional array (1-D Array) to represent a binary tree.
The tree is stored in an array.
For any node at index i:
Left Child: Located at 2 * i +
1
Right Child: Located at 2 * i
+2
Root Node: Stored at index 0
 Linked List Representation of
Binary Tree
• We use a double linked list to represent a binary tree. In
a double linked list, every node consists of three fields.

• First field for storing left child address, second for

storing actual data and third for storing right child
address.
Linked List Representation of
Binary Tree
 Special Types of Trees

On the basis of node values, the Binary Tree can be

classified into the following special types:
 Binary Search Tree
 AVL Tree
 Red Black Tree
 B Tree
 B+ Tree
 Special Types of Trees
Tree Properties Example
 The left subtree of a node contains
only nodes with keys lesser than the
node’s key.
Binary Search  The right subtree of a node contains
Tree only nodes with keys greater than the
node’s key.
 The left and right subtree must also
be a binary search tree.

 AVL tree is a self-balancing Binary

Search Tree (BST) where the
difference between heights of left
AVL Tree and right subtrees of all nodes is at
most 1.
 Special Types of Trees
Tree Properties Example
 A Red-Black Tree is a self-balancing
binary search tree
 Each node has an additional attribute: a color,
which can be either red or black.
 The colors are used to maintain balance during
insertions and deletions, ensuring efficient data
retrieval and manipulation.
Properties of Red-Black Trees
A Red-Black Tree have the following properties:
Red Black Node Color: Each node is either red or black.
Tree Root Property: The root of the tree is
always black.
Red Property: Red nodes cannot have red
children (no two consecutive red nodes on any
path).
Black Property: Every path from a node to its
descendant null nodes (leaves) has the same
number of black nodes.
Leaf Property: All leaves (NIL nodes) are black.
 Special Types of Trees
Tree Properties

B-Tree is a self-balanced search tree in which every node contains

multiple keys and has more than two children.
B-Tree of Order m has the following properties...
 All leaf nodes must be at same level.
 All nodes except root must have at least [m/2]-1 keys and maximum of m-
1 keys.
B Tree  All non leaf nodes except root (i.e. all internal nodes) must have at
least m/2 children.
 If the root node is a non leaf node, then it must have atleast 2 children.
 If the root node is a non leaf node, then it must have atleast 2 children.
[Link]
 All the key values in a node must be in Ascending Order.
 Special Types of Trees
Tree Properties
Example:

B Tree
 Special Types of Trees
Tree Properties

A B+ Tree is an advanced data structure used in database systems and file

systems to maintain sorted data for fast retrieval, especially from disk. It is an
extended version of the B Tree, where all actual data is stored only in the leaf
B+ nodes, while internal nodes contain only keys for navigation.
Tree  Leaf nodes store all the key values and pointers to the actual data.
 Internal nodes store only the keys that guide searches.
 All leaf nodes are linked together, supporting efficient sequential and range
queries.
Demo Link

[Link]
 Special Types of Trees
Tree Properties
Example:

B+
Tree
 Graph
• A graph is an abstract data type (ADT) which consists of a
set of objects that are connected to each other via links. The
interconnected objects are represented by points termed
as vertices, and the links that connect the vertices are
called edges.

• Formally, a graph is a pair of sets (V, E), where V is the set

of vertices and E is the set of edges, connecting the pairs of
vertices.
 Graph

Example

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
 Types of Graph
Graphs can be categorized based on their characteristics
and properties
Type of Properties Example
Graph
Directed In a directed graph, edges have a Think of a Twitter network where
Graph direction, meaning they go from one person follows another. If
one node to another in a specific Alice follows Bob, there is an
way. edge from Alice to Bob but not
necessarily from Bob to Alice.
Alice Bob

Undirected In an undirected graph, edges do Think of a Facebook friendship

Graph not have a direction. They simply where if Alice is friends with Bob,
connect two nodes without any then Bob is also friends with
particular order. Alice. The edge goes both ways.
 Types of Graph
Types of Graph Properties Example
Weighted Graph In a weighted graph, edges A road map where the
have weights or costs weights on the edges
associated with them. represent the distance
These weights can between cities.
represent distances, costs,
or any other metric.

Unweighted Graph In an unweighted graph, A simple social network

all edges have the same where each friendship has
weight, typically the same importance.
considered as 1.
 Representation of Graph

Graphs are commonly represented in two ways:

1. Adjacency Matrix

2. Adjacency List

Adjacency Matrix

• An adjacency matrix is a 2D array of V x V vertices. Each row and

column represent a vertex.

• If the value of any element a[i][j] is 1, it represents that there is an

edge connecting vertex i and vertex j.
Representation of Graph
 Representation of Graph
Adjacency List
• An adjacency list represents a graph as an array of
linked lists.
• The index of the array represents a vertex and each
element in its linked list represents the other vertices
that form an edge with the vertex.
 Graph Operations

Check if the element is present in the graph

Graph Traversal

Add elements(vertex, edges) to graph

Finding the path from one vertex to another

 Applications of Graph
 Google maps uses graphs for building transportation systems, where intersection of two(or more)

roads are considered to be a vertex and the road connecting two vertices is considered to be an edge,

thus their navigation system is based on the algorithm to calculate the shortest path between two

vertices.

 In Facebook, users are considered to be the vertices and if they are friends then there is an edge

running between them. Facebook's Friend suggestion algorithm uses graph theory.

 In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to

other page v if there is a link of page v on page u.

 In the Dijkstra algorithm, we use a graph. we find the smallest path between two or many nodes.

 Network monitoring: Graphs can be used to monitor network traffic in real-time, allowing network

administrators to identify potential bottlenecks, security threats, and other issues. This is critical for

ensuring the smooth operation of complex networks.