CSC 343
Homework 2

• Exercise 4.7, merging two sorted singly-linked lists in θ(n) time.

• Choose one of Exercises 10.2-2, 10.2-3, and 10.2-5, implementing other data structures with linked lists. You may do these in pseudocode or real, compilable code. In either case, make clear what internal state your data structure needs to keep track of, and how its publicly-visible operations are carried out.
• Exercise 10.2-7, reversing a singly-linked list in θ(n) time and θ(1) memory (aside from the list itself). Again, you can do this in pseudocode or real, compilable code. (Note: I was asked on a job interview to do this, live at the whiteboard.)
• Problem 10-1, filling in a table of asymptotic times for various operations on various list implementations. (Hint: see p. 230, just before the beginning of chapter 10, for definitions of these operations.)

To be done in Java

• We'll agree, as a class, on a List ADT, which will be published on the Moodle as a Java interface. The ADT will include not only basic operations for construction and querying, but a sort() method and a toString() method.

• Develop several different classes implementing this List ADT, using different internal representations:

  • an array or vector, as built into the Java language
  • an ArrayList, as built into the java.util library
  • a LinkedList, as built into the java.util library
  • a linked list, built from Links as described in Shaffer section 4.1.2
  • a linked list, built using class polymorphism (“a StringList is either an EmptyStringList or a NonEmptyStringList; a NonEmptyStringList has a first and a rest”)

  Each student is expected to implement at least two of these, and I'd like each one to be implemented by at least two students. We'll discuss who's doing which in class or on Moodle.

  Each implementing class should implement all the operations of the interface, including sort. Use the same sorting algorithm, e.g. insertion-sort, for all implementing classes. Do not use Java library sort methods; write your own.

• Now suppose the sort method hadn't been part of the ADT, and therefore hadn't been supplied by the implementers. Develop a sortFromOutside method (in another class) that takes in a List and, without knowing which implementation it is, sorts it by using only the (non-sort) operations in the ADT. I should be able to plug in an instance of any other student's implementation and have your sortFromOutside method sort it correctly.

• Discuss the pros and cons of the various implementations. What kinds of problems would be easier to do in one implementation than another?