Create a lab directory

Use the techniques you learned from the previous labs to create a suitable directory for this lab and start jEdit. You might consider opening a terminal and entering the following commands:

cd Documents/cse1020
mkdir lab06
cd lab06
jedit &

Collections

"A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers)."
-The Java Tutorials: Introduction to Collections

We look at collections in general in detail later in the course.

ArrayList

ArrayList is a class that represents a list of elements. Each element occupies a specific position in the list, and the positions are numbered (as integers) starting from zero up to N-1 where N is the number of elements in the list.

You can find the number of elements in the list using the size method.

You can add an element to the end of the list using the add method, specifying the element that you want to add.

You can get an element from the list using the get method, specifying the position of the element you want to retrieve.

You can replace an element in the list using the set method, specifying both the position of the element you want to replace and the element you want to use as the replacment.

Creating an ArrayList

The syntax for creating an ArrayList is somewhat different than creating objects like Fraction. When you create an ArrayList, you need to say what type of elements you want the list to contain. Here are several examples:

import java.util.ArrayList;

public class CreateArrayList
{
   public static void main(String[] args)
   {
      // create an empty list of Integer
      ArrayList<Integer> intList = new ArrayList<Integer>();

      // create an empty list of Double
      ArrayList<Double> doubleList = new ArrayList<Double>();

      // create an empty list of String
      ArrayList<String> stringList = new ArrayList<String>();

      // create an empty list of Fraction
      ArrayList<Fraction> fractionList = new ArrayList<Fraction>();
   }
}

Notice that ArrayList can only hold elements that are object references; you cannot create a list that holds primitives (int, double, etc.) If you want a list of int, you must create a list of Integer. Integer is a "wrapper" class that holds a primitive int value so that the primitive type can be treated as an object. You can use an Integer as you would an int; the compiler takes care of converting the Integer to an int for you.

You can read more about the wrapper classes here.

Using an ArrayList

Here is an example program that shows the basic functionality of ArrayList:

import java.io.PrintStream;
import java.util.ArrayList;

public class ExampleArrayList
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;

      // create an empty list of Integer
      ArrayList<Integer> t = new ArrayList<Integer>();

      // add three elements to the list
      t.add(100);
      t.add(200);
      t.add(300);

      // print the list
      out.println("list has elements: " + t);

      // size of the list?
      int sz = t.size();
      out.println("size of the list: " + sz);

      // print each element on a separate line
      out.println("list has elements:");
      for (int i = 0; i < sz; i++)
      {
         Integer elem = t.get(i);
         out.println(i + " : " + elem);
      }

      // replace the first element with -100
      t.set(0, -100);
      out.println("list with first element replaced: " + t);
   }
}

Inserting into a Sorted List: Creating a Sorted List

A classic programming problem is inserting an element into a sorted list such that the list remains in sorted order.

You might want to load the Java API into your browser before starting.

To study this problem, we need a sorted list of elements. Cut and paste the following (incomplete) program into your editor. Complete the for loop (shown in red) so that the list contains N random integers between 1 and MAX. Compile and run the program to make sure that it produces a sorted list of N integers.

import java.io.PrintStream;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Random;

public class RandomInts
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;
      
      // N is the number of elements in the initial list
      final int N = Integer.parseInt(args[0]);

      // the list
      ArrayList<Integer> list = new ArrayList<Integer>();

      // add N random integers between 1 and MAX to the list
      final int MAX = 100;
      Random rng = new Random();
      for ()
      {

      }

      // output the unsorted list
      out.println("unsorted: " + list);
      
      // sort the list
      Collections.sort(list);

      // output the sorted list
      out.println("sorted  : " + list);
   }
}

Inserting into a Sorted List: Finding the Position in the List

Suppose that we want to insert the number M into the sorted list such that the list remains in sorted order. The first thing we need to do is to find the position in the list to insert M.

The position in the list to insert M is the first position where M is less than or equal to the element currently located at that position. If M is larger than every element in the list, then the correct position is position N (the position one past the end of the list).

Add to your program the code shown below in blue and red. Fill in the loop (shown in red) so that position is set to the correct position in the list to insert M. Compile and run your program to make sure that you are finding the correct position.

import java.io.PrintStream;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Random;

public class RandomInts
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;
      
      // N is the number of elements in the initial list
      final int N = Integer.parseInt(args[0]);

      // the list
      ArrayList<Integer> list = new ArrayList<Integer>();

      // add N random integers between 1 and MAX to the list
      final int MAX = 100;
      Random rng = new Random();
      for ()
      {

      }

      // output the unsorted list
      out.println("unsorted: " + list);
      
      // sort the list
      Collections.sort(list);

      // output the sorted list
      out.println("sorted  : " + list);

      // M is the number that we want to insert into the list
      final int M = Integer.parseInt(args[1]);

      // find the position in the list to insert M
      int position = N;
      for ()
      {




      }
      out.println(position);
   }
}

Inserting into a Sorted List: Inserting the Element into the List

Add to your program the code shown below in blue and red. Fill in the loop (shown in red) to perform Step 2 shown in the previous section. Compile and run your program to make sure that the final list contains the new element and is still in sorted order.

import java.io.PrintStream;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Random;

public class RandomInts
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;
      
      // N is the number of elements in the initial list
      final int N = Integer.parseInt(args[0]);

      // the list
      ArrayList<Integer> list = new ArrayList<Integer>();

      // add N random integers between 1 and MAX to the list
      final int MAX = 100;
      Random rng = new Random();
      for ()
      {

      }

      // output the unsorted list
      out.println("unsorted: " + list);
      
      // sort the list
      Collections.sort(list);

      // output the sorted list
      out.println("sorted  : " + list);

      // M is the number that we want to insert into the list
      final int M = Integer.parseInt(args[1]);

      // find the position in the list to insert M
      int position = N;
      for ()
      {




      }
      out.println(position);

      // insert M into the list
      list.add(0);
      for ()
      {
         
      }
      list.set(position, M);
      
      out.println("final   : " + list);
   }
}

Submit

Submit your program using the command:

submit 1020 L06 RandomInts.java