.jpg)
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-elseApply 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] = 10Comprehension 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 ScenariosWhen 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, anddicthave 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)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)