Review 1: Introduction

Problem 1.1.1.

Explain what is meant by the term abstract data type (ADT).

Problem 1.1.2.

The List and Set ADTs are both for representing collections of data values. What makes them different? That is, in what situations should one seek a good data structure for the List ADT, and in what situations should one seek a good data structure for the Set ADT?

Problem 1.1.3.

Write a definition of the List interface as it would be defined within the java.util package, including at least four of the methods explicitly covered in class.

public interface List<E> {
    public int size();
    public boolean add(E value);
    public void add(int index, E value);
    public E remove(int index);
    public E get(int index);
    public E set(int index, E value);
}

Problem 1.2.1.

Consider the following fragment that works with a List variable named data.

for(int i = 1; i < data.size(); i++) {
    data.remove(i);
}

Suppose before executing this fragment, data holds <2, 3, 5, 7, 11, 13, 17>. What will data hold following the completion of the fragment?

Problem 1.2.2.

Suppose we have a List<Integer> variable scores. Using a List's get method to get each Integer, write a code fragment that computes the sum of the Integers into an int variable called sum.

int sum = 0;
for(int i = 0; i < scores.size(); i++) {
    sum += scores.get(i).intValue();
}

Problem 1.2.3.

Suppose we have a BufferedReader variable named file. The BufferedReader class contains a readLine method that reads the next line of a file with each call, returning a String — or it returns null if there are no more lines remaining. Write a code fragment that displays the lines of file in reverse order. (You'll want to store up the lines into an ArrayList and then print them back using System.out.println.)

ArrayList<String> lines = new ArrayList<String>();
String line = file.readLine();
while(line != null) {
    lines.add(line);
    line = file.readLine();
}
for(int i = lines.size() - 1; i >= 0; i--) {
    System.out.println(lines.get(i));
}

Problem 1.2.4.

Below, complete countZeroes so that it counts the number of appearances of 0 in a list. The test method illustrates how the method should work.

public static void test() {
    List<Integer> nums = new ArrayList<Integer>();
    nums.add(new Integer(2));
    nums.add(new Integer(0));
    nums.add(new Integer(4));
    System.out.println(countZeroes(nums)); // prints "1"
    nums.add(new Integer(0));
    nums.add(new Integer(0));
    System.out.println(countZeroes(nums)); // prints "3"
}

public static int countZeroes(List<Integer> all) {
    // your code goes here

public static int countZeroes(List<Integer> all) {
    int found = 0;
    for(int i = 0; i < all.size(); i++) {
        if(all.get(i).intValue() == 0) {
            found++;
        }
    }
    return found;
}

Problem 1.2.5.

Suppose we have an ArrayList<String> variable words containing the following words.

Then we execute the following program fragment.

for(int i = 0; i < words.size(); i++) {
    if(words.get(i).substring(0, 1).equals("p")) {
        words.remove(i);
    }
}

What will then be in words?

Problem 1.2.6.

Write a class method named removePositives that takes a parameter that is a List of Integers, and which removes all positive values from the parameter list. With such a method, the below method would work as indicated.

public static void run() {
    List<Integer> n = new ArrayList<Integer>();
    n.add(new Integer(2));
    n.add(new Integer(-3));
    n.add(new Integer(5));
    n.add(new Integer(6));
    System.out.println(n.size()); // prints "4"
    removePositives(n);
    System.out.println(n.size()); // prints "1"
}

public static void removePositives(List<Integer> data) {
    int pos = 0;
    while(pos < data.size()) {
        if(data.get(pos).intValue() > 0) {
            data.remove(pos); // remove positive number
        } else {
            pos++;           // advance past non-positive
        }
    }
}

Problem 1.2.7.

Define a class named Integers whose instances represent collections of integer values. The class should define the following instance methods.

Integers()

(Constructor) Constructs an empty collection of integers.

void add(int a, int b, int d)

Adds to this collection all the integers starting at a and going up by d, but stopping (and not including) b. (The collection should include multiple copies when integers are added multiple times.)

int find(int q)

Returns the integer value in this collection that is closest to q; in case of a tie, the method can return either of the closest values. Recall that Math includes a class method named abs, which takes an integer as a parameter and returns its absolute value.

The following method illustrates how another class might use your Integers class.

public static void run() {
    Integers nums = new Integers();
    nums.add(5, 18, 5); // inserts 5, 10, 15
    nums.add(3, 12, 3); // inserts 3, 6, 9
    System.out.println(nums.find(8)); // prints "9"
    System.out.println(nums.find(50)); // prints "15"
}

public class Integers {
    private ArrayList<Integer> nums;

    public Integers() {
        nums = new ArrayList<Integer>();
    }

    public void add(int a, int b, int d) {
        for(int i = a; i < b; i += d) {
            nums.add(new Integer(i));
        }
    }

    public int find(int q) {
        int ret = nums.get(0).intValue();
        for(int i = 0; i < nums.size(); i++) {
            int x = nums.get(i).intValue();
            if(Math.abs(q - x) < Math.abs(q - ret)) {
                ret = q;
            }
        }
        return ret;
    }
}