Data structure recommendation for application

Good afternoon,

I'm looking at writing a day time based appointment book app for a windows ce based device.
Windows ce is typically used in resource constrained environments; phones, headless devices, etc.. Consequently, it has a smaller process space and virtual memory model than desktop windows OSes, so memory consumption is an issue.

Can anybody provide me with a recommendation for the best data structure to use to internally "store/retrieve" the appointments? I was thinking the best approach would be to split up the data structure into 12 units corresponding to each month so it's quicker to traverse.
It's been a bit since the college days but I was thinking the following:

1. Hash table for each month. This would allow extremely fast lookups O(1) but I have concerns about the memory overhead associated with using a hash table. And when the # of appointments gets large the frequency of collisions will increase which may require regenerating the hash algorithm (right?) .

2. Linked list for each month. Minimal overhead for the data structure but will take time to walk the list to retrieve appointment at end O(n).

3. Sorted Array. Inserts will be expensive. Looks faster.

Any other ideas? Ideally I want the fastest performance with minimal overhead (duh)! Your help is greatly appreciated.