ArrayLists

The code for this part of the lecture can be found here.

The data structures we used so far in this course are sequential. For example, consider a list. In order to find an element one has to traverse the whole list until the desired element is found. Java gives to its programmers the opportunity to use a more "direct access" style of data organization called ArrayList. In this data structure, each element has its own index and can be easily accessed and modified.

ArrayList is implemented by the generic class of the java.util package:

class ArrayList<T>{...}

The constructor ArrayList<T>() creates a new empty ArrayList of elements of type T.

This class also provides numerous methods to process an ArrayList:

Let's try to make some ArrayList examples.

We will use objects from the Student Class to fill in our ArrayLists:

// to represent a student in our class 
class Student { 
  String name; 
  String lab; 
  int ssid; 

  public Student(String name, String lab, int ssid){ 
    this.name = name; 
    this.lab = lab; 
    this.ssid = ssid; 
  }

  public String toString(){  
    return new String(" Name : " + this.name +  ", " +
                      " Lab  : " + this.lab  +  ", " + 
                      " SSID : " + this.ssid ); 
  } 

}

Now we can create our examples using the default constructor and the add method:

  // Students 
  Student skotthe = new Student("Theo", "A", 1234); 
  Student chadwick = new Student("Bryan", "B", 3456); 
  Student dimvar = new Student("Dimitris", "C", 7890); 
  Student chrdimo = new Student("Christos", "D", 1122); 
  Student mthomas = new Student("Mike", "A", 3344); 

  // ArrayLists 
  ArrayList al0; 
  ArrayList al1; 
  ArrayList al2;
  ArrayList al3;
  ArrayList al4;
  ArrayList al5;

  
 
    al0 = new ArrayList(); 
    al1 = new ArrayList(); 
    al1.add(skotthe); 

    al2 = new ArrayList(); 
    al2.add(skotthe); 
    al2.add(chadwick); 

    al3 = new ArrayList(); 
    al3.add(skotthe); 
    al3.add(chadwick); 
    al3.add(dimvar); 

    al4 = new ArrayList(); 
    al4.add(skotthe); 
    al4.add(chadwick); 
    al4.add(dimvar); 
    al4.add(chrdimo); 

    al5 = new ArrayList(); 
    al5.add(skotthe); 
    al5.add(chadwick); 
    al5.add(dimvar); 
    al5.add(chrdimo); 
    al5.add(dimvar); 

Each cell of an ArrayList contains a reference to an object. So, from the previous examples, al5 looks something like this:

 |-------|--------|-------|-------|-------| 
 |   |   |   |    |   |   |   |   |   |   |
 |---|---|---|----|---|---|---|---|---|---|
     |       |        |       |       | 
     V       V        |       V       |
  skotthe chadwick    |    chrdimo    |
                      +---------------+ 
		      | 
                      V
		    dimvar

We can also play around with the methods provided by the ArrayList Class to create a swap method:

    //swaps the contents of indexes i and j in al
    public <T> void swap(int i, int j, ArrayList<T> al){ 
     
     T tmp=al.get(i);
     al.set(i, al.get(j));
     al.set(j, tmp);     

  }

In the body of swap, we use a local variable tmp to temporally store the content of the i-th position of al. Then we move the content of the j-th position in the i-th position and finally set as new content of the j-th position the content of tmp. Mutation shows its power!

This can also been done differently without the extra local variable:

 public <T> void cuteswap(int i, int j, ArrayList<T> al){ 
     
     al.set(i,al.set(j, al.get(i)));
  } 

Here we take advantage of the fact that set returns the former content of the j-th position. So we can simply move it to the i-th posistion.