Tutorial - Data Structure

and Algorithm
Kibret Zewdu
Department of Computer Science
College of Informatics
University of Gondar
Arrays & Strings
• Stores data elements based on sequential, most commonly 0 based, index.
• Time Complexity
• Indexing: Linear array: O(1), Dynamic array: O(1)
• Search: Linear array: O(n), Dynamic array: O(n)
• Traverse: O(n)

May 9, 2025 Data Structure and Algorithm Tutorial 2

Linked Lists
• Stores data with nodes that point to other nodes
• Time Complexity
• Indexing: O(n)
• Search: O(n)
• Optimized Search: O(n)
• Append: O(1)
• Insertion: O(n)

May 9, 2025 Data Structure and Algorithm Tutorial 3

Queue
• Queues are everywhere in daily life.
• They follow the FIFO (First In, First Out) principle, where the first item added is the first to
be processed.
• Here are some real-world examples:
I. Waiting in Line – At a supermarket checkout or ticket counter, people stand in a queue, and the first
person in line gets served first.
II. Call Center System – When you call customer service, your request is placed in a queue, and agents
answer calls in the order they were received.
III. Printer Queue – When multiple documents are sent to a printer, they are processed one by one in the
order they were submitted.
IV. Task Scheduling in Computers – Operating systems manage processes using queues. The first task
submitted gets processed first.
V. Traffic Management – Vehicles in a toll booth or at a traffic signal follow a queue system—first car in
line moves first.
May 9, 2025 Data Structure and Algorithm Tutorial 4
Priority Queue
• A priority queue is a special type of queue in which each element is associated with
a priority value.
• Elements are served on the basis of their priority. That is, higher priority elements are
served first.
• However, if elements with the same priority occur, they are served according to their
order in the queue.
• Basic operations of a priority queue are inserting, removing, and peeking elements.

May 9, 2025 Data Structure and Algorithm Tutorial 5

Implementation of Priority Queue
• Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary
search tree.

• Among these data structures, heap data structure provides an efficient implementation of priority
queues.
• Heap data structure is a complete binary tree that satisfies the heap property, where any given
node is
• always greater than its child node/s and the key of the root node is the largest among all other
nodes. This property is also called max heap property.
• always smaller than the child node/s and the key of the root node is the smallest among all
other nodes. This property is also called min heap property.

May 9, 2025 Data Structure and Algorithm Tutorial 6

Analysis of the most common implementations of Priority Queues

Implementation Insertion Deletion Best Use Case

Linked List O(n) O(1) Small datasets

Binary Heap O(log n) O(log n) Large datasets, scheduling

BST O(log n) O(log n) Dynamic priority changes

Table __ : A comparative analysis of different implementations of priority queue

May 9, 2025 Data Structure and Algorithm Tutorial 7

Priority Queue Applications
• Dijkstra's algorithm

• for load balancing and interrupt handling in an operating system

• for data compression in Huffman code

May 9, 2025 Data Structure and Algorithm Tutorial 8

Tree
• Tree data structures are widely used in various applications due to their hierarchical
nature and efficient data organization.
• A tree data structure is a hierarchical structure that consists of nodes connected by edges.
• It has a root node and subtrees branching off from it.
• Trees are widely used in computer science for organizing and managing data efficiently.
• Some basic operations performed on tree data structures:
• Traversal,
• insertion, Deletion,
• Searching, Updating,
• Height Calculation,
• Finding Minimum and Maximum.

May 9, 2025 Data Structure and Algorithm Tutorial 9

Tree Applications
• Here are some key applications:
1. File Systems – Operating systems use tree structures to organize directories and
files, allowing efficient navigation and retrieval.
2. Database Indexing – Trees like B-trees and B+ trees help in indexing large datasets,
enabling fast search, insert, and delete operations.
3. Artificial Intelligence – Decision trees are used in AI algorithms for decision-
making processes, such as game trees in chess.
4. Network Routing – Routing algorithms use tree structures to optimize paths and
manage network traffic efficiently.
5. XML and HTML Parsing – Web browsers use tree structures to parse and render
HTML/XML documents.
6. Compiler Design – Abstract syntax trees (ASTs) help compilers analyze and
optimize code execution

May 9, 2025 Data Structure and Algorithm Tutorial 10

Graph
• A graph data structure is a collection of nodes (also called vertices) and edges that connect them.
• Graphs are used in various applications like
1. Social Networks – Platforms like Facebook and LinkedIn use graphs to model connections between
users.
2. Google Maps & GPS Navigation – Graphs help find the shortest path between locations using
algorithms like Dijkstra’s.
3. Web Crawling & Search Engines – Google’s search engine uses graphs to rank web pages based on their
connections.
4. Network Routing – Graphs optimize data transmission paths in computer networks.
5. Recommendation Systems – Platforms like Netflix and Amazon use graphs to suggest movies or
products based on user preferences.
6.MayArtificial
9, 2025 Intelligence & Machine Learning – Graph-based
Data Structure neural networks enhance AI applications.
and Algorithm Tutorial 11
Types of Graphs
1.Directed Graph (Digraph) – Edges have directions, meaning they go from one vertex
to another in a specific way.
2.Undirected Graph – Edges have no direction, meaning connections are
bidirectional.
3.Weighted Graph – Each edge has an associated numerical value (weight), used in
applications like shortest path algorithms.
4.Unweighted Graph – No weights are assigned to edges.
5.Cyclic Graph – Contains cycles, meaning there is a path that leads back to a
previously visited vertex.
6.Acyclic Graph – No cycles exist.
7.Connected Graph – All vertices are connected by some path.
8.Disconnected Graph – Some vertices are isolated and not connected.

May 9, 2025 Data Structure and Algorithm Tutorial 12

Graph: Basic Operations
• Traversal – Visiting each vertex using techniques like:
• Breadth-First Search (BFS) – explores nodes level by level and uses Queue
• Depth-First Search (DFS) – explores as far as possible along each branch before
backtracking - uses Stack
• Insertion – Adding new vertices and edges.
• Deletion – Removing vertices or edges.
• Path Finding – Finding shortest or optimal paths using algorithms like
Dijkstra’s and Floyd-Warshall.
• Cycle Detection – Determining whether a cycle exists in the graph

May 9, 2025 Data Structure and Algorithm Tutorial 13

DFS
• explores as far as possible along each branch before backtracking.
• Internally uses Stack
• DFS is useful for
• pathfinding,
• cycle detection, and
• topological sorting in graphs.

May 9, 2025 Data Structure and Algorithm Tutorial 14

Graph Representation
• the most common representations

Adjacency Matrix

• Uses a 2D array where rows and columns represent nodes.

• If there is an edge between two nodes, the corresponding cell contains a 1 (or the weight
of the edge in weighted graphs).

• Pros: Fast lookups (O(1)) for checking edge existence.

• Cons: Takes up O(V²) space, making it inefficient for sparse graphs.

May 9, 2025 Data Structure and Algorithm Tutorial 15

Graph Representation
2. Adjacency List

• Uses an array of linked lists or hash maps.

• Each node stores a list of its adjacent nodes.

• Pros: Efficient for sparse graphs (O(V + E) space).

• Cons: Checking edge existence takes O(V) time in worst cases.

3. Edge List

• Stores edges as a list of pairs (source, destination).

• Pros: Simple and compact representation.

• Cons: Inefficient for checking edge existence.

May 9, 2025 Data Structure and Algorithm Tutorial 16

Representation Space Complexity Edge Lookup Time Best for

Adjacency Matrix O(V²) O(1) Dense graphs

Adjacency List O(V + E) O(V) Sparse graphs

Edge List O(E) O(E) Simple storage

May 9, 2025 Data Structure and Algorithm Tutorial 17

Advanced Sorting
• Advanced sorting techniques are crucial for efficiently organizing and processing large datasets.
Here are some of the most widely used sorting algorithms:
1. Quick Sort
• Divide-and-conquer algorithm that selects a pivot and partitions the array around it.
• Time Complexity: O (n log n) (average case).
• Best for: Fast sorting in most scenarios.
2. Merge Sort
• Uses recursion to divide the array into smaller parts and merges them in sorted order.
• Time Complexity: O(n log n).
• Best for: Sorting linked lists and large datasets.
May 9, 2025 Data Structure and Algorithm Tutorial 18
Advanced Sorting
3. Heap Sort
• Uses a binary heap to sort elements efficiently.
• Time Complexity: O(n log n).
• Best for: Priority queues and real-time applications.

4. Shell Sort
• An optimized version of insertion sort that compares elements at varying gaps.
• Time Complexity: O(n log n) (depends on gap sequence).
• Best for: Medium-sized datasets.

May 9, 2025 Data Structure and Algorithm Tutorial 19

Hashing
Hashing is a technique used in data structures to store and retrieve data efficiently. It involves using a hash function to map
keys to unique indices in a hash table, allowing for fast lookups.

How Hashing Works:

1. A hash function converts a key (e.g., a name or number) into an index.

2. The key-value pair is stored at that index in a hash table.

3. When retrieving data, the same hash function is used to find the index instantly.

May 9, 2025 Data Structure and Algorithm Tutorial 20

Hash Collisions
• Hash collisions occur when two different keys produce the same hash value, leading to conflicts in a hash table.
• To resolve these collisions, several techniques are used:
. Separate Chaining (Open Hashing)
• Each index in the hash table stores a linked list of elements that hash to the same value.
• When a collision occurs, the new element is added to the linked list at that index.
• Pros: Efficient for handling multiple collisions. Cons: Requires additional memory for linked lists.
2. Open Addressing (Closed Hashing)
• Instead of using linked lists, collisions are resolved by finding another empty slot in the hash table.
• Common methods:
o Linear Probing: Finds the next available slot sequentially.
o Quadratic Probing: Uses a quadratic function to find the next slot.
o Double Hashing: Uses a second hash function to determine the next slot.
• Pros: Saves memory compared to separate chaining.
May 9, 2025 Data Structure and Algorithm Tutorial 21
Hash Table
• Stores data with key-value pairs.
• Time Complexity
• Indexing: O(1)
• Search: O(1)
• Insertion: O(1)

May 9, 2025 Data Structure and Algorithm Tutorial 22