Abstract Data Types
Terms
undefined, object
copy deck
- Implement a stack where put and get operations are: O(1) worst-case time
- Array (but can overflow) Linked list
- Implement a stack where put and get operations are: O(1) time/operation
- Array with doubling
- Implement a queue where put and get operations are: O(1) worst-case time
- Array (but can overflow) Linked list (need to keep track of both head & tail)
- Implement a queue where put and get operations are: O(1) time/operation
- Array with doubling
- Implement a priority queue where insert and getMin operations are: O(1) worst-case time if set of priorities is bounded
- One queue for each priority
- Implement a priority queue where insert and getMin operations are: O(log n) worst-case time
- Heap (but can overflow)
- Implement a priority queue where insert and getMin operations are: O(log n) time/operation
- Heap (with doubling)
- Implement a priority queue where insert and getMin operations are: O(n) worst-case time
- Unsorted linked list Sorted linked list (O(1) for getMin) Unsorted array (but can overflow) Sorted array (O(1) for getMin, but can overflow)
- Implement a set where insert, remove and contains operations are: O(1) worst-case time
- Bit-vector (can also do union and intersect in O(1) time)
- Implement a set where insert, remove and contains operations are: O(1) expected time
- Hash table (with doubling & chaining)
- Implement a set where insert, remove and contains operations are: O(log n) worst-case time
- Balanced BST
- Implement a set where insert, remove and contains operations are: O(n) worst-case time
- Linked list Unsorted array Sorted array (O(log n) for contains)
- Implement a dictionary were insert(k,v), get(k) and remove(k) operations are: O(1) expected time
- Hash table (with doubling & chaining)
- Implement a dictionary were insert(k,v), get(k) and remove(k) operations are: O(log n) worst-case time
- Balanced BST
- Implement a dictionary were insert(k,v), get(k) and remove(k) operations are: O(log n) expected time
- Unbalanced BST (if data is sufficiently random)
- Implement a dictionary were insert(k,v), get(k) and remove(k) operations are: O(n) worst-case time
- Linked list Unsorted array Sorted array (O(log n) for contains)
- You want to build an address book with entries in alphabetical order by last name. Unsorted List Sorted List Stack Balanced Search Tree Directed Graph
- Balanced Search Tree
- You want to build a meeting reminder for a PDA that keeps track of events you schedule and periodically checks the next event to sound an alarm to remind you of the next thing you need to do. List Hashtable Stack Queue Priority Queue
- Priority Queue
- You want to build a table of contents for a textbook. The textbook consists of chapters, chapters consist of sections, and sections consist of subsections. List Hashtable Tree Binary Tree Balanced Tree
- Tree
- You want to build an email address miner that scans a hard drive looking for email addresses, then sends them to a remote host. List Hashtable HashSet Array Balanced Tree
- HashSet
- You want to keep track of appointments and other events organized by their time and date. It is important to be able to efficiently find all the events between a starting time/day and an ending time/day. Hash table Linked list Doubly-linked list Binar
- BST
- You are writing a program that watches packets going by on the network and records the IP address of the host machine sending each packet, for later processing. It’s important that your program not pause for any significant amount of time because it mig
- Linked List
- You are implementing an interactive program development environment (like Eclipse) for the Java language. You need a data structure that keeps track of all the classes and packages and lets you find, for example, the set of classes in a given package or i
- Tree
- Insert, ReportMin, Contains, and GetMax each take time O(log n) in the worst case
- Balanced BST
- Insert and ReportMin each take time O(1) in the worst case.
- Use a linked list along with a variable that holds the current min
- Insert, Contains, and ReportMin each take expected time O(1).
- Use a hash table (with chaining and doubling) and a variable that holds the current min.
- GetMax takes time O(1) in the worst-case and Contains takes time O(log n) in the worst case.
- A sorted array
- You want to build a table of contents for a textbook. The textbook consists of chapters, chapters consist of sections, and sections consist of subsections. List HashMap Tree Binary Tree Huffman Tree
- Tree
- You want to build a meeting reminder for a PDA that keeps track of events you schedule and periodically checks the next event to sound an alarm to remind you of the next thing you need to do. List HashMap Stack Queue Priority Queue
- Priority Queue
- You want to build a telephone book with entries in alphabetical order by last name. Unsorted List Sorted List Stack Search Tree Undirected Graph
- Search Tree
- You want to build a model of the local area net in your department to run some routing simulations. List HashMap HashSet Array Directed Graph
- Directed Graph