Computer Science (9645) | Dictionaries

📚 Advanced Data Structures: Dictionaries (9645) 📚

Welcome to the final chapter in our look at common data structures! You’ve already mastered linear structures like Arrays, Lists, Queues, and Stacks. These structures are great when order matters, or when you access data based on its position (index).

But what if you want to store information and look it up based on its *name* or *label*, rather than its position? That’s where the power of the Dictionary comes in. By the end of these notes, you’ll understand this unique, highly efficient data structure used everywhere in modern programming.

---

1. Understanding the Concept of a Dictionary

A dictionary, sometimes called an associative array, a map, or a hash map in other programming contexts, is a fundamental data structure for storing data that needs fast retrieval using a unique identifier.

The core concept of a dictionary, as defined in the syllabus, is:

A collection of key-value pairs in which the value is accessed via the associated key.

The Phonebook Analogy

Imagine your phone’s contact list:

• If you want to call "Sarah," you don't scroll through every number looking for Sarah's contact details.
• You instantly look up "Sarah."

In this analogy:

• The name "Sarah" is the Key.
• Sarah's phone number (and address, email, etc.) is the Value.

You use the unique, descriptive key (the name) to immediately find the associated data (the number).

Key Terms in a Dictionary

A dictionary is composed of pairs, where each pair contains two elements:

➤ The Key (The Identifier)

The Key is the unique label or index used to look up the data. Think of it as the address.

• Keys must be unique: You cannot have two identical keys in the same dictionary (otherwise, how would the system know which value to retrieve?).
• Keys should be immutable: They generally cannot be changed once created (e.g., a number, a string, or an ID).

➤ The Value (The Data)

The Value is the actual data you want to store and retrieve. Think of it as the information stored at that address.

• Values do not need to be unique: Many keys can point to the same value (e.g., three different students could all have the same grade of 'A').
• Values can be mutable: They can be changed or updated after they are stored.

Did you know? The underlying mechanism that allows dictionaries to retrieve values so quickly from keys often involves a mathematical technique called hashing (which you might study in more detail later if covering Hash Tables!).

---

2. Simple Applications of Dictionaries (3.10.5 Content)

Dictionaries are used whenever there is a need to map one piece of information directly to another. Here are some simple, common applications:

1. Storing Configuration Settings

When software needs to remember settings (like a game's volume level, or a website's default language), dictionaries are ideal.

Example: A game configuration dictionary might look like this:

• Key: 'Volume', Value: 85
• Key: 'Resolution', Value: '1920x1080'
• Key: 'Language', Value: 'English'

2. Mapping Identifiers to Records

If you have large datasets, you need a quick way to find a specific record using a unique ID, rather than searching through the whole list.

Example: Storing student data:

• Key: 'Student_ID_901', Value: {Name: 'Liam', Grade: 'A'}
• Key: 'Student_ID_902', Value: {Name: 'Zoe', Grade: 'B'}

3. Frequency Counting

Dictionaries are fantastic for counting how often something appears (like counting words in a text). The item itself becomes the key, and its count becomes the value.

• Key: 'Apple', Value: 5
• Key: 'Banana', Value: 12

4. Implementing Look-Up Tables

If you need to instantly convert one code or term into another, a dictionary acts as a perfect look-up table.

Example: Converting country codes to full names:

• Key: 'UK', Value: 'United Kingdom'
• Key: 'FR', Value: 'France'

---

3. Using Programming Language Libraries (3.10.5 Content)

In most modern programming languages (like Python, C#, or Java), the dictionary data structure is provided as a built-in type or through a standard library. You are expected to have experience using a programming language library that implements this structure.

Don’t worry if the specific code syntax is different across languages; the fundamental operations remain the same:

Basic Dictionary Operations

1. Inserting (Adding) a Key-Value Pair

This operation adds a new unique key and its associated value to the dictionary.

Analogy: Adding a new contact to your phonebook.

2. Retrieving (Looking Up) a Value

This is the most common and important operation. You provide the key and the dictionary returns the corresponding value.

Analogy: Searching for "Sarah" to get her number.

3. Updating a Value

If the key already exists, you can assign a new value to it. The key remains the same, but the information it points to is changed.

Analogy: Changing Sarah's phone number to a new one.

4. Deleting a Key-Value Pair

This removes both the key and its associated value entirely from the structure.

Analogy: Deleting a contact from your phonebook.

⚠ Common Pitfall to Avoid

A frequent error is trying to retrieve a value using a key that does not exist in the dictionary. This usually results in a runtime error (like a KeyError in Python). You must ensure the key exists before trying to access its value directly.

---

Summary of Dictionaries

Dictionaries are a powerful tool in advanced data structures because they offer incredibly fast look-up times by replacing numerical positional indexing with descriptive, unique keys. They are essential for modeling real-world data where items are identified by names, IDs, or labels.

Key Concepts to Remember:

• A dictionary stores data as key-value pairs.
• The Key is used for access and must be unique.
• Applications include configuration, data mapping, and look-up tables.
• You interact with dictionaries using standard library functions for inserting, retrieving, updating, and deleting data.

Keep practising these operations in your chosen programming language to solidify your understanding. Good luck!