Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 135

/ ** Containerclassforakey-valuepair * /
classKVpair<Key,E>{
privateKeyk;
privateEe;

/ ** Constructors * /
KVpair()
{k=null;e=null;}
KVpair(Keykval,Eeval)
{k=kval;e=eval;}

/ ** Datamemberaccessfunctions * /
publicKeykey(){returnk;}
publicEvalue(){returne;}

}

Figure4.32 Implementation for a class representing a key-value pair.

The fundamental issue is that the key value for a record is not an intrinsic prop-
erty of the record's class, or of any field within the class. The key for a record is
actually a property of the context in which the record is used.
A truly general alternative is to explicitly store the key associated with a given
record, as a separate field in the dictionary. That is, each entry in the dictionary
will contain both a record and its associated key. Such entries are known as key-
value pairs. It is typical that storing the key explicitly duplicates some field in the
record. However, keys tend to be much smaller than records, so this additional
space overhead will not be great. A simple class for representing key-value pairs
is shown in Figure 4.32. The insert method of the dictionary class supports the
key-value pair implementation because it takes two parameters, a record and its
associated key for that dictionary.
Now that we have defined the dictionary ADT and settled on the design ap-
proach of storing key-value pairs for our dictionary entries, we are ready to consider
ways to implement it. Two possibilities would be to use an array-based or linked
list. Figure 4.33 shows an implementation for the dictionary using an (unsorted)
array-based list.
Examining class UALdict (UAL stands for “unsorted array-based list), we can
easily see that insert is a constant-time operation, because it simply inserts the
new record at the end of the list. However, find , and remove both require (n)
time in the average and worst cases, because we need to do a sequential search.
Method remove in particular must touch every record in the list, because once the
desired record is found, the remaining records must be shifted down in the list to
fill the gap. Method removeAny removes the last record from the list, so this is a
constant-time operation.

on the keyword list triggered this appearance of the record. Thus, we cannot write a function that
extracts the key from such a record.