Python - Data Structures and Algorithms
Arrays
One-Dimensional Array
A one-dimensional array, also known as a list, is a collection of elements of the same data type. In Python, lists are created using square brackets [].
# Creating a list
my_list = [1, 2, 3, 4, 5]
# Accessing elements
print(my_list[0]) # Output: 1
print(my_list[-1]) # Output: 5
# Modifying elements
my_list[0] = 10
print(my_list) # Output: [10, 2, 3, 4, 5]
Multi-Dimensional Array
A multi-dimensional array, also known as a matrix, is a collection of one-dimensional arrays. In Python, matrices are created using nested lists.
# Creating a matrix
my_matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# Accessing elements
print(my_matrix[1][1]) # Output: 5
# Modifying elements
my_matrix[1][1] = 10
print(my_matrix) # Output: [[1, 2, 3], [4, 10, 6], [7, 8, 9]]
Linked Lists
A linked list is a linear data structure where each element, called a node, consists of data and a reference to the next node in the sequence. In Python, linked lists can be implemented using classes.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
Stacks and Queues
A stack is a Last-In-First-Out (LIFO) data structure. In Python, stacks can be implemented using lists.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def peek(self):
if not self.is_empty():
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
A queue is a First-In-First-Out (FIFO) data structure. In Python, queues can be implemented using lists and the built-in collections.deque class.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
def peek(self):
if not self.is_empty():
return self.items[0]
def is_empty(self):
return len(self.items) == 0
Sorting Algorithms
Bubble Sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
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]
Selection Sort
Selection sort is a simple sorting algorithm that divides the input into a sorted and an unsorted region. The sorted region is built one item at a time by finding the smallest item in the unsorted region and putting it at the beginning of the sorted region.
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
Merge Sort
Merge sort is a divide-and-conquer algorithm that divides the input into two halves, sorts them recursively, and then merges the sorted halves.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result