List Interface

A List is a collection that holds its elements in numbered sequence. List supports:

• Positional access/mutation : manipulates elements based on their numerical position in the list
• Search : searches for a specified object in the list and returns its numerical position
• Iteration : extends Iterator semantics to take advantage of the list's sequential nature
• Range-view : performs arbitrary range operations on the list

List Interface

public interface List<E> extends Collection<E> 
{
    // Positional access
    E get(int index);
    E set(int index, E element);         //optional
    boolean add(E element);              //optional
    void add(int index, E element);      //optional
    E remove(int index);                 //optional
    boolean addAll(int index,
        Collection<? extends E> c );     //optional

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Iteration
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    // Range-view
    List<E> subList(int from, int to);
}

It would be a good idea to read the List API http://download.oracle.com/javase/6/docs/api/java/util/List.html.

Creating a List

To create a list, you need a class that implements List. Usually, you will want to use ArrayList; the other choice is LinkedList.

// an empty list of Integer
List<Integer> numbers = new ArrayList<Integer>();

// an empty list of String
List<String> words = new ArrayList<String>();

// an empty list of Fraction
List<Fraction> fractions = new ArrayList<Fraction>();

// an empty list of lists of Double
List<List<Double>> matrix = new ArrayList<List<Double>>();

Adding to the End of a List

You use add to add to the end of the list.

List<Integer> numbers = new ArrayList<Integer>();

numbers.add(new Integer(0));
numbers.add(new Integer(10));
numbers.add(20);

Notice how auto-boxing allows you to add an int even though numbers is a list of Integer.

Getting Elements from a List

You use get to retrieve an element using an index from a list.

List<Integer> numbers = new ArrayList<Integer>();

numbers.add(new Integer(0));
numbers.add(new Integer(10));
numbers.add(20);

for (int i = 0; i < numbers.size(); i++)
{
   Integer elem = numbers.get(i);
   output.println(elem);
}
output.println("---");

The above code fragment outputs:

0
10
20
---

Adding into the Middle of a List

You use the overloaded version of add to add an element into the list at a specified index; the existing elements get shifted one index upwards.

List<Integer> numbers = new ArrayList<Integer>();

numbers.add(new Integer(0));
numbers.add(new Integer(10));
numbers.add(20);

for (int i = 0; i < numbers.size(); i++)
{
   output.println(numbers.get(i));
}
output.println("---");

numbers.add(1, new Integer(5));

for (int i = 0; i < numbers.size(); i++)
{
   output.println(numbers.get(i));
}

The above code fragment outputs:

0
10
20
---
0
5
10
20

List Example: Rolling Dice

If you roll two dice what are the odds of rolling a given number?

Solution: try all 6x6 = 36 possible rolls and compute the sum for each roll. Store the result in a table like this:

List Example: Rolling Dice

final int SIZE = 13;
List<Integer> roll = new ArrayList<Integer>(SIZE);

// initialize all elements to 0
for (int i = 0; i < SIZE; i++)
{
   roll.add(0);
}

final int MIN = 1;
final int MAX = 6;

for (int dice1 = MIN; dice1 <= MAX; dice1++)
{
   for (int dice2 = MIN; dice2 <= MAX; dice2++)
   {
      int sum = dice1 + dice2;
      int oldSum = roll.get(sum);
      roll.set(sum, oldSum + 1);
   }
}

See Dice.java.

List Example: Coin-flipping

If you flip a fair coin N times how many heads do you expect to see? How often do you expect to see N / 4 heads?

You could solve the problem using statistics (google "binomial distribution"), or you could write a simulation.

Solution: simulate flipping a coin N times, repeat M times, and store the results in a table like this:

Coin-flipping Simulation

1. Create a list heads of length N + 1.
2. Fill heads with all zeros
3. Repeat the following M times:
   1. Repeat the following N times:
      1. Generate a random boolean (true : heads, false : tails); keep track of the number of heads n
   2. Add 1 to element at index n in heads

Coin-flipping Simulation

final int M = 100000;
final int N = 20;

List<Integer> heads = new ArrayList<Integer>();
for (int i = 0; i <= N; i++)
{
   heads.add(0);
}

Random rng = new Random();
for (int trial = 0; trial < M; trial++)
{
   int count = 0;
   for (int flip = 0; flip < N; flip++)
   {
      if (rng.nextBoolean())
      {
         count++;
      }
   }
   int index = count;
   int oldCount = heads.get(index);
   heads.set(index, oldCount + 1);
}

See CoinFlip.java.

Check if a List is Sorted

Sorted lists are very useful; how can you tell if an existing list is already sorted in ascending order (from smallest to largest)?

A list is sorted if:
element (i) is less than or equal to element (i + 1) for i = 0, 1, ..., (size - 2).

Check if a List is Sorted

In this case, you cannot correctly use <= with object references, but you can use compareTo.

// t is a List<E> where E implements Comparable<E>

boolean isSorted = true;
for (int i = 0; i < t.size() - 1; i++)
{
   isSorted = isSorted &&
              t.get(i).compareTo(t.get(i + 1)) <= 0; 
}

or perhaps more pragmatically:

// t is a List<E> where E implements Comparable<E>

boolean isSorted = true;
for (int i = 0; i < t.size() - 1; i++)
{
   if (t.get(i).compareTo(t.get(i + 1)) > 0)
   {
      isSorted = false;
      break;
   }
}

Bogosort

Bogosort is a perversely awful sorting algorithm; its complexity is O(N ⋅ N!).

while the list is not sorted
   randomly shuffle the elements in the list

Bogosort

Unfortunately, this algorithm is easy to implement in Java using Collections.shuffle.

boolean isSorted = false;
while (!isSorted)
{
   Collections.shuffle(t);
   
   // this part checks for sorted order
   isSorted = true;
   for (int i = 0; i < t.size() - 1; i++)
   {
      isSorted = isSorted &&
                 t.get(i).compareTo(t.get(i + 1)) <= 0; 
   }
}

See BogoSort.java.

Bozosort

Bozosort is another perversely awful sorting algorithm; its complexity is O(N!).

while the list is not sorted
   pick two elements at random and swap them

Bozosort

Like bogosort, bozosort is easy to implement in Java.

// t is a List<Integer>

Random rng = new Random();

boolean isSorted = false;
while (!isSorted)
{
   int index1 = rng.nextInt(t.size());
   int index2 = rng.nextInt(t.size());

   Integer tmp = t.get(index1);
   t.set(index1, t.get(index2));
   t.set(index2, tmp);
   
   // this part checks for sorted order
   isSorted = true;
   for (int i = 0; i < t.size() - 1; i++)
   {
      isSorted = isSorted &&
                 t.get(i).compareTo(t.get(i + 1)) <= 0; 
   }
}

See BozoSort.java.

Collections.sort

You should use the java.util.Collections utility class for sorting:

// t is a List<E> where E extends Comparable<? super E>

Collections.sort(t);

The time complexity is O(n log n)