Homework 1: Lists

This assignment is to get you familiar with Java.

Part 1:

Fill in the procedures squish() and twin() in the SList class. Read comments in SList.java to see what needs to be done. Implement a doubly-linked list class called DList.

Part 2:

Implement a Set ADT in Set.java. Your sets should behave like mathematical sets, which means they should not contain duplicate items. To make set union and intersection operations run quickly, you will keep your sets will contain only Comparable elements, and you will keep them in sorted order from least to greatest element. (You will want to review the Comparable interface on the Java API web page.)

You will need to decide on fields and implement the following methods:
public Set() constructs an empty Set
public int cardinality()Number of elements in this Set
public void insert(Comparable c)Insert c into this Set
public void union(Set s)Assign this = (this union s)
public void intersect(Set s) Assign this = (this intersect s)
public String toString() Express this Set as a String


union() and intersect() must run in linear time. Be sure to declare variables of type List and ListNode, not variables of type DList, DListNode, SList or SListNode. Set.java should be able to switch between using DLists and using SLists by changing one constructor call in the Set() constructor.

Support files:
  1. List.java
  2. ListNode.java
  3. InvalidNodeException.java
  4. SList.java
  5. SListNode.java
  6. TestHelper.java
  7. DList.java
  8. DListNode.java
  9. Set.java

Bonus points:

Implement a singly-linked list, a doubly-linked list and a set in C. Readings: K&R