Held: Friday, 14 November 2014

Back to Outline 40 - Designing a Dictionary API. On to Outline 42 - Implementing Dictionaries with Arrays or Lists.

Summary

We consider techniques for implementing the dictionary ADT.

Related Pages

• EBoard 41 (Source 41) (HTML 41)

Overview

• Review: Thinking about data structures.
• Association lists.
• Techniques for improving the implementation.
• Binary search trees.

Administrivia

• Continue lab partners.
• Today we discuss potential implementations of dictionaries.
  Next week, we'll practice with implementation issues.
• Formal description of project still on my to-do list. Sorry.
• It's Friday. It's time for your weekly PSA.

Upcoming Work

• Homework: Phase 1 of project (Class design, Algorithm design, I/O subsystem)
• No reading for Monday. Today's discussion should provide appropriate preparation.

Extra Credit

Academic

• CS Table Friday: ShellShock

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo. TONIGHT!
• YGB on Saturday, 7:30 p.m. at Sebring-Lewis.
• Copehagen on Nov. 20.

Miscellaneous

• VP Student Affairs Candidate Open Sessions
  • Today, 4:15, JRC 209
  • Wednesday, 4:15, JRC 209
  • Friday next, 4:15, JRC 209

Implementing Dictionaries: A Simple Approach

• Probably easiest to start with an unordered array or linked list.
• We'll store key/value pairs in the array or list.
• We can implement put by adding to the front of the linked list (or the back of the array).
• We can implement get by searching the linked list or array.
• How should we deal with a set for an element already in the array?
  • Technique 1: Find the key/value pair, replace.
  • Technique 2: Just shove new things at the front of the list; we'll see them first anyway.
• What are the running times in each case?
• This approach is typically called an association list.

How can we do better?

• After you design and analyze a data structure (or algorithm), your first question (after assuring correctness) should be Can I do better?
• So, how might we improve this implementation?
• One common strategy: Store in a sorted array.
• One strategy you should know: Use a skip list.
• Are there others?

About binary search trees

• Idea: Apply "divide and conquer" to data structure design.
• Linked structures.
• Two links from every node. One to the "smaller" values, one to the "larger" values.
• When used to implement dictionaries, store a key/value pair in each node.
• Note: While association lists only require that we be able to compare value for equality, binary search trees require that we have a way to order values.