DATA STRUCTURES, SORTING AND SEARCHING ALGORITHMS

 A data structure is a particular way of organizing and storing data in a computer so that it
can be accessed and modified efficiently.
 Crucial for designing efficient algorithms.
 Framework that holds the data, and an algorithm is the tool used to manipulate that data
within the framework to achieve a desired outcome

Key Terminology

 Data: Raw facts and figures.

 Structure: A specific way of organizing the data.
 Abstract Data Type : A mathematical model for a data type. It defines the operations
that can be performed on the data structure, but not how those operations are
implemented. Examples include List, Stack, Queue, and Map.
 Time Complexity: Measures how the running time of an algorithm grows as the input
size (n) grows [O(1), O(logn), O(n), O(n2) ]
 Space Complexity: Measures the amount of memory space an algorithm uses as a
function of the input size (n).
Linear Data Structures

Data elements are arranged sequentially or linearly.

1. Arrays

An array is a collection of items stored at contiguous memory locations and can be accessed
using an index.

 Characteristics:
o Elements are of the same data type.
o Size is often fixed at the time of creation (in languages like C/Java) or dynamic
(like in Python/JavaScript).
 Operations & Complexity (for a static array
 Use Cases: Storing a fixed number of items, implementing matrices, and serving as the
underlying structure for other data structures (like ArrayLists).

Creating an array

# 1. Creating an empty list

my_list_empty = []

# 2. Creating a list with initial values

my_list_data = [10, 'hello', 3.14, True]

# 3. Creating a list using a list comprehension (for generating sequences)

# This creates a list of squares from 0 to 9
my_list_squares = [x**2 for x in range(10)]

accessing array elements

print(my_list_data[0]) # Output: 10 (Access the first element)
print(my_list_data[-1]) # Output: True (Access the last element)
 my_list_data[1] = 'world' # Modify an element
print(my_list_data) # Output: [10, 'world', 3.14, True]

my_list_data.append(50) # Add an element to the end

print(my_list_data) # Output: [10, 'world', 3.14, True, 50]

2. Linked Lists

A linked list is a sequence of nodes where each node contains data and a pointer (or reference)
to the next node in the sequence.

 Types:
o Singly Linked List: Nodes point only forward.
o Doubly Linked List: Nodes point both forward and backward (to the previous
node).
o Circular Linked List: The last node points back to the first node.
 Advantages over Arrays: Dynamic size, and easy insertion/deletion without shifting
elements.
 Disadvantages: Requires extra memory for pointers, and accessing an element takes
longer.

3. Stacks (LIFO)

A stack is an ADT where insertion and deletion operations occur at one end, called the Top. It
follows the Last-In, First-Out (LIFO) principle.

 Primary Operations:
o Push: Adds an element to the top. (O(1))
o Pop: Removes and returns the element from the top. (O(1))
o Peek/Top: Returns the top element without removing it. (O(1))
 Use Cases: Function call management (call stack), expression evaluation, and undo/redo
mechanisms.
4. Queues (FIFO)

A queue is an ADT where insertion occurs at the Rear (or back) and deletion occurs at the
Front. It follows the First-In, First-Out (FIFO) principle.

 Primary Operations:
o Enqueue: Adds an element to the rear. (O(1))
o Dequeue: Removes and returns the element from the front. (O(1))
o Peek/Front: Returns the front element without removing it. (O(1))
 Use Cases: Task scheduling (CPU scheduling), breadth-first search (BFS), and handling
requests on a single shared resource.

Non-Linear Data Structures

Data elements are not arranged sequentially; instead, they are connected in various ways.

1. Trees

A tree is a non-linear hierarchical data structure consisting of nodes connected by edges.

 Terminology: Root (top node), Parent, Child, Leaf (node with no children), Height
(longest path from root to a leaf).
 Binary Tree: Each node has at most two children (left and right).
 Binary Search Tree (BST): A binary tree where, for every node, all keys in the left
subtree are smaller than the key in the node, and all keys in the right subtree are larger.
o Search, Insertion, Deletion: Average complexity is O(logn), worst-case is O(n).
 Balanced Search Trees (AVL, Red-Black): Variations of BSTs that automatically keep
the height minimal, guaranteeing O(logn) performance for all major operations.
  Use Cases: File systems, database indexing, and sorting algorithms.

2. Heaps

A heap is a specialized tree-based data structure that satisfies the heap property. It is typically
implemented as a complete binary tree.

 Types:
o Max-Heap: The value of each node is greater than or equal to the values of its
children.
o Min-Heap: The value of each node is less than or equal to the values of its
children.
 Primary Operation: Heapify (to maintain the heap property).
 Use Cases: Implementing Priority Queues and the Heap Sort algorithm.

3. Graphs
A graph is a set of Vertices (nodes) and Edges (connections) that link pairs of vertices.

 Types: Undirected (edges have no direction) and Directed (edges have direction, e.g., A
→ B).
 Representations:
o Adjacency Matrix: A 2D array where M[i][j]=1 if there is an edge between
vertex i and vertex j.
o Adjacency List: An array of lists/linked lists where the index represents a vertex
and the list stores its neighbors.
 Graph Traversal Algorithms:
o Breadth-First Search (BFS): Explores neighbors level by level (uses a Queue).
o Depth-First Search (DFS): Explores as far as possible along each branch before
backtracking (uses a Stack or recursion).
 Use Cases: Social networks, road maps, and modeling connections between components.
Hash Tables (Maps/Dictionaries)

A hash table is a data structure that implements an associative array abstract data type, which is
used to map keys to values.

 Mechanism: A Hash Function is used to compute an index (or "slot") into an array,
from which the desired value can be found.
 Collision: Occurs when two different keys hash to the same index.
 Collision Resolution Techniques:
o Chaining: Store conflicting keys/values in a linked list at the same index.
o Open Addressing (Probing): Look for the next available empty slot (linear,
quadratic, or double hashing).
 Performance: Ideally, average-case insertion, deletion, and search are O(1). Worst-case
is O(n) if all keys collide.
 Use Cases: Caching, symbol tables in compilers, and fast data lookups.
Relationship between Data Structures and Algorithms

Data structures and algorithms are two sides of the same coin in computer science; they are
inextricably linked and fundamentally interdependent.1 An algorithm is a step-by-step procedure
for solving a problem, and a data structure is the organized way data is stored to be
manipulated by that algorithm.2

1. Interdependence and Efficiency

The choice of one directly impacts the efficiency and design of the other.3

 Algorithms Depend on Data Structures: An algorithm cannot execute efficiently (or

sometimes at all) without an appropriate data structure to organize the information it
needs to process.4
o Example: To perform an efficient Binary Search (an algorithm), the data must
be stored in a sorted Array or a Binary Search Tree (data structures).5 A
sequential search is necessary if the data is stored in an unsorted Linked List,
which is much slower.
 Data Structures Support Algorithms: The operations defined on a data structure are
specifically designed to enable certain algorithms to perform well.
o Example: A Min-Heap data structure is specifically designed with the Heap
Property to allow the Min-Heapify algorithm to maintain the property in O(\log
n) time, which is essential for algorithms like Heap Sort or Dijkstra's Shortest
Path.7

2. The Equation for Effective Programming

A common way to conceptualize their relationship is:

Program = Algorithms + Data Structures

 Data Structure: Focuses on the organization of data and the cost (time/space) of
accessing and modifying it.8
 Algorithm: Focuses on the logic and steps required to transform the data or find a
solution.9

3. Concrete Examples

Optimal Data
Problem Required Algorithm Efficiency Gain
Structure

Graph (via Breadth-First Search Allows exploration of

Pathfinding
Adjacency List) (BFS) or Dijkstra's connections efficiently.

Fast Hash Table Average O(1) search and

Hashing Function
Lookups (Map/Dictionary) insertion.

Ensures the highest priority task

Task Priority Queue Insert and Extract-Min
is always retrieved first in O(\log
Scheduling (using a Heap) operations
n) time.

Push (for undo history)

Enforces the Last-In, First-Out
Undo/Redo Stack and Pop (for redo
(LIFO) order.
history)
SORTING ALGORITHMS

Sorting algorithms are fundamental procedures used to arrange elements of a list or array in a
specific order (e.g., numerical or lexicographical).

The efficiency of a sorting algorithm is typically measured by its Time Complexity and Space
Complexity.

1. Simple (Quadratic Time) Sorting Algorithms

These algorithms have a worst-case and average time complexity of O(n^2), making them
inefficient for large datasets.

A. Bubble Sort

 Mechanism: Repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order. The largest unsorted element "bubbles up" to its
correct position in each pass.
 Best Use: Simple to implement, or for checking if a list is nearly sorted.
 Time Complexity:
o Worst-case/Average: O(n^2) (e.g., reverse sorted array)
o Best-case: O(n) (already sorted array)
 Space Complexity: O(1) (In-place)
 Stability: Stable (maintains the relative order of equal elements).

B. Selection Sort

 Mechanism: Divides the list into a sorted and an unsorted sublist. It repeatedly finds the
minimum element from the unsorted sublist and swaps it with the leftmost element of the
unsorted sublist, expanding the sorted sublist.
 Best Use: Situations where minimizing the number of swaps is critical, as it performs at
most n swaps.
 Time Complexity:
o Worst-case/Average/Best-case: O(n^2) (Performance is consistent regardless of
initial order).
 Space Complexity: O(1) (In-place)
 Stability: Unstable in its standard form.

C. Insertion Sort �
  Mechanism: Builds the final sorted array one item at a time. It iterates through the input
elements, taking one element and finding its correct position within the already sorted
part of the array, then shifting the other elements to make room.
 Best Use: Small arrays, or arrays that are mostly sorted.
 Time Complexity:
o Worst-case/Average: O(n^2)
o Best-case: O(n) (already sorted array)
 Space Complexity: O(1) (In-place)
 Stability: Stable.

2. Efficient (O(n \log n)) Sorting Algorithms

These algorithms are significantly faster than quadratic sorts for large inputs and form the
backbone of practical sorting implementations.

A. Merge Sort

 Mechanism: A Divide and Conquer algorithm.

1. Divide: Continuously divides the array into two halves until it has n sub-arrays,
each containing one element (which is considered sorted).
2. Conquer/Merge: Repeatedly merges the sub-arrays to produce new sorted sub-
arrays until one final sorted array is obtained. The merging step is the core,
comparing elements from two sorted sub-arrays to form a larger sorted array.
 Best Use: Sorting Linked Lists (as it requires sequential access) and for external sorting
(where data is too large for memory).
 Time Complexity:
o Worst-case/Average/Best-case: O(n \log n) (Consistent performance).
 Space Complexity: O(n) (Requires auxiliary space for merging).
 Stability: Stable.

B. Quick Sort

 Mechanism: Another Divide and Conquer algorithm.

1. Pivot Selection: Chooses an element from the array, called the pivot.
2. Partition: Rearranges the array so that all elements smaller than the pivot come
before it, and all elements greater than the pivot come after it. The pivot is now in
its final sorted position.
3. Recurse: Recursively applies the above steps to the sub-arrays formed by the
partition.
 Best Use: Generally the fastest sorting algorithm in practice due to better constants in the
O(n \log n) performance and excellent cache performance.
 Time Complexity:
 o Worst-case: O(n^2) (Occurs when the pivot is always the smallest or largest
element, e.g., in an already sorted array). This is often mitigated by choosing a
random pivot.
o Average/Best-case: O(n \log n)
 Space Complexity: O(\log n) (Due to the recursion stack, or O(1) in a non-recursive, in-
place implementation).
 Stability: Unstable in its standard in-place form.

C. Heap Sort

 Mechanism: Utilizes the Binary Heap data structure.

1. Build Heap: Converts the input array into a Max-Heap (a complete binary tree
where every parent node is greater than its children).
2. Sort Down: Repeatedly extracts the maximum element (the root of the heap) and
places it at the end of the array. The remaining elements are then heapified
(restoring the heap property) to find the new maximum.
 Best Use: When guaranteed O (n \log n) worst-case performance is required without
needing O(n) extra space (like Merge Sort).
 Time Complexity:
o Worst-case/Average/Best-case: O(n \log n)
 Space Complexity: O (1) (In-place, as the heap is built on the array itself).
 Stability: Unstable.

3. Non-Comparison Sorting Algorithms

These algorithms do not rely on comparing elements, allowing them to achieve O(n) time
complexity in specific scenarios. They only work for data with certain constraints (e.g., integers
within a limited range).

A. Counting Sort

 Mechanism: Assumes input elements are integers within a small, known range [0, k].
1. Counts the number of occurrences of each distinct element in a counting array of
size k+1.
2. Uses the count information to place each element into its correct position in the
output array.
 Time Complexity: O (n+k), where k is the range of input values. If k is O (n), the time
complexity is O (n).
 Space Complexity: O (n+k) (Requires two auxiliary arrays).
 Stability: Can be Stable if implemented correctly.

B. Radix Sort
 Mechanism: A non-comparison integer sorting algorithm that sorts data by processing
individual digits (or "radixes").
1. Sorts the input array based on the least significant digit (LSD) using a stable
sorting algorithm (often Counting Sort).
2. Repeats the process for the second least significant digit, and so on, until the most
significant digit.
 Time Complexity: O (d \cdot (n+k)), where d is the number of digits in the largest
number, and k is the base (radix) of the number system.
 Space Complexity: O (n+k) (Auxiliary space for the stable sort used).
 Stability: Stable (due to the use of a stable intermediate sort).
Summary of Key Properties
Worst-Case Average Best-Case Space
Algorithm Stable? Method
Time Time Time Complexity

Divide &
Merge Sort O(n \log n) O(n \log n) O(n \log n) O(n) Yes
Conquer

Divide &
Quick Sort O(n^2) O(n \log n) O(n \log n) O(\log n) No
Conquer

Heap Sort O(n \log n) O(n \log n) O(n \log n) O(1) No Selection

Insertion
O(n^2) O(n^2) O(n) O(1) Yes Insertion
Sort

Selection
O(n^2) O(n^2) O(n^2) O(1) No Selection
Sort

Bubble Sort O(n^2) O(n^2) O(n) O(1) Yes Exchange

Counting
O(n+k) O(n+k) O(n+k) O(n+k) Yes Counting
Sort
SEARCHING ALGORITHMS

Search algorithms are methods for finding a specific element (or a set of elements) that satisfy a
given property within a collection of items (like an array, list, tree, or graph).

The efficiency of a search algorithm is crucial in determining the performance of a program.

1. Linear Search (Sequential Search)

A. Mechanism

 Concept: The simplest search algorithm. It checks every element in the collection
sequentially from the start until the target value is found or the end of the collection is
reached.
 Data Structure Requirement: Can be applied to any unsorted collection (array, linked
list, etc.).
 Process:
1. Start at the first element.
2. Compare the current element with the target key.
3. If they match, the search is successful, and the index is returned.
4. If they don't match, move to the next element.
5. If the end is reached without finding the key, the search is unsuccessful.

B. Complexity

 Time Complexity:
o Worst-case/Average: O(n) (The element is at the end or not present, requiring n
comparisons).
o Best-case: O(1) (The element is the first item).
 Space Complexity: O(1) (In-place).

2. Binary Search
A. Mechanism

 Concept: A highly efficient search technique that works by repeatedly dividing the
search interval in half.
 Data Structure Requirement: The collection must be sorted (usually an array or a list
that supports O(1) random access).
 Process:
1. Find the middle element of the search interval.
 2. Compare the middle element with the target key.
3. If they match, the search is successful.
4. If the key is less than the middle element, repeat the search in the left half.
5. If the key is greater than the middle element, repeat the search in the right half.
6. If the interval becomes empty, the search is unsuccessful.

B. Complexity

 Time Complexity:
o Worst-case/Average/Best-case: O(\log n) (Because the search space is halved in
each step).
 Space Complexity: O(1) for an iterative approach, or O(\log n) for a recursive approach
because of the recursion stack

3. Graph Traversal Searches

These algorithms are designed for searching through Graph and Tree data structures to find
paths, nodes, or to explore connections.

A. Breadth-First Search (BFS)

 Concept: An algorithm for traversing or searching tree or graph data structures. It

explores all the neighbor nodes at the present depth level before moving on to the nodes
at the next depth level.
 Data Structure Used: Queue (to manage the nodes to visit, ensuring FIFO order).
 Search Strategy: Level-by-level (shortest path in an unweighted graph).
 Process:
1. Start at a root/start node and enqueue it.
2. Dequeue a node, visit it, and then enqueue all its unvisited neighbors.
3. Repeat until the queue is empty.
 Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the
number of edges.

B. Depth-First Search (DFS)

 Concept: An algorithm for traversing or searching tree or graph data structures. It

explores as far as possible along each branch before backtracking.
 Data Structure Used: Stack (implicitly using the function call stack for recursion, or
explicitly using a stack for an iterative approach).
 Search Strategy: As deep as possible (explores a path completely before exploring
siblings).
 Process:
1. Start at a root/start node and push it onto the stack.
2. Pop a node, visit it, and then push all its unvisited neighbors onto the stack.
3. Repeat until the stack is empty.
  Time Complexity: O(V + E), where V is the number of vertices and E is the number of
edges.

4. Specialized/Informed Searches
These algorithms typically operate on weighted graphs and use domain knowledge (heuristics) to
guide the search.

A. Dijkstra's Algorithm

 Concept: Finds the shortest path between a starting node (source) and all other nodes in
a weighted graph with non-negative edge weights.
 Data Structure Used: A Min-Priority Queue (usually implemented with a Min-Heap)
to efficiently extract the unvisited node with the smallest current distance.
 Search Strategy: Greedy. It continuously selects the unvisited node closest to the
source.
 Time Complexity: O((V+E) \log V) using a binary heap implementation.

B. A* Search

 Concept: An informed search algorithm (best-first search) that finds the shortest path
between nodes in a graph by using a heuristic function to estimate the cost from the
current node to the goal.
 Search Evaluation: Uses a total cost function f(n) = g(n) + h(n):
o g(n): The actual cost from the starting node to node n.
o h(n): The estimated cost (heuristic) from node n to the goal node.
 Time Complexity: Depends heavily on the quality of the heuristic. In the worst case, it
can degrade to O(E) or O(V^2) (similar to Dijkstra's), but it is often much faster in
practice.
 Use Case: Robotics, video game pathfinding, and planning.