Page |1

1. Introduction to Data Structures and Algorithms

What are Data Structures?

Data structures are ways to organize and store data to enable efficient access and modification.
Examples include arrays, linked lists, stacks, queues, trees, graphs, hash tables, and heaps.

What are Algorithms?

Algorithms are step-by-step procedures or formulas for solving problems. They are used to
manipulate data within data structures to perform tasks such as searching, sorting, and
optimization.

Why are They Important?

Efficient data structures and algorithms are critical for optimizing the performance of software
applications, improving computational efficiency, and solving complex problems.

2. Basic Data Structures

Arrays

 Description: A collection of elements identified by index or key.

 Operations: Access, insertion, deletion, traversal.
 Example:

python
Copy code
array = [1, 2, 3, 4, 5]
print(array[2]) # Output: 3
array.append(6)
print(array) # Output: [1, 2, 3, 4, 5, 6]

Linked Lists

 Description: A linear data structure where each element is a separate object, called a
node, with a reference to the next node.
 Operations: Insertion, deletion, traversal.
 Example:

python
Copy code
class Node:
def __init__(self, data):
self.data = data
self.next = None
 Page |2

class LinkedList:
def __init__(self):
self.head = None

def append(self, data):

new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)

Stacks

 Description: A linear data structure that follows the Last In, First Out (LIFO) principle.
 Operations: Push, pop, peek.
 Example:

python
Copy code
stack = []
stack.append(1)
stack.append(2)
print(stack.pop()) # Output: 2

Queues

 Description: A linear data structure that follows the First In, First Out (FIFO) principle.
 Operations: Enqueue, dequeue, peek.
 Example:

python
Copy code
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft()) # Output: 1

Trees

 Description: A hierarchical data structure consisting of nodes, with a root node and child
nodes forming a tree-like structure.
 Operations: Insertion, deletion, traversal (in-order, pre-order, post-order).
 Example:
 Page |3

python
Copy code
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def in_order_traversal(root):
if root:
in_order_traversal(root.left)
print(root.data)
in_order_traversal(root.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

Graphs

 Description: A collection of nodes (vertices) and edges connecting them.

 Operations: Add vertex, add edge, search (DFS, BFS).
 Example:

python
Copy code
from collections import defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):

self.graph[u].append(v)

def bfs(self, start):

visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
print(vertex)
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)

Hash Tables

 Description: A data structure that maps keys to values for efficient lookup.
 Operations: Insert, delete, search.
 Example:

python
Copy code
 Page |4

hash_table = {}
hash_table['key1'] = 'value1'
print(hash_table['key1']) # Output: value1

3. Basic Algorithms
Searching Algorithms

 Linear Search: Simple search algorithm that checks each element in the list until the
target is found.

python
Copy code
def linear_search(arr, target):
for i, value in enumerate(arr):
if value == target:
return i
return -1

 Binary Search: Efficient search algorithm for sorted arrays, repeatedly dividing the
search interval in half.

python
Copy code
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

Sorting Algorithms

 Bubble Sort: Simple sorting algorithm that repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order.

python
Copy code
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
 Page |5

 Quick Sort: Efficient sorting algorithm that uses divide-and-conquer approach to sort
elements.

python
Copy code
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

4. Practice Problems
Easy

 Reverse a string
 Check if a string is a palindrome
 Find the maximum and minimum elements in an array

Medium

 Implement a stack using queues

 Find the intersection of two linked lists
 Implement depth-first search in a graph

Hard

 Implement a binary search tree and its operations

 Find the shortest path in a weighted graph (Dijkstra's algorithm)
 Implement a balanced binary tree (AVL tree)

5. Resources for Learning

 Books:
o "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
o "Algorithms" by Robert Sedgewick and Kevin Wayne
o "Data Structures and Algorithms in Python" by Michael T. Goodrich
 Online Courses:
o Coursera: Data Structures and Algorithms Specialization
o Udemy: Mastering Data Structures & Algorithms using C and C++
 Practice Platforms:
o LeetCode
o HackerRank
o GeeksforGeeks