Data Structures Summary
The Search Problem
The problem we are presented: Given a stream of data, retrieve information of interest.
What are some examples of this?
- Website users post to personal page. Serve content only to friends.
- Given logs for thousands of weather stations, display weather map for specified date and time.
- Dog owners request the best pet store, choosing to define their best store either in price, quality, or atmosphere.
All of the data structures we have discussed so far have been to solve the search problem. How you might ask? Each of the data structures we've learned are used for storing information in schemes that make searching efficient in specific scenarios.
Search Data Structures
| Name | Store Operation(s) | Primary Retrieval Operation | Retrieve By |
|---|---|---|---|
| List | add(key), insert(key, index) |
get(index) |
index |
| Map | put(key, value) |
get(key) |
key identity |
| Set | add(key) |
containsKey(key) |
key identity |
| PQ | add(key) |
getSmallest() |
key order (aka key size) |
| Disjoint Sets | connect(int1, int2) |
isConnected(int1, int2) |
two integer values |
Remember that these are Abstract Data Types. This means that we define the behavior, not the implementation. We've defined many of the possible implementations in previous chapters. Let's think about how these implementations and ADTs interact:
What does this diagram tell us? The first thing you'll notice is that many implementations that we have devised in earlier chapters can be used in implementing many different ADTs. You'll also notice the red colored implementations (meaning poor performance), telling us that not all implementations are optimal for the behavior we are trying to achieve.
Exercise 14.1.1. Consider how each of these implementations can be modified in order to accommodate to the behavior attempting to be defined. For example, how would we use a Hash Table to function as a Priority Queue?
Abstraction
Abstraction often happens in layers. Abstract Data Types can often contain two abstract ideas boiling down to one implementation. Let's consider some examples:
- If we remembered the Priority Queue ADT, we were attempting to find an implementation that would be efficient for PQ operations. We decided that our Priority Queue would be implemented using a Heap Ordered Tree, but as we saw we had several approaches (1A, 1B, 1C, 2, 3) of representing a tree for heaps.
- A similar idea is an External Chaining Hash Table. This data structure is implemented using an array of buckets, but these buckets can be done using either an ArrayList, Resizing Array, Linked List, or BST.
These two examples tell us that we can often think of an ADT by the use of another ADT. And that Abstract Data Types have layers of abstraction, each defining a behavior that is more specific than the idea that came before it.