Held: Monday, 3 November 2014

Back to Outline 33 - Linked Lists in Java. On to Outline 35 - Doubly-Linked Lists.

Summary

We continue our exploration of singly-linked lists, considering a few of the complex issues raised by the LinkedIterator interface and the singly-linked implementation.

Related Pages

• EBoard 34 (Source 34) (HTML 34)

Overview

• Review of singly-linked lists.
• Insertion and deletion in singly-linked lists.
• A trick for simplifying insertion and deletion.

Administrivia

• 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.
  
  • CSC 207 has three kinds of sessions.
  • Group analysis/design, like today.
  • Workshop-style classes (students work on problems in pairs).
  • Combinations.
• Extended office hours this week and next week.
  • Complicated by exam times and too many meetings.
• Some students in a review session said (approximately): "No one reads the eboards" (presumably, except during class). Double-blind vote (Mira approximates, you and I close our eyes):
  • Do you find eboards useful?
  • Should I continue doing eboards?

Upcoming Work

• 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 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 weeks: 7:30 p.m. Internship panel with some random Grinnellian whose name Mira will eventually remember, plus 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.

Review of Singly-Linked Lists

• Nodes have value and next.
• Likely fields: Front of the list
• Optional fields: Back of the list, number of elements.

Insertion and Deletion in Singly-Linked Lists

• We noted that insertion and deletion can be hard, since you want to insert where the cursor is.
• A trick: Keep the cursor immediately before the item you will return with next, rather than on that item.
• How do you deal with the front of the list? You have a "dummy" node.
• What about the remove operation (assuming that we are only moving forward in the list)? (We'll discuss.)

Bi-Directional Traversal in Singly-Linked Lists

• Most of you found a way to implement the previous operation, although perhaps not so efficiently.
• What operations still work correctly when you implement previous?
• What operations do not work correctly?
• How can we deal with those issues?