The problem we are presented: Given a stream of data,
retrieve information of interest.
- 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’ve discussed so far have been to solve the
search problem. They are used for
storing information in schemes that make searching efficient in specific scenarios.
Remember that these are
Abstract Data Types. This means that we define the behavior, not the implementation.
Also, we’ve defined many possible implementations. Let’s see how these implementations and ADTs interact:
What does this diagram tell us?
- Many implementations can be used in implementing many different ADTs.
- The red colored implementations (meaning poor performance) tell us that not all implementations are optimal for the behavior we are trying achieve.
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 often happens in layers! Abstract Data Types can often contain two abstract ideas boiling down to one implementation. Let’s consider some examples:
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.
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 ADTs have layers of abstraction, and each defining a behavior that is
more specific than the idea that came before it.
When trying to manage complexity and write programs that are fast, it is important of knowing first of all:
- What the Abstract Data Types are that will make your life easy?
- Which implementation will make your implementation faster?
- Usually a good implementation is good enough.
A data structure is a
collection of data values, the
relationships among them, and the
functions or operations that can be applied to the data.
- List, Stack, Queue 等是 Abstract Data Type（或者说是 Data Type？算法第四版交换使用 ADT 和 Data Type 这两个词，似乎不作区分）
- 而 Array 和 Linked List 是 Data Structure，侧重的是数据的存储方式。
- 每一种 ADT 都既可以用 Array 来实现，也可以用 Linked List 来实现。
In computer science, a ‘tree’ is a widely used abstract data type (ADT)—or data structure (like BSTs) implementing this ADT.
Also, we can use Array or Linked List to store a tree.