Held: Tuesday, 28 October 2014

Back to Outline 30 - OOD in Practice: Designing a List Interface. On to Outline 32 - Linked Lists in Java.

Summary

We consider a very simple implementation of lists, using arrays.

Related Pages

• Reading: Designing List ADTs
• Lab: Implementing Lists with Arrays
• Repository: https://github.com/Grinnell-CSC207/lab-array-based-lists
• EBoard 31 (Source 31) (HTML 31)

Overview

• Status of our List Interface.
• Implementing Lists with Arrays - The Basics.
• Implementing Lists with Arrays - Some Complications.

Administrivia

• Continue lab partners.
• Dr. Davis will be visiting our class today.
• Extended office hours this week (and probably next).
• Tomorrow, we will discuss ways for students to recover from difficulties they had on exam.
• Tomorrow, we will also discuss likely projects.

Upcoming Work

• Reading for Wednesday:
  • Review your notes on linked lists from 161.
  • Reflect on how you might make those linked lists meet our new SimpleList interface (see today's lab for details).

Extra Credit

Academic

• CS Extras Thursday: Randomness
• Pre-CS Extras: Graduate School Meeting at 3:45.
• Wednesday at 7:30 p.m. Internship panel with Lea and Mira and some random Grinnellian who interned at Google.

Peer Support

• China's talk on A Model for Transport in Stereocilia, today at 4:15 pm in Science 2517.
• Men's Soccer, Wednesday at 4pm vs. Cornell.
• Basketball Scrimmage Wednesday at 7pm in Darby.
• Ajuna's Radio show Mondays at 8pm. Listen to African music
• Ajuna MC's talk on Sustainability of Grinnell Wednesday at noon in ARH 102.
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo.
• Saturday fall festival to support MICA. 4-8 pm in Main Quad.
• Cook for ISO Food Bazaar. (You need to submit recipes in order to do this.)
• Eat at ISO Food Bazaar.

Status

• We've been designing a new ADT (although one you already know a bit about).
• We designed one version that worked just with strings.
• We also designed a more generalized version.
• Now it's time to start implementing it.

Implementing Lists with Arrays

"If all you have is a hammer, everything looks like a nail."

• We'll start with a simple approach - Since the primary structure we know is an array, we'll use arrays to implement our lists.
• Fields:
  • The underlying array
  • A count of the number of set elements
• What's an Iterator? It will be a position in the array.
• How do we append?
• How do we prepend?
  • Easy strategy: Shift everything over one, which is in O(n).
  • Harder strategy: Wrap around.
• What happens when we insert at the iterator?
  • Almost always - Shift things down, which is O(n)
  • What does that do to the other iterators? Maybe it's time to change our documentation.