Sure! Here's the content with notes and code separated.

---

Data Structures and Algorithms in Python

1. Data Structures

1.1 Arrays (Lists in Python)

Notes: An array (or list in Python) is a collection of elements identified by an index or key. Lists in Python are dynamic, meaning they can grow or shrink in size. Lists can store elements of various types (e.g., integers, strings, etc.).

• Operations:
  • Access: arr[index]
  • Insert: arr.append(value) or arr.insert(index, value)
  • Remove: arr.remove(value) or arr.pop(index)
  • Traverse: Loop through the list.

Code:

# Example of list usagearr= [1, 2, 3, 4, 5]
arr.append(6) # Add 6 at the endarr.insert(2, 9) # Insert 9 at index 2arr.remove(4) # Remove first occurrence of 4print(arr)

1.2 Linked List

Notes: A linked list is a linear collection of elements called nodes. Each node contains a value and a reference (or pointer) to the next node in the sequence.

• Types:

  • Singly Linked List: Each node points to the next.
  • Doubly Linked List: Each node points to both the next and the previous node.

• Basic Operations:

  • Insertion: At the beginning, end, or a specific index.
  • Deletion: At the beginning, end, or a specific node.

Code:

classNode:
def__init__(self, data):
self.data=dataself.next=NoneclassLinkedList:
def__init__(self):
self.head=Nonedefappend(self, data):
new_node=Node(data)
ifnotself.head:
self.head=new_nodereturnlast=self.headwhilelast.next:
last=last.nextlast.next=new_nodedefdisplay(self):
current=self.headwhilecurrent:
print(current.data, end=" -> ")
current=current.nextprint("None")
ll=LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()

1.3 Stack

Notes: A stack is a linear data structure that follows the LIFO (Last In First Out) principle. Operations are primarily push (add to the stack) and pop (remove from the stack).

Code:

stack= []
stack.append(1) # Pushstack.append(2)
stack.pop() # Pop (removes 2)print(stack)

1.4 Queue

Notes: A queue is a linear data structure that follows the FIFO (First In First Out) principle. The two main operations are enqueue (add to the queue) and dequeue (remove from the queue).

Code:

fromcollectionsimportdequequeue=deque()
queue.append(1) # Enqueuequeue.append(2)
queue.popleft() # Dequeueprint(queue)

1.5 Hash Tables (Dictionaries in Python)

Notes: A hash table stores data in key-value pairs. In Python, dictionaries are implemented as hash tables, providing efficient lookups.

Code:

hash_map= {}
hash_map['key1'] ='value1'hash_map['key2'] ='value2'print(hash_map['key1']) # O(1) average time complexity

1.6 Trees

Notes: A tree is a hierarchical data structure with a root node and subtrees (children nodes).

• Binary Tree: A tree where each node has at most two children (left and right).

Code:

classTreeNode:
def__init__(self, data):
self.data=dataself.left=Noneself.right=NoneclassBinaryTree:
def__init__(self, root):
self.root=TreeNode(root)
definorder_traversal(self, node):
ifnode:
self.inorder_traversal(node.left)
print(node.data, end=" ")
self.inorder_traversal(node.right)
bt=BinaryTree(1)
bt.root.left=TreeNode(2)
bt.root.right=TreeNode(3)
bt.inorder_traversal(bt.root)

1.7 Graphs

Notes: A graph is a collection of nodes (vertices) and edges connecting them. Graphs can be directed or undirected, and weighted or unweighted.

Code:

# Adjacency List representationgraph= {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}

---

2. Algorithms

2.1 Sorting Algorithms

Bubble Sort

Notes: Bubble Sort is a simple comparison-based sorting algorithm where the largest element "bubbles up" to its correct position in each iteration.

Code:

defbubble_sort(arr):
n=len(arr)
foriinrange(n):
forjinrange(0, n-i-1):
ifarr[j] >arr[j+1]:
arr[j], arr[j+1] =arr[j+1], arr[j]
arr= [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)

Merge Sort

Notes: Merge Sort is a divide-and-conquer algorithm. It divides the array into halves, recursively sorts them, and then merges them.

Code:

defmerge_sort(arr):
iflen(arr) >1:
mid=len(arr) //2left_half=arr[:mid]
right_half=arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i=j=k=0whilei<len(left_half) andj<len(right_half):
ifleft_half[i] <right_half[j]:
arr[k] =left_half[i]
i+=1else:
arr[k] =right_half[j]
j+=1k+=1whilei<len(left_half):
arr[k] =left_half[i]
i+=1k+=1whilej<len(right_half):
arr[k] =right_half[j]
j+=1k+=1arr= [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr)

2.2 Searching Algorithms

Binary Search

Notes: Binary Search works on sorted arrays and repeatedly divides the search interval in half.

Code:

defbinary_search(arr, x):
low=0high=len(arr) -1whilelow<=high:
mid= (low+high) //2ifarr[mid] ==x:
returnmidelifarr[mid] <x:
low=mid+1else:
high=mid-1return-1arr= [2, 3, 4, 10, 40]
result=binary_search(arr, 10)
print("Element found at index:", result)

2.3 Graph Algorithms

Depth-First Search (DFS)

Notes: DFS explores as far as possible along each branch before backtracking.

Code:

defdfs(graph, node, visited=None):
ifvisitedisNone:
visited=set()
visited.add(node)
forneighboringraph[node]:
ifneighbornotinvisited:
dfs(graph, neighbor, visited)
returnvisitedgraph= {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
print(dfs(graph, 'A'))

Breadth-First Search (BFS)

Notes: BFS explores all neighbors at the present depth level before moving on to nodes at the next depth level.

Code:

fromcollectionsimportdequedefbfs(graph, start):
visited=set()
queue=deque([start])
visited.add(start)
whilequeue:
vertex=queue.popleft()
print(vertex, end=" ")
forneighboringraph[vertex]:
ifneighbornotinvisited:
visited.add(neighbor)
queue.append(neighbor)
graph= {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
bfs(graph, 'A')

---

Conclusion

Data structures and algorithms are key to optimizing and solving problems efficiently. The examples provided give a practical introduction to implementing these concepts in Python. Practice solving problems with these structures and algorithms to master them.