Pick two data structures to use in implementing a Map. Describe lookup, insert, & delete operations. Give time & Space Complexity for each.

Give pros & cons for each.

a) Linked List I. Insert is O(1)

II. Delete is O(1)

III. Lookup is O(1) auxiliary and O(N) worst case.

IV. Pros: Fast inserts and deletes, can use for any data type.

V. Cons: Slow lookups.

b) Balanced Search Tree (RB Tree)

I. Insert is O(logn)

II. Delete is O(logn)

III. Lookup is O(logn)

IV. Pros: Reasonably fast inserts/deletes and lookups.

V. Cons: Data needs to have order defined on it.