Data Structure and GUI: ADT, Comprehension, Time Complexity

 

---

Abstract Data Structures

Abstract data structures provide a logical way to organize and manipulate data. These include structures such as:

• Stacks: Operate on a Last-In-First-Out (LIFO) principle.
• Queues: Operate on a First-In-First-Out (FIFO) principle.
• Trees: Hierarchical data structures with nodes connected by edges.
• Graphs: Networks of nodes and edges.
• Linked Lists: Sequences of nodes, where each node links to the next.

---

Primitive Data Structures

Primitive data structures are the most basic data types provided by programming languages:

• Integer (int): Whole numbers.
• Floating-point (float): Decimal numbers.
• Character (char): Single characters.
• Boolean (bool): True or False values.

---

Non-Primitive Data Structures

Non-primitive data structures are derived from primitive types and can store multiple values:

• Arrays: Fixed-size collections of similar types.
• Lists: Dynamic-size collections (e.g., Python list).
• Dictionaries: Key-value pairs (e.g., Python dict).
• Sets: Unordered collections of unique items.
• Tuples: Immutable ordered collections.

List Comprehensions

A concise way to create lists using an expression inside square bracket:

# Example: Create a list of squares of numbers from 0 to 9
squares = [x**2 for x in range (10)]

Accessing Elements

• Access by index: squares [2] give the 3rd element.
• Slicing: squares [2:5] gives a sublist from index 2 to 4.

Performing Operations

• Add elements: squares.append(100)
• Modify elements: squares [1] = 10

Comprehension Using if

Filter elements with a condition:

# Example: Keep only even numbers
evens = [x for x in range(10) if x % 2 == 0]


Comprehension Using if-else
Apply conditions to elements:
# Example: Label numbers as "Even" or "Odd"
labels = ["Even" if x % 2 == 0 else "Odd" for x in range(10)]


Nested List Comprehensions
Used for working with multidimensional data:
# Example: Create a multiplication table
table = [[i * j for j in range (1, 6)] for i in range (1, 6)]


Dictionary Comprehensions
Create dictionaries in a compact way:

# Example: Map numbers to their squares
squares_dict = {x: x**2 for x in range (5)}

Accessing Elements
Access values by their key: squares_dict[2] gives the square of 2.
Performing Operations
Add a key-value pair: squares_dict[5] = 25
Update a value: squares_dict[2] = 10
Comprehension Using zip()
Combine two iterables into a dictionary:
keys = ['a', 'b', 'c']
values = [1, 2, 3]
zipped_dict = {k: v for k, v in zip (keys, values)}


Comprehension for Lambda Functions
Use lambda functions in comprehensions:
# Example: Square numbers using lambda
squared = [(lambda x: x**2)(x) for x in range (5)]


Nested Dictionary Comprehensions
Create dictionaries with complex structures:

# Example: Nested dictionary for students and their grades
students = {f"Student {i}": {f"Subject {j}": j*10 for j in range(1, 4)} for i in range(1, 3)}


Processing Lists in Parallel
Using zip () to iterate over multiple lists simultaneously:

list1 = [1, 2, 3]
list2 = [4, 5, 6]
summed = [x + y for x, y in zip (list1, list2)]
This provides efficient and Pythonic ways to handle parallel list operations.

Time Functionality: Big O Notation
Case Scenarios
When evaluating an algorithm, we consider three scenarios:
Best Case: Minimum time taken by an algorithm.
Average Case: Average time over all inputs of a given size.
Worst Case: Maximum time taken (used for Big O).
Example:
Searching in a list:
Best Case: The item is at the first position (O (1)).
Worst Case: The item is at the last position or not present (O(n)).
Time Complexity in Python Collections
Python collections like list, set, and dict have specific time complexities for various operations:
Operation
List
Dictionary
Set
Indexing
O (1)
N/A
N/A
Appending
O (1)
N/A
N/A
Insertion
O (n)
O (1)
O (1)
Searching
O (n)
O (1)
O (1)
Deleting
O (n)
O (1)
O (1)
Iteration
O (n)
O (n)
O (n)