Dictionary Abstract Data Types

Table of Contents

Dictionaries

The dictionary data type permits access to data items by content. You stick an item into a dictionary so you can find it when you need it.

The primary operations of dictionary support are:

  1. Search(D,k) – Given a search key k, return a pointer to the element in dictionary D whose key value is k, if one exists.
  2. Insert(D,x) – Given a data item x, add it to the set in the dictionary D.
  3. Delete(D,x) – Given a pointer to a given data item x in the dictionary D, remove it from D.

Certain dictionary data structures also efficiently support other useful operations:

  1. Max(D) or Min(D) – Retrieve the item with the largest (or smallest) key from D. This enables the dictionary to serve as a priority queue
  2. Predecessor(D,k) or Successor(D,k) – Retrieve the item from D whose key is immediately before (or after) k in sorted order. These enable us to iterate through the elements of the data structure.

Many common data processing tasks can be handled using these dictionary operations. For example, suppose we want to remove all duplicate names from a mailing list, and print the results in sorted order. Initialize an empty dictionary D, whose search key will be the record name. Now read through the mailing list, and for each record search to see if the name is already in D. If not, insert it into D. Once finished, we must extract the remaining names out of the dictionary. By starting from the first item Min(D) and repeatedly calling Successor until we obtain Max(D), we traverse all elements in sorted order.

By defining such problems in terms of abstract dictionary operations, we avoid the details of the data structure’s representation and focus on the task at hand.

Carefully investigate simple dictionary implementations based on arrays and linked lists. More powerful dictionary implementations such as binary search trees and hash tables are also attractive options in practice.

TODO

A complete discussion of different dictionary data structures is presented in the catalog in Section 12.1 (page 367). Skiena

Links to this note