New lab partners!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The design of ADTs, revisited.
• Exercise: Designing a list ADT.
• Quick notes on implementation.

Preliminaries

Admin

• I hope you had an awesome break! I particularly hope you had a chance to rest and relax.
• Exam 1 to be returned at the end of class (about 11:40).
  • I think I spent more time grading your exam than any of you spent taking it.
• Dr. Davis will be visiting our class tomorrow.
• Office hours
  • Extended office hours this week. See outside my office.
• A correction on my interpretation of College policies on academic honesty: In discussing the situation in CSC 151, I may have told you that if you don't turn in work, then you cannot be charged for academic dishonesty on that work. While the chair of the CAS subcommittee on academic dishonesty agreed with me that it was appropriate to tell you that for my take-home exams, the dean who serves on that committee told me that that policy does not always apply. So don't count on it. (I don't expect that you will ever need to count on that rule, but I don't want to mislead you if you find that you want to.)

Upcoming Work

• Reading for tomorrow:
  • Designing List ADTs
    • The reading goes over some of the issues we will discuss in class today, as well as some others.
  • Lists with Current Considered Harmful
• Also reflect on how you might implement lists with arrays.

Extra Credit

Academic

• CS Extras Thursday: Randomness
• 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, Tuesday 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.

Questions

The design of ADTs, revisited

What are the key ideas in designing an ADT?

• Philosophy - The primary idea that drives the ADT; what distinguishes it from others
• Use cases - Ways in which we use the data type
• Methods - The functions that it supports

Exercise: Designing a list ADT

With your partner, answer each of the following. (I'll probably stop you along the way to share and compare answers.)

What is the basic "philosophy" of lists?

• Lists are homogensous collections of values that grow dynamically.
  • Or are lists heterogenous collections of values that grow dynamically.
• You should be able to access an element at a specific index.
  • Or is that more of an array/vector?
• In which you can insert elements at various positions
• And you can rearrange the elements VETO
• The elements are "in order" (as compared to a "set" or "bag")
  • There's a first (in the nonempty list)
  • There's a last (in the nonempty list)
  • Each element except the last has a next element
  • Each element except the first has a previous element
• The client of the list determines the order

Can we efficiently insert and index? (Efficiently usually means O(1), at least in this case.)

• We can't think of a way.
• So we can give up indexing.

Sam's attempt to tie our ideas together.

• Lists are dynamic, homogenous, client-ordered, linear collections of values.
  • By dynamic, we mean that you can add or remove elements.
  • By client-ordered, we mean that ...

What's the difference between how we think about a Vector (dynamic array) and a List?

• In vectors, we don't assume indices of values change
• In lists, we expect that the implicit indices of values change when we insert or delete.

What use cases do you envision?

What general categories of operations/methods you expect a list to provide?

• Constructors
  • Build a new list
• Mutators
  • Add elements to the list (aka "insert")
  • Delete elements from the list (aka "remove")
  • Other mutators
    • Swap elements in the list
  • Set elements
• Observers
  • Get elements from the list
    • First
    • Last
    • Get the element at a particular index (?)
  • Get the number of elements in the list (length)
    • IsEmpty
  • Determine information about the relationship between elements
    • Does an element have a next element?
• Interesting big things to do with lists
  • Reverse- build a reversed version of the list
  • Map
  • ForEach: Do something to each value in the list
  • Contains
  • RemoveAll

What are the details of some of the methods within each category?

E.g., insert, remove

insert

• parameter

  • list (maybe the primary object)
  • value to insert

  • position - where to insert it

    public interface SimpleList { public void insert(T value, Position p);

    public void addToEnd(T value);

    public void insertAfter(T here, T newvalue); // What happens if the same value appears twice? }

What's a position?

• Option 1: An integer. Yech.

• Option 2: A data type that has related methods

  interface SimpleList<T>
  {
     Position front();
  }
  
  
  interface Position
  {
     void advance();
  }
  SimpleList.get(p);
  

• Option 3: A notion of the current location in the list
• Option 4: Iterator: Something that steps through the list. Java's model.

Quick notes on implementation

What are the key ideas in designing a data structure / implementing an ADT?