Dictionaries

 

Dictionaries are a form of container that permits access to data items by content. You put a word into a dictionary because you know you can look it up when you need it.  

The primary operations dictionaries support are:

• 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.
• Insert(D,x): Given a data item x, add it to the set of items in the dictionary D.
• Delete(D,x): Given a pointer to a given data item x in the dictionary D, remove it from D.

Perhaps the simplest possible dictionary implementation maintains an unsorted linked list as a data structure. Insertion and deletion are supported in constant time, although a query requires potentially traversing the entire linked list. Basing an implementation on a stored array speeds up the query operation to by binary search. Making room for a new item or filling a hole left by a deletion may require moving arbitrarily many items, so insertion and deletion become linear-time operations.

Many other dictionary implementations are available. Binary search trees are discussed in some detail in the next section. Hash tables are another attractive option in practice. A complete discussion of different dictionary data structures is presented catalog Section . We encourage the reader to browse through the data structures section of the catalog in order to learn what your options are.

Certain dictionary data structures also efficiently support the following useful operations:

• 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, as discussed below.
• Predecessor(D,k) or Successor(D,k): Retrieve the item from D whose key is immediately before (or after) k in sorted order. By starting from the first item Min(D) and repeatedly calling Successor until we obtain Max(D), we traverse all elements in sorted order.