GCSE Link: None

A dictionary is a collection of key-value pairs where each value can be retrieved using the associated key.

Dictionaries are usually written like this: {key1: val1, key2: val2, key3: val3}

They can be implemented either as a static or dynamic data type, with two arrays/lists storing the keys and values.

Example 1 shows some example pseudo-code to initialise a dictionary (implemented here dynamically using two lists).

Example 1
SUBROUTINE Initialise()
  this.keys = []
  this.vals = []
ENDSUBROUTINE

To add a key-value pair to the dictionary, we can do a linear search to check if the key is already in the dictionary. If it is, we can just edit the value. Otherwise, we append the key to the end of the keys list, and append the value to the end of the values list.

Example 2 shows some example pseudo-code to add a new key-value pair to a dictionary, or change an existing value.

Example 2
SUBROUTINE Add(key, val)
  // Linear search
  index ← -1
  FOR i ← 0 TO this.keys.length - 1
    IF this.keys[i] = key THEN
      index ← i
    ENDIF
  ENDFOR

  IF index = -1 THEN
    // Key not in dictionary,
    // so add the key and value
    this.keys.append(key)
    this.vals.append(val)
  ELSE
    // Key already in dictionary,
    // so change the value
    this.vals[index] = val
  ENDIF
ENDSUBROUTINE

To retrieve the value corresponding to a certain key, we can again use a linear search to get the correct index, and then use this to find the correct value.

Example 3 shows some example pseudo-code to retrieve a value from a dictionary using its key.

Example 3
SUBROUTINE Get(key)
  // Linear search
  index ← -1
  FOR i ← 0 TO this.keys.length - 1
    IF this.keys[i] = key THEN
      index ← i
    ENDIF
  ENDFOR

  IF index = -1 THEN
    // Key not in dictionary
    return null
  ELSE
    // Return the value at that index
    return this.vals[index]
  ENDIF
ENDSUBROUTINE

To remove a key-value pair from the dictionary given the key, we once again perform a linear search to find the correct index.

Example 4 shows some example pseudo-code to remove a key-value pair from a dictionary.

Example 4
SUBROUTINE Remove(key)
  // Linear search
  index ← -1
  FOR i ← 0 TO this.keys.length - 1
    IF this.keys[i] = key THEN
      index ← i
    ENDIF
  ENDFOR

  // If key exists then remove
  // the pair from the lists
  IF index ≠ -1 THEN
    this.keys.removeAt(index)
    this.vals.removeAt(index)
  ENDIF
ENDSUBROUTINE

One use of dictionaries is to store character frequencies in a string.

Example 5 shows some example pseudo-code to count the number of occurrences of each character in a string.

Example 5
// Initialise variables
dict ← Dictionary.Initialise()
string ← input()

// Go through each character
FOREACH char IN string
  count ← dict.Get(char)

  IF count = null THEN
    // Key not in dictionary
    dict.Add(char, 1)
  ELSE
    // Key in dictionary
    dict.Add(char, count + 1)
  ENDIF
ENDFOR

// Output the dictionary
print(dict)

---

What is the worst-case time complexity of the Get method in Example 3?

It is O(n), where n is the number of items in the dictionary (because of the linear search). We will see how this can be reduced on the next page.

---