Phone Directory 📞📅

Welcome to our comprehensive guide on Data Structures and Algorithms, where we delve into the world of a Phone Directory! This guide is perfect for both beginners and intermediates, and we'll explain concepts from the ground up. Let's get started!

Introduction 🎯

In this lesson, we'll discuss a practical application of Data Structures and Algorithms: designing a Phone Directory. By the end of this lesson, you'll understand the importance of efficient data structures for managing large amounts of data, and you'll learn about algorithms to quickly search for contacts in your directory.

Data Structures for Phone Directory 📝

Arrays 📦

An Array is a collection of items stored at contiguous memory locations. It's perfect for storing a list of contacts in our Phone Directory.

python

contacts = ["John Doe", "Jane Smith", "Michael Brown"]

💡 Pro Tip: Arrays are efficient when it comes to accessing elements by their index. However, searching for a specific contact can be slow if the array is large.

Hash Maps (or Dictionaries) 📓

A Hash Map (or Dictionary) is a data structure that stores key-value pairs. In our Phone Directory, we can use it to store each contact's name as a key and their phone number as a value.

python

phonebook = {
    "John Doe": "555-1234",
    "Jane Smith": "555-5678",
    "Michael Brown": "555-9012"
}

💡 Pro Tip: Hash Maps are excellent for quickly finding a contact by their name since we can use the key to access the corresponding value.

Algorithms for Phone Directory 📝

Linear Search 🔍

Linear Search is a simple algorithm for finding a specific contact in an Array. It works by iterating through the Array and comparing each contact with the target contact.

python

def linear_search(contacts, target):
    for contact in contacts:
        if contact == target:
            return True
    return False

💡 Pro Tip: Linear Search is straightforward, but inefficient when searching through large Arrays.

Binary Search 🔎

Binary Search is a more efficient algorithm for finding a specific contact in a sorted Array. It works by repeatedly dividing the Array in half until we find the target contact.

python

def binary_search(contacts, target):
    low = 0
    high = len(contacts) - 1
    mid = (low + high) // 2

    while low <= high:
        if contacts[mid] == target:
            return True
        elif contacts[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return False

💡 Pro Tip: Binary Search is much faster than Linear Search for large Arrays, but it requires the Array to be sorted.

Hash Map Search 🔍

We can use a Hash Map to find a specific contact by their name. Since the Hash Map stores contacts as key-value pairs, we can quickly find a contact by their name (the key).

python

def find_contact(phonebook, name):
    return phonebook.get(name, None)

💡 Pro Tip: Hash Map Search is extremely fast since it only requires a constant time to find a contact by their name.

Putting it all together 🔄

Now that we've discussed data structures and algorithms for a Phone Directory, let's put it all together in a complete application!

python

def main():
    contacts = ["John Doe", "Jane Smith", "Michael Brown"]
    phonebook = {
        "John Doe": "555-1234",
        "Jane Smith": "555-5678",
        "Michael Brown": "555-9012"
    }

    name = input("Enter a contact's name: ")

    if linear_search(contacts, name):
        print(f"Found {name} in the contacts list.")

    if name in phonebook:
        print(f"{name}'s phone number is {phonebook[name]}.")

    if not linear_search(contacts, name) and name not in phonebook:
        print(f"Could not find {name}.")

if __name__ == "__main__":
    main()

💡 Pro Tip: This application demonstrates the use of both Arrays and Hash Maps, as well as Linear Search and Hash Map Search.

Challenge 🏋️‍♂️

Modify the application to allow the user to add a new contact and their phone number to the phonebook.

:::quiz Question: Modify the application to allow the user to add a new contact and their phone number to the phonebook. A: Modify the phonebook variable to be a mutable data structure, and provide a function for adding new contacts and phone numbers. B: Modify the contacts variable to be a mutable data structure, and provide a function for adding new contacts. C: Modify the phonebook variable to be a mutable data structure, and provide a function for adding new contacts and phone numbers that updates both contacts and phonebook. Correct: C Explanation: To add a new contact and their phone number, we need to update both the contacts Array and the phonebook Hash Map.