Day 6: Introduction to Data Structures

Day 6: Introduction to Data Structures

Introduction to Data Structures

Definition and Importance of Data Structures

Data structures are a specific means of organizing and storing data in a computer so that it can be accessed and modified efficiently. They are one of the fundamental concepts in computer science and are the building blocks of any software or program.

Data structures enable the management and organization of data in different ways. This flexibility to manage data depending on one’s needs is central to solving complex problems. With the right data structure, your code will not only be efficient but also more organized and scalable.

As mentioned in the previous chapter, the importance of data structures cannot be overstated. They aid in efficient data organization and management, enhance performance by ensuring optimal utilization of resources, enable reusability and abstraction, and simplify complex problems by breaking them down into more manageable parts.

Different types of Data Structures in Python

Python comes with several built-in data structures. Each of these serves different purposes and has its own advantages and unique characteristics. They can be broadly classified into two categories: built-in data structures and user-defined data structures. Here’s a quick overview:

Built-in Data Structures:

• Lists: A list in Python is a collection of items that are ordered and changeable. Lists allow duplicate members and are useful for holding an ordered collection of items, such as all the students in a class or all the items in a shopping cart.
• Tuples: A tuple is a collection of items that is ordered but unchangeable. Tuples are useful when you have an ordered collection of items that shouldn’t be changed, like the months of the year, or the dates of public holidays.
• Sets: A set is an unordered collection of items where every element is unique (no duplicates). Sets are useful when you want to keep track of a collection of elements, but don’t care about their order, their frequency, or whether they’re repeated.
• Dictionaries: A dictionary in Python is an unordered collection of data values that are changeable and indexed. Unlike other data types that hold only single value as an element, dictionaries hold key:value pair. They are great for situations where you want to describe some data (like a card in a card game, a book in a library, or a product in a shopping cart).

User-Defined Data Structures:

• Arrays: Arrays are a collection of elements identified by array indices. They are used when we need to perform computations on a collection of the same data types.
• Stacks: A stack is a collection of elements, with two main operations: push, which adds to the collection, and pop, which removes the most recently added element.
• Queues: Like stacks, queues are a collection of elements. But, unlike stack, elements are added at one end and removed from the other – following the First-In-First-Out (FIFO) principle.
• Trees: A tree is a collection of elements (called nodes) that simulate a hierarchy in the real world. Each node in the tree has a value and possibly a set of children nodes.
• Graphs: Graphs are a more general structure than trees – one could actually describe trees as a special kind of graph. Graphs are collections of nodes with edges between (some of) them.
• Linked Lists: A linked list is a sequence of data structures, which are connected together via links. It is a data structure consisting of a collection of nodes which together represent a sequence.

These various data structures will be covered in detail in the subsequent days. Their thorough understanding and correct application will make you an effective Python programmer.

Basic Python Data Structures

Overview and Comparison: List, Tuple, Set, Dictionary

Python provides a variety of data structures to handle different programming scenarios. Today, we will briefly introduce four basic built-in data structures: List, Tuple, Set, and Dictionary. Each has unique characteristics and is used in different situations, so it’s essential to understand their differences and choose the right one for your specific task.

List

A list in Python is an ordered collection of items. The items can be of different types and are changeable, meaning we can add, remove, or change items after the list is created. Lists are defined by enclosing a comma-separated sequence of objects in square brackets [].

Example:

fruits = ['apple', 'banana', 'cherry']

Tuple

A tuple is similar to a list in that it is an ordered collection of items. The main difference is that tuples are immutable, meaning you cannot add, remove, or change items once the tuple is created. Tuples are defined by enclosing a comma-separated sequence of objects in parentheses ().

Example:

fruits = ('apple', 'banana', 'cherry')

Set

A set in Python is an unordered collection of unique items. Sets automatically remove duplicate values and can be used to perform mathematical set operations like union, intersection, difference, etc. They are created by enclosing a comma-separated sequence of objects in curly braces {} or by using the built-in set() function.

Example:

fruits = {'apple', 'banana', 'cherry'}

Dictionary

A dictionary in Python is an unordered collection of data in a key:value pair format. Each key is unique, and the values can be of any type. Dictionaries are mutable and are defined by enclosing a comma-separated sequence of key-value pairs in curly braces {}. The key-value pairs are separated by a colon :.

Example:

person = {'name': 'John', 'age': 30, 'city': 'New York'}

Comparison

The table below provides a quick comparison of these four data structures:

Remember, each data structure serves a particular purpose, and understanding these will help you write more efficient and readable code. In the coming days, we will delve deeper into each of these data structures.

Deep Dive – Lists in Python

Introduction to Lists

Defining and Creating Lists:

A list in Python is an ordered collection of items which are mutable, meaning they can be changed after their creation. Lists are defined by enclosing a comma-separated sequence of objects in square brackets [].

my_list = [1, 2, 3, 4, 5]
print(my_list)  # Output: [1, 2, 3, 4, 5]

Lists with Multiple Data Types:

Python lists can contain items of different data types. For instance, a list can contain a mix of integers, floats, strings, and even other lists.

my_list = [1, "two", 3.0, ["another", "list"]]
print(my_list)  # Output: [1, "two", 3.0, ["another", "list"]]

Basic Operations on Lists

Indexing:

Like strings, indexing operator [index] is used to access an item in a list. Remember that the indices start at 0.

my_list = ['apple', 'banana', 'cherry', 'date']
print(my_list[0])  # Output: 'apple'
print(my_list[2])  # Output: 'cherry'

Slicing:

Lists can be sliced to return a new list containing a subset of its items. List slicing is done by using the colon : operator.

my_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(my_list[2:6])  # Output: [2, 3, 4, 5]

Changing Elements:

Lists are mutable, so you can change their content without changing their identity.

my_list = ['apple', 'banana', 'cherry']
my_list[2] = 'date'
print(my_list)  # Output: ['apple', 'banana', 'date']

Adding Elements:

You can add one item to a list using the append() method or add several items using extend() method. The insert(i, x) method inserts an item x at a given position i.

my_list = ['apple', 'banana']
my_list.append('cherry')  # ['apple', 'banana', 'cherry']
my_list.extend(['date', 'elderberry'])  # ['apple', 'banana', 'cherry', 'date', 'elderberry']
my_list.insert(1, 'avocado')  # ['apple', 'avocado', 'banana', 'cherry', 'date', 'elderberry']

Deleting Elements:

You can remove items from a list using del, pop(), or remove(). del removes the item at a specific index. pop() removes and returns the last item unless an index is provided. remove() removes the first occurrence of a value.

my_list = ['apple', 'banana', 'cherry', 'date', 'elderberry']
del my_list[1]  # ['apple', 'cherry', 'date', 'elderberry']
my_list.pop()  # ['apple', 'cherry', 'date']
my_list.remove('apple')  # ['cherry', 'date']

Other List Methods:

count(x) returns the number of times x appears in the list.

sort() sorts the items. reverse() reverses the items.

my_list = [1, 1, 2, 3, 3, 3, 4, 5]
print(my_list.count(3))  # Output: 3
my_list.sort()  # sorts the list in ascending order
my_list.reverse()  # reverses the list

Iterating over Lists

Using For Loops with Lists:

A ‘for’ loop is used to iterate over a list. In each iteration, the value of the current item is assigned to the variable.

my_list = ['apple', 'banana', 'cherry']
for fruit in my_list:
    print(fruit)

List Comprehension:

List comprehension offers a shorter syntax when you want to create a new list based on the values of an existing list.

original_list = [1, 2, 3, 4, 5]
new_list = [x**2 for x in original_list]
print(new_list)  # Output: [1, 4, 9, 16, 25]

Lists and Memory

Memory Allocation in Lists:

Each time an element is added to a list, Python allocates new memory for it. When elements are deleted, Python frees the memory for other use.

Shallow and Deep Copy of Lists:

There are ways to create a new list using an existing one. A shallow copy creates a new list, but fills it with references to the original items. A deep copy creates a new list and fills it with copies of the items in the original list. Deep copy is used when you need to change elements in the new list without affecting the original list.

# shallow copy
original = [[1, 1], [2, 2], [3, 3]]
shallow = original[:]
shallow[1][0] = 'X'
print(original)  # Output: [[1, 1], ['X', 2], [3, 3]]

# deep copy
import copy
original = [[1, 1], [2, 2], [3, 3]]
deep = copy.deepcopy(original)
deep[1][0] = 'X'
print(original)  # Output: [[1, 1], [2, 2], [3, 3]]

The above information provides a basic but comprehensive understanding of lists in Python. As you practice more, you’ll get a stronger grip over these concepts. Happy coding!

Practical Application – Problem Solving with Lists

Examples and Practice Problems using Lists

Example 1: Calculate the average of numbers in a list

numbers = [2, 4, 6, 8, 10]
average = sum(numbers) / len(numbers)
print(average)  # Output: 6.0

Example 2: Find all the even numbers in a list

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_numbers = [num for num in numbers if num % 2 == 0]
print(even_numbers)  # Output: [2, 4, 6, 8, 10]

Practice Problem 1: Find the maximum and minimum number in a list

Practice Problem 2: Count the frequency of words in a list

Practice Problem 3: Remove all duplicates from a list

Common Mistakes and Pitfalls with Lists

Mutable List Default Arguments: In Python, default argument values are evaluated once when the function is defined, not each time the function is called. This can be problematic when using mutable objects like lists as default argument values.

def append_to(num, target=[]):
    target.append(num)
    return target

print(append_to(1))  # Output: [1]
print(append_to(2))  # Output: [1, 2], not [2] as you might expect!

To avoid this problem, you can use None as a default value and then initialize the list in the function body.

def append_to(num, target=None):
    if target is None:
        target = []
    target.append(num)
    return target

Modifying Lists While Iterating Over Them: It’s generally not a good idea to modify a list while iterating over it. This can lead to unexpected behavior and bugs.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in numbers:
    if i % 2 == 0:
        numbers.remove(i)  # Trying to remove even numbers
print(numbers)  # Output: [1, 3, 5, 7, 9], not [1, 3, 5, 7, 9, 10] as you might expect!

List Index Out of Range: This error occurs when you try to access an index that does not exist for the list. Remember, Python lists are zero-indexed, so the last index of a list will always be len(list) - 1.

numbers = [1, 2, 3, 4, 5]
print(numbers[5])  # Error: list index out of range, as the last index is 4

By being aware of these common mistakes and pitfalls, you can avoid them in your coding journey with Python. Practice with care and have fun coding!

Homework and Reading Assignments

Assignments and Practice Problems using Lists

1. Assignment 1: Write a Python function to multiply all the numbers in a list.
2. Assignment 2: Write a Python program to get a list, sorted in increasing order by the last element in each tuple from a given list of non-empty tuples.
3. Assignment 3: Write a Python function that takes two lists and returns True if they have at least one common member.

Practice Problems

1. Problem 1: Create a list of colors from comma-separated color names entered by the user. Display first and last colors.
2. Problem 2: Write a Python program to print a specified list after removing the 0th, 4th, and 5th elements.
3. Problem 3: Write a Python program that takes a list of words and counts the length of each one.

Reading Assignments: Introduction to Tuples (to prepare for Day 7)

To prepare for the next session, please read the following resources on tuples in Python. These readings will provide you with a foundational understanding of this data type.

1. “Tuples and Sequences” from Python Official Documentation: https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences
2. “Python Tuples” from W3Schools: https://www.w3schools.com/python/python_tuples.asp
3. “Python Tuples” from Geeks for Geeks: https://www.geeksforgeeks.org/tuples-in-python/

Self-paced Learning Resources

Suggested books, online resources, and tutorials for more practice

1. Books:
   • “Python Crash Course” by Eric Matthes: This book is a straightforward and beginner-friendly guide to learning Python with plenty of examples and exercises for practice.
   • “Automate The Boring Stuff With Python” by Al Sweigart: This book focuses on practical programming for total beginners and includes real-world applications.
2. Online Resources:
   • Codecademy’s Python Course: Codecademy offers interactive programming lessons in Python. Their hands-on approach involves writing lots of code and getting immediate feedback which makes it an excellent tool for beginners.
   • LeetCode’s Python Problems: This platform offers a plethora of programming challenges that you can solve using Python. These challenges range in difficulty from easy to hard, which makes it a great tool for practice.
   • Project Euler: Project Euler is a collection of challenging computational problems intended to be solved with computer programs, making it a great way to practice problem-solving skills in Python.
3. Tutorials:
   • Python.org Tutorial: This is a comprehensive tutorial on Python from the creators of the language. It’s a bit dense but incredibly thorough.
   • W3Schools Python Tutorial: This tutorial is more beginner-friendly, with lots of examples and exercises you can try out directly in your browser.
   • Real Python: Real Python provides a variety of tutorials and articles on different aspects of Python programming, from beginner to advanced topics.

Remember, the key to mastering Python, or any new skill, is consistent practice and persistence. Make use of these resources, and you’ll see steady progress in your Python journey.