The TAO of Java

Laboratory: Doubly-Linked Lists

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the list ADT through an implementation using doubly-linkeds.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Code Reading
  • Exercise 2: Sequenced Lists
• For Those With Extra Time

Required Code Files:

• DLNode.java
• DoublyLinkedListCursor.java
• DoublyLinkedSequencedList.java
• DoublyLinkedSimpleList.java
• DoublyLinkedSortedList.java
• SequencedListTester.java
• TestDLSimpleList.java
• TestDLSequencedList.java
• TestDLSortedList.java

Exercises

Exercise 0: Preparation

a. You should already have a package named username.lists with a variety of files.

b. Add all of the files linked above in that package.

c. Make sure to change the package name in each file.

Exercise 1: Code Reading

a. Skim through DoublyLinkedSimpleList and confirm that you understand the implementation.

b. Using TestDLSimpleList, verify that it behaves as it should.

Exercise 2: Sequenced Lists

a. Sketch how you might write addToFront, addToEnd, addBefore, and addAfter.

b. Compare your implementations of addToEnd and addBefore to those in DoublyLinkedSequencedList.

c. Fix the implementations of addToFront and addAfter.

d. Test your work using TestDLSequencedList.

For Those With Extra Time

Figure out a way to add an isValid operation. One strategy is to have a counter in the primary class and a corresponding field in each cursor. When we change an element of the primary class, we increment the counter. When we create a cursor, we copy the counter. If the value stored in the cursor is smaller than the counter, the cursor is invalid.

History

Sunday, 27 November 2005 [Samuel A. Rebelsky]

• Wrote initial code.

Monday, 28 November 2005 [Samuel A. Rebelsky]

• Wrote additional code.

Tuesday, 29 November 2005 [Samuel A. Rebelsky]

• Wrote lab.