Data Structures

Arrays

• random access
• fixed size

Linked Lists

• dynamically sized
• require an extra reference per data item
• many operations O(n)

Stacks

• LIFO
• operations are push/pop
• all operations can be implemented in O(1) time

Queues

• FIFO
• operations are enqueue/dequeue
• operations can be implemented in O(1) time

Hash Tables

• map key to value
• operations are get/put
• O(1) access to any value

Design Exercise #1

Which data structures would you use to store data in a web mail application? Be specific, for example if you choose to use a hash table, identify which data members will act as keys. How efficiently would your design support the following operations?

• insert new message for user A from user B
• display all messages sent to user A sorted by arrival date
• display all message for user A sorted by sender
• delete a particular message for user A

Design Exercise #2

Which data structures would you use to store data in a calendaring application? Each user can view his/her own calendars and may also view calendars that have been shared among multiple users. How efficiently would your design support the following operations?

• insert a new event into calendar C for user A
• display all events in all calendars shared with/owned by user A
• display all events in a particular calendar