Introduction to Python Data Structures

Overview of Python Data Structures

Python offers a variety of built-in data structures that are flexible and easy to use. They are critical for holding and manipulating data in your programs. Let's explore the most common ones:

• Lists: Ordered collections of items that can be of mixed types. Lists are mutable, allowing modification.
• Tuples: Similar to lists, but immutable. Once created, the contents cannot be changed.
• Dictionaries: Unordered collections of key-value pairs. Keys are unique, and the dictionary allows for fast retrieval based on the key.
• Sets: Unordered collections of unique elements. They are useful for operations like union, intersection, difference, and symmetric difference.

The Importance of Data Structures in Programming

Data structures are essential for organizing and storing data efficiently. They allow for data to be manipulated efficiently, enabling algorithms to perform tasks like searching and sorting more quickly. The choice of data structure can significantly affect the performance of a program.

Brief Comparison with Data Structures in Other Programming Languages

While Python's data structures are known for their ease of use and flexibility, other languages offer similar constructs with some differences in syntax and functionality. For example:

• In Java, arrays are fixed in size, while Python lists are dynamic.
• C++ provides a rich library of template classes in the Standard Template Library (STL), including vectors (similar to Python lists) and maps (similar to Python dictionaries), but with more explicit type definitions required.
• JavaScript objects can be used similarly to Python dictionaries, but they lack the comprehensive standard library support Python offers for complex data manipulation.

‍

In this section of your Jupyter Notebook, you'll dive into Python lists, covering creation, manipulation, and advanced features like list comprehensions. Lists are versatile and widely used in Python programming for storing sequences of items. Here’s how you can structure this part:

Lists in Python

Lists are ordered collections of items that can be of any type. They are mutable, meaning the contents can be changed after creation. Let’s explore how to work with lists.

Creation, Indexing, and Slicing

Creating a List

Lists are created by placing elements inside square brackets [], separated by commas.

my_list = [1, "Hello", 3.14]
print(my_list)

‍


Indexing

You can access an item in a list by referring to its position within square brackets. Remember, indexing in Python starts at 0.

# Access the first item
print(my_list[0])  # Output: 1
# Access the last item
print(my_list[-1]) # Output: 3.14

Slicing

Slicing allows you to get a subset of the list by specifying a range [start:stop:step].

numbers = [0, 1, 2, 3, 4, 5]
# Get items from index 1 to 4
print(numbers[1:5])  # Output: [1, 2, 3, 4]
# Get items from the beginning to index 3
print(numbers[:4])   # Output: [0, 1, 2, 3]
# Get items from index 2 to the end
print(numbers[2:])   # Output: [2, 3, 4, 5]

Methods

Lists provide various methods for manipulating their contents:

• append(): Adds an item to the end.
• remove(): Removes the first occurrence of an item.
• sort(): Sorts the list in ascending order by default.

# Append
my_list.append('Python')
print(my_list)  # Output: [1, "Hello", 3.14, 'Python']

# Remove
my_list.remove('Hello')
print(my_list)  # Output: [1, 3.14, 'Python']

# Sort
numbers.sort()
print(numbers)  # Output: [0, 1, 2, 3, 4, 5]

‍

List Comprehensions

List comprehensions provide a concise way to create lists. Common applications are to make new lists where each element is the result of some operation applied to each member of another sequence or iterable.

# Squares of numbers from 0 to 4
squares = [x ** 2 for x in range(5)]
print(squares)  # Output: [0, 1, 4, 9, 16]

Use Cases and Examples

Lists are incredibly versatile and can be used in a wide array of situations:

1. Storing a collection of items (e.g., names of students, items in an inventory).
2. Data analysis (e.g., storing and manipulating a dataset for statistical analysis).
3. Stack implementation (using append and pop methods to add/remove items).
4. Queue implementation (using append and pop(0) or using collections.deque for efficiency).
5. Matrix representation (using nested lists to represent rows and columns).

Examples:

# Example 1: Storing different types of items
misc_items = ['pencil', 3, [1, 2, 3], {'key': 'value'}]

# Example 2: Data analysis (simplified)
temperatures = [22.1, 23.4, 21.6, 24.1]
average_temp = sum(temperatures) / len(temperatures)
print(f'Average Temperature: {average_temp}')

# Example 3: Stack implementation
stack = []
stack.append('A')
stack.append('B')
stack.pop()  # Removes 'B'
print(stack)  # Output: ['A']

# Example 4: Queue implementation using deque
from collections import deque
queue = deque(['A', 'B', 'C'])
queue.append('D')
queue.popleft()  # Removes 'A'
print(list(queue))  # Output: ['B', 'C', 'D']

# Example 5: Matrix representation
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix[1][2])  # Accessing row 2, column 3; Output: 6

Lists are a fundamental data structure in Python, suitable for a broad range of programming and data manipulation tasks

In the next section of your Jupyter Notebook, you'll focus on tuples in Python. Tuples are similar to lists in that they are used to store collections of items. However, they have key differences, such as immutability, which makes them a crucial part of Python programming. Here's how you could structure the section on tuples:

Tuples in Python

Tuples are ordered collections of items, similar to lists. The main difference is that tuples are immutable, meaning once a tuple is created, its contents cannot be changed. This section will cover how to create and use tuples, the concept of immutability, and tuple packing and unpacking.

Creation and Usage

Creating a Tuple

Tuples are created by placing elements inside parentheses (), separated by commas. It's the commas that define the tuple, not the parentheses. Parentheses are optional for tuples with more than one element.

my_tuple = (1, "Hello", 3.14)
print(my_tuple)

# A single-element tuple needs a comma after the item
single_element_tuple = (42,)
print(single_element_tuple)

# Parentheses are optional
another_tuple = 1, 2, 3
print(another_tuple)

‍


Accessing Tuple Elements

Tuple elements can be accessed in the same way as lists, through indexing.

# Access the second item
print(my_tuple[1])  # Output: "Hello"

Immutability Concept

Unlike lists, tuples are immutable, which means you cannot add, remove, or change elements after the tuple is created. This immutability makes tuples useful as fixed collections of items and can offer performance benefits.

# Trying to change a tuple's item results in an error
# my_tuple[1] = "World"  # Uncommenting this line will raise a TypeError

Tuple Packing and Unpacking

Packing

Packing refers to the process of creating a tuple without using parentheses, where the items are packed into a tuple.

packed_tuple = 1, 2, "pack"
print(packed_tuple)

‍‍Unpacking

Unpacking allows you to assign the values from a tuple into variables in a single statement.

a, b, c = packed_tuple
print(a)  # Output: 1
print(b)  # Output: 2
print(c)  # Output: "pack"

Use Cases and Examples

Tuples are widely used in Python for various reasons:

1. Function arguments and return values: Functions can use tuples to return multiple values.
2. Unchangeable records: Use tuples when you need an ordered collection of items that should not change.
3. Dictionary keys: Tuples can be used as keys in dictionaries, provided all the elements of the tuple are immutable.
4. Looping through multiple lists simultaneously with the zip() function, which pairs elements from lists into tuples.

Examples:

# Example 1: Function returning multiple values
def min_max(numbers):
    return min(numbers), max(numbers)  # Returns a tuple
result = min_max([1, 2, 3, 4, 5])
print(result)  # Output: (1, 5)

# Example 2: Unchangeable records
person_info = ('John', 'Doe', 30)
print(person_info)

# Example 3: Using a tuple as a dictionary key
coordinates = {(35.6895, 139.6917): "Tokyo Tower"}
print(coordinates[(35.6895, 139.6917)])

# Example 4: Looping with zip
names = ["Anna", "Bob", "Charlie"]
ages = [24, 30, 18]
for name, age in zip(names, ages):
    print(f"{name} is {age} years old")

Tuples provide a way to create collections of items in Python that cannot be modified after their creation, ensuring data integrity and improving code readability and performance in specific scenarios.

Dictionaries in Python

Dictionaries are unordered collections of items. Each item in a dictionary is stored as a key-value pair. This makes dictionaries ideal for storing data that can be easily retrieved by a unique key. In Python, dictionaries are mutable, meaning you can add, remove, or modify items after the dictionary has been created.

Creating and Accessing Dictionaries

Creating a Dictionary

Dictionaries are defined within curly braces {}, with key-value pairs separated by colons : and items separated by commas.

my_dict = {'name': 'John', 'age': 30, 'city': 'New York'}
print(my_dict)

‍


Accessing Dictionary Values

Values are accessed by their key using square brackets [] or the get method, which returns None instead of an error if the key doesn't exist.

# Using square brackets
print(my_dict['name'])  # Output: John

# Using get method
print(my_dict.get('age'))  # Output: 30

‍

‍

Methods

Dictionaries provide a variety of methods for manipulation and access:

• keys(): Returns a view object containing the keys of the dictionary.
• values(): Returns a view object containing the values of the dictionary.
• items(): Returns a view object with tuples of key-value pairs.
• update(): Updates the dictionary with elements from another dictionary or from an iterable of key-value pairs.

# keys method
print(my_dict.keys())  # Output: dict_keys(['name', 'age', 'city'])

# values method
print(my_dict.values())  # Output: dict_values(['John', 30, 'New York'])

# items method
print(my_dict.items())  # Output: dict_items([('name', 'John'), ('age', 30), ('city', 'New York')])

# update method
my_dict.update({'country': 'USA', 'age': 31})
print(my_dict)

Dictionary Comprehensions

Dictionary comprehensions provide a concise way to create dictionaries from iterables.

# Squares of numbers using dictionary comprehension
squares = {x: x**2 for x in range(6)}
print(squares)

Use Cases and Examples

Dictionaries are versatile and can be used in numerous scenarios:

1. Storing data about objects or entities (e.g., storing user information).
2. Counting items (e.g., counting the occurrences of words in a text).
3. Caching results (e.g., memoization in recursive functions).
4. Configurations (e.g., settings for an application).
5. Building complex data structures (e.g., graphs represented as adjacency lists).

Examples:

# Example 1: Storing user information
user_profile = {
    'username': 'johndoe',
    'email': 'john@example.com',
    'location': 'New York',
    'verified': True
}
print(user_profile)

# Example 2: Counting word occurrences
words = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
word_count = {}
for word in words:
    word_count[word] = word_count.get(word, 0) + 1
print(word_count)

# Example 3: Caching with memoization
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))

# Example 4: Configuration settings
config = {
    'theme': 'dark',
    'notifications': True,
    'login_remember_me': False
}
print(config)

Dictionaries are a fundamental data structure in Python, offering fast, flexible, and powerful options for data management and manipulation.

Sets in Python

Sets are collections of unordered, unique items. They are mutable, allowing the addition and removal of items, and are particularly useful for mathematical set operations.

Set Creation and Basic Operations

Creating a Set

Sets are created by placing elements inside curly braces {} or by using the set() constructor. Note that to create an empty set, you must use set(), as {} creates an empty dictionary.

my_set = {1, 2, 3}
print(my_set)

# Using set() constructor
empty_set = set()
print(empty_set)  # Output: set()

Basic Set Operations

• Addition: Use the add() method to add an element to a set.
• Removal: Use the remove() or discard() methods to remove elements. The remove() method raises a KeyError if the element is not found, whereas discard() does not.

# Addition
my_set.add(4)
print(my_set)  # Output: {1, 2, 3, 4}

# Removal
my_set.remove(2)
print(my_set)  # Output: {1, 3, 4}
my_set.discard(5)  # Does not raise an error

• Union: Combines elements from two sets without duplicates.
• Intersection: Finds elements common to both sets.
• Difference: Finds elements in the first set but not in the second.

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

# Union
print(a | b)  # Output: {1, 2, 3, 4, 5, 6}

# Intersection
print(a & b)  # Output: {3, 4}

# Difference
print(a - b)  # Output: {1, 2}

Set Comprehensions

Set comprehensions allow sets to be constructed using an existing iterable.

squared = {x**2 for x in range(10)}
print(squared)

‍

‍


Use Cases and Examples

Sets are useful in various scenarios, especially when dealing with unique collections of items:

1. Removing duplicates: Easily remove duplicate elements from a list or another collection.
2. Membership testing: Quickly test for the presence of an element in a collection.
3. Mathematical operations: Perform union, intersection, difference, and symmetric difference operations for analysis and data processing.
4. Data filtering: Filter out unwanted data based on certain criteria.

Examples:

# Example 1: Removing duplicates from a list
numbers = [1, 2, 2, 3, 4, 4, 5]
unique_numbers = set(numbers)
print(unique_numbers)  # Output: {1, 2, 3, 4, 5}

# Example 2: Membership testing
print(1 in unique_numbers)  # Output: True

# Example 3: Mathematical operations
a = {1, 2, 3}
b = {2, 3, 4}
print(a.union(b))  # Output: {1, 2, 3, 4}

# Example 4: Data filtering
data = {1, 2, 3, 4, 5, 6}
filtered_data = {x for x in data if x > 3}
print(filtered_data)  # Output: {4, 5, 6}

Sets offer a unique combination of functionality and performance for certain types of operations and should be considered an essential part of the Python programmer's toolkit.

Intermediate Data Structures

Stacks and Queues

Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The last element added to the stack is the first one to be removed.

Implementation using Lists

In Python, lists can be used as stacks. You can use the append() method to push an item onto the stack and the pop() method to remove an item.

stack = []
# Push items onto the stack
stack.append('A')
stack.append('B')
stack.append('C')
print(stack)  # Output: ['A', 'B', 'C']

# Pop an item off the stack
stack.pop()
print(stack)  # Output: ['A', 'B'

Applications

• Function call management in programming languages.
• Undo mechanisms in text editors.
• Syntax parsing in compilers.

Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The first element added is the first element to be removed.

Implementation using Lists

While you can use lists to implement queues by using append() to enqueue and pop(0) to dequeue, this is inefficient due to the O(n) time complexity for pop(0). A better alternative is to use collections.deque.

from collections import deque

queue = deque()
# Enqueue items
queue.append('A')
queue.append('B')
queue.append('C')
print(list(queue))  # Output: ['A', 'B', 'C']

# Dequeue an item
queue.popleft()
print(list(queue))  # Output: ['B', 'C']

Applications

• Managing tasks in operating systems.
• Handling of interrupts in real-time systems.
• Queueing systems for load balancing.

Strings

Strings in Python are sequences of characters. They are immutable, meaning once a string is created, it cannot be modified.

String Manipulation and Operations

You can concatenate strings using +, access characters by indexing, and slice strings using :

# Concatenation
hello_world = "Hello" + " " + "World"
print(hello_world)  # Output: "Hello World"

# Indexing
print(hello_world[0])  # Output: 'H'

# Slicing
print(hello_world[:5])  # Output: 'Hello'

String Formatting and Methods

Python provides multiple ways to format strings, including the format() method, f-strings (formatted string literals), and more.

# Using format()
formatted_string = "{} {}!".format("Hello", "World")
print(formatted_string)  # Output: "Hello World!"

# Using f-strings
name = "Python"
formatted_string = f"Hello, {name}!"
print(formatted_string)  # Output: "Hello, Python!"

Strings have a variety of methods for case conversion, trimming, splitting, and joining.

s = " hello, world! "
print(s.strip())  # Output: "hello, world!"
print(s.upper())  # Output: " HELLO, WORLD! "
print(s.split(','))  # Output: [' hello', ' world! ']
print(','.join(['A', 'B', 'C']))  # Output: 'A,B,C'

Applications

• User input processing.
• File and network operations.
• Data parsing and formatting.

This section introduces students to more complex data structures and their applications, with stacks, queues, and strings serving as the foundation for understanding more advanced concepts later on.

Excercises

Lists

1. Rotate a List: Write a function that rotates a list by k elements. For example, [1, 2, 3, 4, 5] rotated by 2 becomes [4, 5, 1, 2, 3].
2. Merge and Sort: Given two lists, write a program that merges them and sorts the result.
3. Find Missing Number: Given a list of numbers from 1 to n with one number missing, write a function to find that missing number.

Dictionaries

1. Invert a Dictionary: Write a function that inverts a dictionary, swapping keys and values. Assume all values are unique.
2. Count Character Occurrences: Given a string, write a function that counts the occurrence of each character and stores the counts in a dictionary.
3. Merge Dictionaries: Write a function that merges two dictionaries. If there is a conflict, the value from the second dictionary should be used.

Tuples

1. Swap Values: Write a function that swaps the values of two tuples.
2. Calculate Distance: Given two tuples representing points in a 2D plane (x1, y1) and (x2, y2), write a function to calculate the Euclidean distance between them.
3. Tuple List Sorting: Given a list of tuples where each tuple contains a name and a score, write a function to sort the list by scores in descending order.

Sets

1. Unique Elements in Lists: Given two lists, write a program that prints out all elements that are unique to each list.
2. Common Elements: Write a function that finds the common elements between three sets and returns them as a new set.
3. Set Operations: Given two sets, write a program that prints the results of union, intersection, difference, and symmetric difference.

Strings

1. Palindrome Checker: Write a function that checks whether a given string is a palindrome (reads the same backward as forward, ignoring spaces, punctuation, and case).
2. Word Frequencies: Given a long string of text, write a function to count how many times each word appears. Ignore punctuation and case differences.
3. Anagram Checker: Write a function that checks whether two strings are anagrams of each other (contain the same letters in a different order).

Mixed

1. Data Structure Conversion: Write a function that converts a list of dictionaries into a dictionary of lists, grouping by a specific key/value pair found in the original dictionaries.
2. Inventory Update: Given a list of items (a mix of tuples and lists) representing an inventory (where each sub-list/tuple contains an item name and quantity), write a function to update the inventory based on a new list of updates (also items with quantities). The result should be a single merged and sorted list by item name.
3. String Compression: Implement a function to perform basic string compression using counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your function should return the original string.

These exercises provide a broad spectrum of challenges that encourage students to apply their knowledge of Python's data structures in various scenarios, enhancing their problem-solving skills.

[ ]:

list exercises solution:

1. Rotate a List

This function rotates a list by k elements to the right. If you need to rotate to the left, you can adjust the slicing accordingly.

def rotate_list(lst, k):
    n = len(lst)
    k = k % n  # To handle cases where k > n
    return lst[-k:] + lst[:-k]

# Example usage
print(rotate_list([1, 2, 3, 4, 5], 2))  # Output: [4, 5, 1, 2, 3]

2. Merge and Sort

This program merges two lists and sorts the resulting list. It demonstrates simple list operations and the use of the sorted() function.

def merge_and_sort(list1, list2):
    return sorted(list1 + list2)

# Example usage
print(merge_and_sort([1, 4, 6], [2, 3, 5]))  # Output: [1, 2, 3, 4, 5, 6]

3. Find Missing Number

This function finds the missing number in a list of numbers from 1 to n. The approach uses the formula for the sum of the first n natural numbers to find the missing number by subtracting the sum of the array from the expected sum.

def find_missing_number(lst):
    n = len(lst) + 1  # Since one number is missing
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(lst)
    return expected_sum - actual_sum

# Example usage
print(find_missing_number([1, 2, 4, 5, 6]))  # Output: 3

These functions showcase basic yet powerful list operations in Python, useful for a wide range of programming tasks.

‍

dictionary exercises solution

1. Invert a Dictionary

This function inverts a dictionary, assuming all values are unique and can thus be used as keys in the inverted dictionary.

def invert_dict(d):
    return {value: key for key, value in d.items()}

# Example usage
my_dict = {'a': 1, 'b': 2, 'c': 3}
print(invert_dict(my_dict))  # Output: {1: 'a', 2: 'b', 3: 'c'}

2. Count Character Occurrences

This function counts the occurrences of each character in a string and stores the counts in a dictionary. It's a common pattern for frequency counting.

def count_character_occurrences(s):
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    return counts

# Example usage
print(count_character_occurrences("hello world"))  # Output: {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

3. Merge Dictionaries

This function merges two dictionaries. In case of key conflicts, the value from the second dictionary is used. This makes use of the ** operator for dictionaries introduced in Python 3.5+.

def merge_dictionaries(dict1, dict2):
    return {**dict1, **dict2}

# Example usage
dict1 = {'a': 1, 'b': 2}
dict2 = {'b': 3, 'c': 4}
print(merge_dictionaries(dict1, dict2))  # Output: {'a': 1, 'b': 3, 'c': 4}

These exercises and solutions provide practical examples of how to manipulate and utilize dictionaries in Python, showcasing their versatility and efficiency in handling data.

tuple exercises solution

1. Swap Values

This function swaps the values of two tuples by making use of Python's ability to return multiple values from a function, effectively swapping the tuples.

def swap_tuples(tuple1, tuple2):
    return tuple2, tuple1

# Example usage
tuple1 = (1, 2)
tuple2 = (3, 4)
tuple1, tuple2 = swap_tuples(tuple1, tuple2)
print("Tuple1:", tuple1, "Tuple2:", tuple2)  # Output: Tuple1: (3, 4) Tuple2: (1, 2)

2. Calculate Distance

This function calculates the Euclidean distance between two points in a 2D plane represented by tuples (x1, y1) and (x2, y2).

def calculate_distance(point1, point2):
    return ((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2) ** 0.5

# Example usage
point1 = (1, 2)
point2 = (4, 6)
print(calculate_distance(point1, point2))  # Output: 5.0

3. Tuple List Sorting

This function sorts a list of tuples by the scores in descending order. Each tuple contains a name and a score. The sorted() function is used with a lambda function as the key to specify sorting based on the second item of each tuple.

def sort_tuples_by_score(tuple_list):
    return sorted(tuple_list, key=lambda x: x[1], reverse=True)

# Example usage
players = [("Alice", 10), ("Bob", 8), ("Cindy", 11)]
print(sort_tuples_by_score(players))  # Output: [('Cindy', 11), ('Alice', 10), ('Bob', 8)]

These exercises and their solutions offer a practical look into working with tuples in Python, showcasing their immutability, utility in representing data, and their ability to be used in conjunction with Python's powerful built-in functions for sorting and mathematical calculations.

‍

string exercises solutions

1. Palindrome Checker

This function checks whether a given string is a palindrome, considering only alphanumeric characters and ignoring cases.

import re

def is_palindrome(s):
    cleaned = re.sub(r'[\W_]+', '', s.lower())
    return cleaned == cleaned[::-1]

# Example usage
print(is_palindrome("A man, a plan, a canal: Panama"))  # Output: True
print(is_palindrome("Not a palindrome"))  # Output: False

2. Word Frequencies

This function counts how many times each word appears in a given string, ignoring punctuation and case differences. It splits the string into words based on spaces and punctuation using a regular expression.

from collections import Counter
import re

def word_frequencies(s):
    words = re.findall(r'\b\w+\b', s.lower())
    return Counter(words)

# Example usage
text = "This is a test. This test is only a test."
print(word_frequencies(text))  # Output: Counter({'this': 2, 'is': 2, 'a': 2, 'test': 3, 'only': 1})

3. Anagram Checker

This function checks whether two strings are anagrams of each other. It compares sorted versions of the strings (after removing all non-alphanumeric characters and converting to lower case) to determine if they are anagrams.

def are_anagrams(s1, s2):
    format_str = lambda s: sorted(re.sub(r'[\W_]+', '', s.lower()))
    return format_str(s1) == format_str(s2)

# Example usage
print(are_anagrams("Listen", "Silent"))  # Output: True
print(are_anagrams("Hello", "World"))    # Output: False

These exercises and solutions provide a comprehensive look at common string manipulation tasks in Python, demonstrating the language's robust support for handling text data through its standard library functions and regular expressions.

‍