, , , , , , , ,

Course: Berkeley’s CS 61B: Data Structures.

Homework 5: Safer doubly linked lists and sets

Homework 5 (mirror) is due before lecture 19: Asymptotic Analysis.

This assignment solves the invariant violations possible in hw4 by introducing a smarter/safer DListNode, the node knows the list it belongs into and some of the duties have been moved off the DList class and into the DListNode class.

Part 1 of the assignment asks you to implement the stubs (unimplemented methods) in the two classes. Code from hw4 should fit here, with minor modifications.

DList.java (view | download)
DListNode.java (view | download)

Part2 of the assignment asks you to implement a Set ADT that uses a List to store elements and satisfies these invariants:

  1. The Set‘s elements must be precisely the elements of the List.
  2. The List must always contain Comparable elements, and those elements must always be sorted in ascending order.
  3. No two elements in the List may be equals().

If you need a brush up on Sets this should do it.

Set.java (view | download)

The rest of the files are not modified.