Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Doubly-linked lists.
• Circularly-linked lists.

Preliminaries

Admin

• New lab partners. (Also HW partners, unless you've indicated that you want to work alone; I've paired singletons.)
  • AHD and CMV
  • AK and PS
  • AOA and EE
  • AS and YK
  • CG and TP
  • CM and NS
  • EF and NK
  • HZ and ZW
  • LG and ZC
  • MSZ and WR
  • RHB and LBA
• Extended office hours this week and next week.
  • Complicated by exam times and too many meetings.
• I've been scheduled in an important meeting during class time on Friday. (Thank you Grinnell College.) You should show up and do the lab on linear structures/stacks. Mira will run lab.
• Review session tomorrow at 11 am (with Sam)
• A great quote from Made to Stick: "Trying to solve a problem beore being taught the solution leads to better learning, even when errors are made in the attempt."

Upcoming Work

• Homework 8: Sorting Out Sorting due tonight.
• Homework 9: Skip Lists due next Wednesday.
• Readings for Friday:
  • Linear Structures
  • Stacks
  • Yes, these used to be the readings for today (and Tuesday).

Cool Upcoming Events on Campus

• Peace studies talk Monday at 4:15 p.m. in JRC 101 "With All the World’s Violence, Where is Peace?"

Extra Credit

Academic

• CS Extra Thursday: Study Abroad in CS.
• CS Table Friday: Open Data.
• Wednesday one week: 7:30 p.m. Internship panel with Nelson, Mira, and Lea.

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music tonight!
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Charlie's Friday Night "War in Animated Film" ExCo.
• Womens soccer game Friday, 2:00 p.m., at Lake Forest.
• One event in the African Carribean Student Union series next week
  • Sometimes you get food, too
  • And you can contribute money to a good cause!
• Womens BBall Alumni Game on Saturday at maybe 1pm

Questions

Doubly-linked lists

Discuss with partner

• What changes do we make to the Node class to achieve doubly-linked lists?

  public class Node
  {
    T data;
    Node next;
    Node prev;
  } // class Node
  

• In dealing with singly-linked lists, we kept the cursor at the node before the next node. Where should we keep it now?

• Given those decisions, how do we implement
  • add?
  • remove?
  • next?
  • previous?
  • set?
• In dealing with the previous method, we had to store additional information (e.g., which direction we are going). Do we need to store the same information?
• In dealing with the remove method, we had to keep track of whether we'd just removed a node. Should we still do so?

Question one: Where do we put the cursor?

• On the node prior to the node for next, just like we did before. (aka "right before the conceptual cursor")
  • Makes more sense for remove when we are going forward.
  • Will require us to have a dummy node at the front
• On the node that contains the next value, because that seems more sensible. (aka "right after the conceptual cursor")
  • May not make a difference
  • May require that we have a node at the end
• Somewhere else
• May not make a difference, so we'll choose the first, since it's consistent with what we've done before.

Let's write pseudo-Java (not all of the syntax will be perfect

    public class DoublyLinkedIterator<T>
    {
      Node<T> cursor;
      int pos;
      boolean forward;

      public T next()
      {
        failFast();
        if (!this.hasNext())
          throw new SomeSillyThingException()
        this.cursor = this.cursor.next;
        forward = true;
        return this.cursor.data;
      } // next()

      public T previous()
      {
        failFast();
        if (!this.hasPrevious())
          throw new SomeSillyThingException()
        this.cursor = this.cursor.previous;
        forward = false;
        return this.cursor.next.data;
      } // previous()

      public void add(T val)
      {
        failFast();
        Node<T> newnode = new Node(this.cursor, val, this.cursor.next); // (prev,val,next)
        this.cursor.next = newnode;
        newnode.next.prev = newnode;
        this.cursor = newnode;
      } // add(T)

      public void remove()

      public void set(T val)
    }

Circularly-linked lists

• Are there benefits to having the last element link to the first, and vice versa? Will a dummy node make a difference?