Crash Course on Data Structures: A Comprehensive Guide • Prajwal Murthy

Data structures are the building blocks of computer programs. They provide efficient ways to store, organize, and manage data, which is a fundamental aspect of software development. Whether you’re a beginner looking to learn the basics or an experienced programmer aiming to refresh your knowledge, this crash course on data structures has you covered.

What Are Data Structures?

In computer science, data structures are specialized formats for organizing and storing data. They enable efficient data manipulation, retrieval, and storage. Think of them as the containers that hold your data, each with its own unique properties and advantages.

Why Are Data Structures Important?

Understanding data structures is essential for several reasons:

Efficiency: Choosing the right data structure can significantly impact the efficiency of your algorithms. Well-designed data structures allow for faster data access and manipulation.
Problem Solving: Many programming problems involve organizing and processing data. Proficiency in data structures is crucial for solving these problems effectively.
Memory Management: Data structures also play a vital role in memory management. They help you allocate and deallocate memory efficiently, preventing memory leaks and optimizing resource usage.

Common Data Structures

Let’s explore some common data structures and their key characteristics:

1. Arrays

Description: Arrays are ordered collections of elements, each identified by an index or a key.
Use Cases: Storing a fixed number of elements with constant-time access.
Complexity: Access (O(1)), Insertion/Deletion (O(n)), Search (O(n)).

class DynamicArray:
    def __init__(self):
        self.capacity = 1  # Initial capacity
        self.length = 0   # Current number of elements
        self.data = [None] * self.capacity

    def is_empty(self):
        return self.length == 0

    def append(self, item):
        if self.length == self.capacity:
            self.resize(2 * self.capacity)  # Double the capacity if full
        self.data[self.length] = item
        self.length += 1

    def get(self, index):
        if 0 <= index < self.length:
            return self.data[index]
        else:
            raise IndexError("Index out of range")

    def set(self, index, item):
        if 0 <= index < self.length:
            self.data[index] = item
        else:
            raise IndexError("Index out of range")

    def delete(self, index):
        if 0 <= index < self.length:
            for i in range(index, self.length - 1):
                self.data[i] = self.data[i + 1]
            self.data[self.length - 1] = None
            self.length -= 1
        else:
            raise IndexError("Index out of range")

    def resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.length):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

    def __str__(self):
        return '[' + ', '.join(str(self.data[i]) for i in range(self.length)) + ']'

# Example usage:
arr = DynamicArray()
arr.append(1)
arr.append(2)
arr.append(3)
print("Array:", arr)
print("Element at index 1:", arr.get(1))
arr.set(1, 4)
print("Modified Array:", arr)
arr.delete(0)
print("Array after deleting at index 0:", arr)

2. Linked Lists

Description: Linked lists are chains of nodes, each containing data and a reference to the next node.
Use Cases: Dynamic memory allocation, efficient insertions and deletions.
Complexity: Access (O(n)), Insertion/Deletion (O(1)), Search (O(n)).

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

    def is_empty(self):
        return self.head is None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.prepend(0)
llist.display()
llist.delete(2)
llist.display()

3. Stacks

Description: Stacks follow the Last-In-First-Out (LIFO) principle and are used for managing function calls, undo operations, and more.
Use Cases: Function call management, expression evaluation, undo mechanisms.
Complexity: Push/Pop (O(1)).

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("Pop from an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("Peek from an empty stack")

    def size(self):
        return len(self.items)

# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Stack:", stack.items)
print("Peek:", stack.peek())
print("Pop:", stack.pop())
print("Stack size:", stack.size())

4. Queues

Description: Queues follow the First-In-First-Out (FIFO) principle and are used for tasks like scheduling.
Use Cases: Task scheduling, print job management, breadth-first search.
Complexity: Enqueue/Dequeue (O(1)).

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            raise IndexError("Dequeue from an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            raise IndexError("Peek from an empty queue")

    def size(self):
        return len(self.items)

# Example usage:
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("Queue:", queue.items)
print("Peek:", queue.peek())
print("Dequeue:", queue.dequeue())
print("Queue size:", queue.size())

5. Trees

Description: Trees are hierarchical data structures with nodes connected by edges. They include binary trees, AVL trees, and more.
Use Cases: Hierarchical data representation, efficient searching and sorting.
Complexity: Search/Insertion/Deletion (O(log n) for balanced trees).

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_data):
        self.root = Node(root_data)

    def insert(self, data):
        self._insert_recursively(self.root, data)

    def _insert_recursively(self, current_node, data):
        if data < current_node.data:
            if current_node.left is None:
                current_node.left = Node(data)
            else:
                self._insert_recursively(current_node.left, data)
        else:
            if current_node.right is None:
                current_node.right = Node(data)
            else:
                self._insert_recursively(current_node.right, data)

    def search(self, data):
        return self._search_recursively(self.root, data)

    def _search_recursively(self, current_node, data):
        if current_node is None:
            return False
        if current_node.data == data:
            return True
        if data < current_node.data:
            return self._search_recursively(current_node.left, data)
        else:
            return self._search_recursively(current_node.right, data)

# Example usage:
tree = BinaryTree(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
tree.insert(60)
tree.insert(80)

print("Search for 40:", tree.search(40))  # Output: True
print("Search for 90:", tree.search(90))  # Output: False

6. Graphs

Description: Graphs consist of vertices and edges, allowing for complex relationships between data points.
Use Cases: Social networks, network topology, route finding.
Complexity: Depends on the specific algorithm and structure used.

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)

    def display(self):
        for vertex, neighbors in self.graph.items():
            print(f"{vertex}: {neighbors}")

# Example usage:
graph = Graph()
graph.add_vertex('A')
graph.add_vertex('B')
graph.add_vertex('C')
graph.add_edge('A', 'B')
graph.add_edge('B', 'C')
graph.add_edge('A', 'C')

graph.display()

Data structures are a cornerstone of computer science and programming. They provide the foundation for efficient algorithms and problem-solving. Whether you’re building a simple application or tackling complex computational challenges, a solid understanding of data structures is indispensable. Dive into the world of data structures, explore their intricacies, and watch your programming skills soar to new heights.

Thank you! Happy coding!