Scribd
Upload
8 views16 pages

Dictionary Implementations Overview

The document discusses different implementations of dictionaries using arrays, vectors, and linked lists. Array-based implementations can use arrays of entry objects, parallel arrays of keys and values, or 2D arrays. Unsorted array dictionaries have O(1) addition but O(n) removal and retrieval, while sorted arrays have O(log n) retrieval but O(n) addition and removal. Vector dictionaries are similar but vectors dynamically resize. Linked dictionaries can link entry objects or use parallel key/value chains, with unsorted versions having same efficiency as unsorted arrays.

Uploaded by

gitu583
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
8 views16 pages

Dictionary Implementations Overview

The document discusses different implementations of dictionaries using arrays, vectors, and linked lists. Array-based implementations can use arrays of entry objects, parallel arrays of keys and values, or 2D arrays. Unsorted array dictionaries have O(1) addition but O(n) removal and retrieval, while sorted arrays have O(log n) retrieval but O(n) addition and removal. Vector dictionaries are similar but vectors dynamically resize. Linked dictionaries can link entry objects or use parallel key/value chains, with unsorted versions having same efficiency as unsorted arrays.

Uploaded by

gitu583
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Dictionary Implementations

Chapter 18
Chapter Contents
Array-Based Implementations
• The Entries
• An Unsorted Array-Based Dictionary
• A Sorted Array-Based Dictionary

Vector-Based Implementation
Linked Implementations
• The Entries
• An Unsorted Linked Dictionary
• A Sorted Linked Dictionary
2
Array Based Implementations
Each entry consists of two parts
• A search key
• A value

Strategies
• Encapsulate the two parts into an object
• Use two parallel arrays
• Use a two dimensional array

Text
Textfocuses
focuseson
onfirst
first
approach
approach
3
Array-Based Implementations
Fig. 18-1 3 ways to
use arrays to
represent dictionary
entries: (a) an array
of entry objects; (b)
parallel arrays of
search keys and
values;
(c) 2-dimensional
array of search keys
and values

4
The Entries
A class to represent the two-part entries
private class Entry implements [Link]
{ private Object key;private Object value;
private Entry(Object searchKey, Object dataValue)
{ key = searchKey;
value = dataValue;
} // end constructor
private Object getKey()
{ return key;} // end getKey
private Object getValue()}
{ return value; } // end getValue
private void setValue(Object dataValue)
{ value = dataValue; } // end setValue
} // end Entry
5
Unsorted Array-Based Dictionary

Fig. 18-2 Unsorted,


array-based dictionary:
(a) adding an entry;
(b) removing an entry.

6
Array-Based Implementations
Unsorted worst-case efficiencies
• Addition O(1)
• Removal O(n)
• Retrieval O(n)
• Traversal O(n)
Sorted worst-case efficiencies
• Addition O(n)
• Removal O(n)
• Retrieval O(log n)
• Traversal O(n)
7
Sorted Array-Based Dictionary

Fig. 18-3 Adding an


entry to a sorted
array-based
dictionary:
(a) search;
(b) make room;
(c) insert.

8
Sorted Array-Based Dictionary
Beginning of the class
public class SortedArrayDictionary implements DictionaryInterface,
[Link]
{ private Entry [] entries; // array of sorted entries
private int currentSize = 0; // number of entries
private final static int DEFAULT_MAX_SIZE = 25;
public SortedArrayDictionary()
{ entries = new Entry[DEFAULT_MAX_SIZE];
currentSize = 0;
} // end default constructor
public SortedArrayDictionary(int maxSize)
{ entries = new Entry[maxSize];
currentSize = 0;
} // end constructor
...
9
Vector-Based Implementations
Similar in spirit to the array-based version
With vector no need for …
• makeRoom
• doubleArray
• isArrayFull

• Counting entries, vector does so for you

Downside
• Requires some involved casts

10
Vector-Based Implementations
Beginning of the class
public class SortedVectorDictionary implements DictionaryInterface,
[Link]
{ private Vector entries;
public SortedVectorDictionary()
{ entries = new Vector(); // as needed, vector doubles its size
} // end default constructor
public SortedVectorDictionary(int maxSize)
{ entries = new Vector(maxSize);
} // end constructor
...

11
Linked Implementations

Fig. 18-4 a) Could use a chain of nodes that


each reference an entry object
12
Linked Implementations

figure 18-4 a & b

Fig. 18-4 b) Use parallel chains of


search keys and values
13
Linked Implementations

figure 18-4 c

Fig. 18-4 c) Use a chain of nodes that each


reference a search key and value
14
Linked Implementations
Unsorted worst-case efficiencies
• Addition O(1)
• Removal O(n)
• Retrieval O(n)
• Traversal O(n)
Sorted worst-case efficiencies
• Addition O(n)
• Removal O(n)
• Retrieval O(n)
• Traversal O(n)
15
Linked Implementations

Fig. 18-5 Adding to an unsorted linked dictionary.

16

You might also like