Key Terms and Definitions

3.1 Data Operations: Insert, Delete, Search

Insert:

Adding a new element to a data structure. Insertion can occur at the beginning, end, or any arbitrary position in the data structure.

Delete:

Removing an element from a data structure. Deletion can occur by element value, index, or element position in the data structure.

Search:

Finding an element in a data structure. Searching can be by value or other criteria.

Examples of operations:

• Arrays: Insertion and deletion require shifting elements, which can be time-consuming — O(n).
• Linked Lists: Insertion and deletion can occur in O(1) if the node position is known.
• Hash Tables: Search, insertion, and deletion are usually done in O(1) on average.
• Trees: Operations of search, insertion, and deletion can be performed in O(log n) in balanced trees.

3.2 Basic Concepts: Array, List, Stack, Queue

Array

An Array is a sequence of elements of the same type, accessible by index.

Complexity of operations: Access by index — O(1), insertion, and deletion — O(n).

Example: Creating an array, modifying an element, and displaying the result

# Create an array of numbers
arr = [1, 2, 3, 4, 5]

# Modify the element at index 2 (third element, since indexing starts at 0)
arr[2] = 10

# Display the modified array
print(arr)  # Output: [1, 2, 10, 4, 5]

# Add a new element to the end of the array
arr.append(6)
print(arr)  # Output: [1, 2, 10, 4, 5, 6]

# Delete the element by index
del arr[1]
print(arr)  # Output: [1, 10, 4, 5, 6]

List

A List is a collection of elements where each element contains a reference to the next (singly linked list) or to the next and previous (doubly linked list) element.

Complexity of operations: Insertion and deletion — O(1) when position is known, search — O(n).

Example: Creating a simple singly linked list and traversing it

# Define the node structure of the list
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Create a singly linked list
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")

# Link the nodes
node1.next = node2
node2.next = node3

# Set the start of the list
list_head = node1

# Traverse the list and print data
current = list_head
while current:
    print(current.data)
    current = current.next

# Output:
# 101
# 102
# 103

Stack

A Stack is a collection of elements with LIFO (Last In, First Out) principle: last added, first out.

Complexity of operations: Push and pop — O(1).

Example: Implementing and using a stack to check bracket balance

def is_balanced(expression):
    stack = []
    opening = "({["
    closing = ")}]"
    pairs = {")": "(", "}": "{", "]": "["}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or stack.pop() != pairs[char]:
                return False
    
    return len(stack) == 0

# Check various expressions
print(is_balanced("({[]})"))  # Output: True
print(is_balanced("([)]"))    # Output: False
print(is_balanced("(("))      # Output: False

Queue

A Queue is a collection of elements with FIFO (First In, First Out) principle: first added, first out.

Complexity of operations: Enqueue and dequeue — O(1).

Example: Implementing and using a queue to simulate task processing

from collections import deque

class TaskQueue:
    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        self.queue.append(task)
        print(f"Task '{task}' added to the queue")

    def process_task(self):
        if self.queue:
            task = self.queue.popleft()
            print(f"Processing task: '{task}'")
        else:
            print("Queue is empty")

    def display_queue(self):
        print("Current task queue:", list(self.queue))

# Create and use task queue
task_queue = TaskQueue()

task_queue.add_task("Send email")
task_queue.add_task("Update database")
task_queue.add_task("Create report")

task_queue.display_queue()

task_queue.process_task()
task_queue.process_task()

task_queue.display_queue()

# Output:
# Task 'Send email' added to the queue
# Task 'Update database' added to the queue
# Task 'Create report' added to the queue
# Current task queue: ['Send email', 'Update database', 'Create report']
# Processing task: 'Send email'
# Processing task: 'Update database'
# Current task queue: ['Create report']

3.3 Differences Between Various Data Structures

Here's a breakdown of the key differences between various data structures:

Arrays:

• Access: Fast access by index — O(1).
• Resize: Fixed size, resizing requires copying all elements — O(n).
• Good for: Random access of elements when the data size is known in advance.

Linked Lists:

• Access: Slow access by index — O(n).
• Resize: Easily resizable, insertion and deletion take O(1).
• Good for: Frequent addition and removal of elements.

Stack:

• Operation Principle: LIFO.
• Operations: Insertion and deletion at one end only — O(1).
• Good for: Reversing task order, managing function calls.

Queue:

• Operation Principle: FIFO.
• Operations: Insertion and deletion at different ends — O(1).
• Good for: Managing tasks in the order they arrive.

3.4 Application of Various Data Structures

Examples of applying various data structures in practice:

Arrays

Storing fixed-length data, such as days of the week or months of the year.

Example: Using an array to work with days of the week

# Create an array with days of the week
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]

# Get the day of the week by index (e.g., third day)
print(days[2])  # Output: Wednesday

# Change the name of the day
days[0] = "Monday (Start of the week)"
print(days[0])  # Output: Monday (Start of the week)

# Iterate through all days of the week
for day in days:
    print(day)

# Output:
# Monday (Start of the week)
# Tuesday
# Wednesday
# Thursday
# Friday
# Saturday
# Sunday

Linked Lists

Implementing dynamic collections where elements can be added and removed from the middle of the collection.

Example: Implementing and using a linked list to store a to-do list

class TodoItem:
    def __init__(self, task):
        self.task = task
        self.next = None

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

    def add_task(self, task):
        new_item = TodoItem(task)
        if not self.head:
            self.head = new_item
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_item

    def display_tasks(self):
        current = self.head
        if not current:
            print("To-do list is empty")
        else:
            while current:
                print(f"- {current.task}")
                current = current.next

# Create and use a to-do list
todo = TodoList()
todo.add_task("Buy groceries")
todo.add_task("Call mom")
todo.add_task("Prepare presentation")

print("My to-do list:")
todo.display_tasks()

# Output:
# My to-do list:
# - Buy groceries
# - Call mom
# - Prepare presentation

Stack

Reversing task order, e.g., handling function calls in recursion, undo operations.

Example: Using a stack to reverse a string

def reverse_string(s):
    stack = []
    # Push each character of the string onto the stack
    for char in s:
        stack.append(char)
    
    reversed_s = ''
    # Pop characters off the stack to form the reversed string
    while stack:
        reversed_s += stack.pop()
    
    return reversed_s

# Example usage
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"Original string: {original}")
print(f"Reversed string: {reversed_str}")

# Output:
# Original string: Hello, World!
# Reversed string: !dlroW ,olleH

Queue

Managing tasks in the order they arrive, like print jobs, customer service queues.

Example: Simulating a print queue

from collections import deque

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_document(self, document):
        self.queue.append(document)
        print(f"Document '{document}' added to the print queue")

    def print_document(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Printing document: '{document}'")
        else:
            print("The print queue is empty")

    def display_queue(self):
        print("Current print queue:", list(self.queue))

# Create and use the print queue
printer = PrinterQueue()
printer.add_document("Report")
printer.add_document("Presentation")
printer.add_document("Contract")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()

# Output:
# Document 'Report' added to the print queue
# Document 'Presentation' added to the print queue
# Document 'Contract' added to the print queue
# Current print queue: ['Report', 'Presentation', 'Contract']
# Printing document: 'Report'
# Printing document: 'Presentation'
# Current print queue: ['Contract']

In this example, we created a simple simulation of a print queue. Documents are added to the end of the queue and printed in the order they arrive, demonstrating the FIFO (First In, First Out) principle.