CSE 131 Module 6: Abstract Data Types

Practice Problems

Directions: Familiarize yourself with the documentation for Java's built in LinkedList class, which is an implementation of a list abstraction as discussed in lecture.

Primitives like int and double are not classes, so their values are not Objects. However, sometimes we want to be able to put a primitive value in a data structure where an Object is required. Therefore, as a convenience, Java provides classes that correspond to each of the primitive types. For example, the Integer class provides a constructor whose parameter is the int value that should be held inside the object, and provides an accessor intValue that returns the int value that was stored in the Integer object. (In Java 5.0 and later, this conversion happens automatically. For example, if you pass an int to the add method of a List, the Java compiler will insert code that will automatically create an Integer object corresponding to that int value.)

  1. Study the following procedures and then write specifications of what they do. If in doubt, try hand simulating the execution of the procedure on some small test cases.

    LinkedList<Integer> foo(int n) {
      LinkedList<Integer> result = new LinkedList<Integer>();
      while (n >= 0) {
      return result;
    double bar(LinkedList<Integer> numbers) { // asssume: numbers is not null
      double result = 0;
      for (Integer i : numbers)
        result += Math.pow(i, 0.5);
      return result;
    LinkedList<String> baz(LinkedList<String> a, LinkedList<String> b) {
      // Assume: a and b are not null
      Iterator<String> ls1 = a.iterator();
      Iterator<String> ls2 = b.iterator();
      LinkedList<String> result = new LinkedList<String>();
      while (ls1.hasNext() && ls2.hasNext())
         result.addLast(ls1.next() + " " + ls2.next());
      return result;
  2. Write a procedure pairwiseSum that takes as its parameters two LinkedLists of Integers and returns a new LinkedList that is the pairwise sum of the lists. If the lists are of different lengths, do the computation as if the shorter list has zeros at the end. For example, if the given lists are (1 2 3 4) and (4 5), the resulting list would be (5 7 3 4).

  3. Write a procedure reverse that takes as its parameter a LinkedList and returns a new LinkedList with the same data, but in the reverse order.

  4. Write a procedure multiplyPosition that takes as its parameter a LinkedList containing Double objects as data, and returns another LinkedList in which each of the original values was multiplied by its position (index) in the list. For example, if the input was (2 2 2 1 9), the result would be (0 2 4 3 36), computed as follows: (2*0 2*1 2*2 1*3 9*4).