, , , , , , ,

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

Homework 4: Doubly linked lists and inheritance

Homework 4 (mirror) is due before lecture 16: Game Trees.

The assignment asks you to implement a doubly-linked list that satisfies these invariants.

  1. For any DList d, d.head != null.
  2. For any DListNode x in a DList, x.next != null.
  3. For any DListNode x in a DList, x.prev != null.
  4. For any DListNode x in a DList, if x.next == y, then y.prev == x.
  5. For any DListNode x in a DList, if x.prev == y, then y.next == x.
  6. For any DList d, the field d.size is the number of DListNodes, NOT COUNTING the sentinel, that can be accessed from the sentinel (d.head) by a sequence of “next” references.

No test code is provided, but users are encouraged to write their own.

Although it’s not speifically mentioned, it is implied DListNode.java should not be modified.

It becomes clear, in part 2, the specification permits a DList that has the potential of being corrupted (as in: it violates its invariants) via hostile or badly written code on the side of an application that uses it. Even though this is true, a good effort should be put in plugging as many such potential holes as possible in DList.java (without modifying DListNode.java).

Here’s an example of some test code that can be used:

DListTest.java (view | download)

I added two additional methods in DList to help with verification. One is hasValidLength() which checks invariant #6; Basically boils down to: return size == actualLength;. The other is toStringBackwards() which should return the same string as toString() does, but does so by traversing the list backwards instead of forwards. So this condition should always be true: list.toString().equals(list.toStringBackwards()).

My test code uses those two methods and their calls should be removed from DListTest.java if not implemented in DList.

DListTest.java, if run against a DList.java that follows the given specs in the assignment, will at best give a result such as: Successful tests: 21/24. That’s fine and within the scope of the assignment. — See further below for a version that gets a full score 😉

Here’s such a DList:

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

Part 2 of the assignment asks you to find which parts of the DList have weakness against hostile or badly written code. The main culprit is: a DListNode node, when passed as a parameter to some of the methods, may not even be part of this Dlist instance.

Part 3 of the assignment asks you to make a list with nodes that can be locked, so that they cannot be removed.

To achieve this, both DList and DListNode must be extended. The assignment specification demands that the subclasses may not have more code than is absolutely necessary to achieve the goal.

LockDList.java (view | download)
LockDListNode.java (view | download)

And here’s some test code:

LockDListTest.java (view | download)


Here’s a subclass implementation that is safe against the weaknesses mentioned in part2. To achieve this, SafeDListNode nodes are aware of which SafeDList list they belong to.

SafeDlist.java (view | download)
SafeDListNode.java (view | download)

And here’s some test code:

SafeDListTest.java (view | download)

As promised, this does get a score of 24/24 successful tests.

You can get all the above sources in gotfu_hw4.zip