Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Review of singly-linked lists.
  • Effects of previous.
  • Deletion in singly-linked lists.
• Doubly-linked lists.
• Circularly-linked lists. (If there's time.)

Preliminaries

Admin

** Missing: Way too many students: RHB

• Continue lab partners.
• I hope you had a wonderful weekend and found ways to enjoy the weather.
• Welcome to any prospective students who are visiting class.
• Extended office hours this week and next week.
  • Complicated by exam times and too many meetings.
• Exam 1 makeup times distributed via email. Let me know if you requested a time and did not get one.

Upcoming Work

• Think about the following:
  • Whether our previous method breaks our implementation of add and, if so, how you fix it.
  • How can we remove an element efficiently? (It may mean adding or changing the meaning of various fields.)
  • How do we prevent the client from calling remove twice in sequence?
• Homework 8: Sorting Out Sorting due Wednesday.
  • Sorry for misnaming classes.
  • Quicksort may overflow the stack with really bad choices of pivot. Your options are to remove the bad pivot from future tests, or add a try/catch clause to your code. (I've added one for people who download the code later.)
• Readings for Tuesday:
  • Linear Structures
  • Stacks

Cool Upcoming Events on Campus

• Peace studies talk Monday the 10th 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.

Questions

• Is quicksort slower than insertion sort? (Perhaps on some inputs and with a really bad pivot selection method.)

Review of our implementation of singly-linked lists

• Node class: value plus link to next node.
• List class has two fields: front and mods.
  • front points to a dummy node before the first element, which makes adding easier to write.
  • mods keeps track of number of modifications (insertions or removals), which lets us decide whether or not we may have broken an iterator
• Iterators have a three fields:
  • cursor, which points to a node,
  • pos, which keeps track of the position
  • mods, used for failFast (see above).
• Where does the cursor associated with an iterator reside?
  
  • Before the element that will be returned by next
  • Why don't we just keep at at the node that contains the element that will be returned by next? It makes insertion much easier.

Effects of the previous Operation

Here's a typical implementation of the previous operation.

    public T previous()
      throws NoSuchElementException
    {
      failFast();
      if (!this.hasPrevious())
        throw new NoSuchElementException();
      Node current = SimpleLinkedList.this.front;
      while (current.next != this.cursor)
        current = current.next;
      this.cursor = current;
      this.pos--;
      return this.cursor.next.data;
    } // previous()

Another strategy: You can use the position field to identify how many times you have to move forward.

    --this.pos;
    for (i = 0; i < this.pos; i++)
      current = current.next;

How do you implement hasPrevious?

• See if it's equal to the dummy node. Approximately ...

  public boolean hasPrevious()
  {
    return this.cursor == SimpleLinkedList.this.front;
  }
  

• Or use the position field.

Discuss with partner:

• What other operations are there?
  • next Seems okay
  • hasNext Seems okay
  • previousIndex Ignore
  • nextIndex Ignore
  • set - set a value (replace previous value) Sets the value most recently returned by next or previous
  • add - Does this break?
• What operations does adding this implementation of previous break?
  
  • It might break set.

• How do we make set work?

  ListIterator<String> it = list.listIterator()
  ...
  // State        Hello Goodbye Sam
  //                   ^
  it.set("x");
  // What happens?  If you just called `previous`, 
  // when we call set we get
  //      State        Hello X Sam
  // In contrast, if you just called `next`, 
  // when we call set, we get
  //      State        X Goodbye Sam
  

• One strategy: Store a pointer to the prior element.

• Another strategy: Just change the data field. Only works going forward. So ... store direction.
  • If you are moving forward, set the data field in the current node.
  • If you are moving backwards, set the data field in the next node.
• We've fixed set.

Removing elements

    // State:       alpha beta gamma
    //                        ^
    // We know that we've moved forward.
    it.remove()

• What should happen conceptually? Remove the beta

  // State:       alpha ^ gamma
  

• How do we achieve that goal?

  • Reroute the pointer to the node that contains beta to now point to the node that contains gamma.
• And code-wise?
  • Start at the front of the list and keep moving forward until we reach one before the node to be removed. (Just like in the previous method.
• What if I call it.remove() immediately thereafter?

Thoughts

• We can remove an element using a trick like previous - back up to the beginning of the list and find the node before the one we want do remove.
• But that's O(n). Can we do better?

Discuss with partner:

• How can we remove an element efficiently? (It may mean adding or changing the meaning of various fields.)
• How do we prevent the client from calling remove twice in sequence?

Doubly-linked lists

Discuss with partner

• What changes do we make to the Node class?
• 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?
• In dealing with the previous method, we had to store additional information. Do we need to store the same information?

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?