Class 4: Data Structures

In this class, we will review some of the built-in data structures in Python and then move on to working with arrays and matrices. We will then look at creating and using custom data structures before ending with a practice exercise to implement a hash table data structure in Python.

Photo by Claudio Schwarz on Unsplash

Review of built-in data structures

Python provides several built-in data structures that are widely used in programming. These include lists, tuples, sets, and dictionaries.

Lists are mutable ordered sequences of elements. They can contain any type of element and can be modified by adding or removing elements.

Tuples are immutable ordered sequences of elements. They are similar to lists but cannot be modified once created.

Sets are unordered collections of unique elements. They can be used for operations such as union, intersection, and difference.

Dictionaries are unordered collections of key-value pairs. They are used to store and retrieve data based on keys rather than indices.

Working with arrays and matrices

Arrays and matrices are important data structures in scientific computing and data analysis. In Python, we can work with arrays and matrices using the NumPy library.

NumPy provides a multidimensional array object that can be used to store and manipulate large arrays of numerical data efficiently. NumPy arrays are homogeneous and can contain only elements of the same data type.

Creating and using custom data structures

In addition to the built-in data structures in Python, we can also create and use our own custom data structures. These can be used to represent complex data types and can be tailored to meet specific requirements.

To create a custom data structure in Python, we can define a new class that encapsulates the required data and operations. The class can then be instantiated to create new instances of the data structure.

Practice: Implement a hash table data structure in Python

A hash table is a data structure that allows you to store and retrieve values based on a key. The hash table works by computing the hash of the key, which is an integer value that represents the key. This integer value is then used as an index into an array, which contains the values associated with the keys.

To implement a hash table in Python, you can start by creating a class for the hash table that initializes an array with a fixed size. The size of the array will depend on the number of elements you plan to store in the hash table.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

Next, you need to define a hash function that computes the hash of a given key. There are many ways to implement a hash function, but one common method is to use the built-in hash() function in Python and then apply a modulo operation to limit the result to the range of indices in the array.

def hash_func(self, key):
    return hash(key) % self.size

With the hash function defined, you can now add a method to the HashTable class to insert a key-value pair into the table. This method first computes the hash of the key, then uses that index to access the corresponding entry in the array. If the entry is None, it creates a new linked list to hold the key-value pairs. Otherwise, it searches the linked list for the key and updates the value if it already exists, or adds a new node to the end of the list if it does not.

def insert(self, key, value):
    index = self.hash_func(key)
    if self.table[index] is None:
        self.table[index] = LinkedList()
    node = self.table[index].find(key)
    if node is None:
        self.table[index].append(key, value)
    else:
        node.value = value

The LinkedList class is another custom data structure that you will need to define for this implementation. It should support basic operations like adding nodes to the end of the list, searching for a node with a given key, and updating the value of a node.

Finally, you can add a method to the HashTable class to retrieve a value based on a key. This method also computes the hash of the key to find the index in the array, and then searches the linked list at that index for the key.

def get(self, key):
    index = self.hash_func(key)
    if self.table[index] is None:
        return None
    node = self.table[index].find(key)
    if node is None:
        return None
    else:
        return node.value

Overall, implementing a hash table in Python can be a challenging but rewarding exercise in data structures and algorithms. With this implementation, you can store and retrieve key-value pairs efficiently, making it a useful tool for many applications.