UF 06: JAVA¶

Arrays and ArrayLists¶

Alta Formazione Professionale - ITT Marconi

February 2021

6.1. Array Creation and Access¶

In [1]:
int[] highScores = {5,2,7,8,2,4};
  • sequence of contiguous elements
  • fixed length
  • primitive and references types
  • mutable cells
  • fast read / write
  • access by index
  • memory efficient

1) Declaring and Creating an Array

In [2]:
int[] ratings;
In [3]:
System.out.println(ratings);

null
In [4]:
Arrays.toString(ratings)
Out[4]:
null

2) Using new to Create Arrays

In [5]:
ratings = new int[5];
In [6]:
System.out.println(ratings);

[I@7d86980e
In [7]:
System.out.println(Arrays.toString(ratings));

[0, 0, 0, 0, 0]
In [8]:
String[] titles = new String[5];
In [9]:
System.out.println(Arrays.toString(titles));

[null, null, null, null, null]
In [10]:
Integer[] durations = new Integer[5];  // boxed !
In [11]:
System.out.println(Arrays.toString(durations));

[null, null, null, null, null]

3) Initializer Lists to Create Arrays

In [12]:
String[] titles = {"Robocop", "Alien", "Terminator"};
In [13]:
System.out.println(Arrays.toString(titles));

[Robocop, Alien, Terminator]

4) Array length

In [14]:
System.out.println(titles.length)

3

5) Access and Modify Array Values

In [15]:
System.out.println(titles[0]);

Robocop
In [16]:
System.out.println(titles[0].charAt(2));

b
In [17]:
titles[0] = "Star Wars";
Arrays.toString(titles)
Out[17]:
[Star Wars, Alien, Terminator]
In [18]:
titles[1] = "Space Cowboys";
titles[2] = "Back to the Future";
Arrays.toString(titles);
Out[18]:
[Star Wars, Space Cowboys, Back to the Future]

What could possibly go wrong?¶

titles[3] = "Apollo 13";

---------------------------------------------------------------------------
java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
    at .(#51:1)
titles[-1] = "Don't Open the Door";

---------------------------------------------------------------------------
java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
    at .(#54:1)

titles[1] = 666;

|   titles[1] = 666;
incompatible types: int cannot be converted to java.lang.String

6.2. Traversing Arrays with For Loops¶

1) Index Variables

In [19]:
String[] titles = {"Robocop", "Alien", "Terminator", "Star Wars", "Back to the Future"};

for (int i = 0; i < titles.length; i++) {
    System.out.println(  titles[i] );
}

Robocop
Alien
Terminator
Star Wars
Back to the Future

6.3. Enhanced For-Loop (For-Each) for Arrays¶

In [20]:
String[] titles = {"Robocop", "Alien", "Terminator", "Star Wars", "Back to the Future"};

for (String s : titles) {
    System.out.println( s );
}

Robocop
Alien
Terminator
Star Wars
Back to the Future

Mutating or not?¶

int[] years = {1987, 1079, 1984, 1977, 1985};

for (int i=0; i < years.length; i++) {
    years[i] + 100;
}

// System.out.println( Arrays.toString(years) );
In [21]:
int[] years = {1987, 1079, 1984, 1977, 1985};

for (int i=0; i < years.length; i++) {
    years[i] = years[i] + 1000;
}
 
// System.out.println( Arrays.toString(years) );

Mutating or not?¶

In [22]:
int[] years = {1987, 1079, 1984, 1977, 1985};

for (int y : years) {
    y = y + 1000;
}
 
// System.out.println( Arrays.toString(years) );

Mutating or not?¶

In [23]:
String[] titles = {"Robocop", "Alien", "Terminator", "Star Wars", "Back to the Future"};

for (String s : titles) {
    s.toUpperCase();
}
 
// System.out.println( Arrays.toString(titles) );
In [24]:
String[] titles = {"Robocop", "Alien", "Terminator", "Star Wars", "Back to the Future"};

for (String s : titles) {
    s = s.toUpperCase();
}
 
// System.out.println( Arrays.toString(titles) );

Mutating or not?¶

In [25]:
String[] titles = {"Robocop", "Alien", "Terminator", "Star Wars", "Back to the Future"};

for (String s : titles) {
    s = "BOH";
}
 
// System.out.println( Arrays.toString(titles) );

Mutating or not?¶

In [26]:
import java.util.Date;

Date releases[] = { new Date(87, 6, 17), 
                    new Date(85, 4, 24), 
                    new Date(84, 9, 25), 
                    new Date(77, 4, 24),
                    new Date(85, 6, 2)
};

System.out.println( Arrays.toString(releases) + '\n');

for (int i=0; i < releases.length; i++) {    
    releases[i].setYear(releases[i].getYear() + 1000);
}

// System.out.println( Arrays.toString(releases) );

[Fri Jul 17 00:00:00 CEST 1987, Fri May 24 00:00:00 CEST 1985, Thu Oct 25 00:00:00 CET 1984, Tue May 24 00:00:00 CEST 1977, Tue Jul 02 00:00:00 CEST 1985]

Mutating or not?¶

In [27]:
Date releases[] = { new Date(87, 6, 17), 
                    new Date(85, 4, 24), 
                    new Date(84, 9, 25), 
                    new Date(77, 4, 24),
                    new Date(85, 6, 2)
};

System.out.println( Arrays.toString(releases) + '\n');

for (Date d : releases) {    
    d.setYear(d.getYear() + 1000);
}

// System.out.println( Arrays.toString(releases) );

[Fri Jul 17 00:00:00 CEST 1987, Fri May 24 00:00:00 CEST 1985, Thu Oct 25 00:00:00 CET 1984, Tue May 24 00:00:00 CEST 1977, Tue Jul 02 00:00:00 CEST 1985]

Can we use a while?¶

In [28]:
Date releases[] = { new Date(87, 6, 17), 
                    new Date(85, 4, 24), 
                    new Date(84, 9, 25), 
                    new Date(77, 4, 24),
                    new Date(85, 6, 2)
};


int i=0;

while (i < releases.length) {
    
    Date d = releases[i];
    d.setYear(d.getYear() + 1000);
    
    i++;
}

// System.out.println( Arrays.toString(releases) );

Mutating what?¶

We want an array with 5 dates having consecutive years

In [29]:
Date releases[] = new Date[5];

Date d = new Date();

for (int i = 0; i < releases.length; i++){

    d.setYear(80 + i); 
    d.setMonth(5);
    d.setDate(10);   // sets the day

    releases[i] = d;
}

// System.out.println( Arrays.toString(releases) );

Exercise - Dungeon¶

A knight explores a cavern in search of rare objects. As soon as he finds what he's looking for, he rejoices and goes back. We represent the dungeon as an array of strings. The variable goal holds the object to find. Write some code to PRINT the output.

  • DO NOT USE break !
  • The array may also not contain object to look for
explore("the treasure", 
        {"a rock","a trap","some swords", "the treasure","a spiderweb", "a bolete of the tombs"})

     Entering..
     Found a rock
     Found a trap
     Found some swords
     How lucky! I found a treasure.
     Going back!     
     Found some swords
     Found a trap
     Found a rock
     Exiting..
explore("the talisman of power", {"a trap","a bolete of the tombs","a spiderweb"});

   Entering..
   Found a trap
   Found a bolete of the tombs
   Found a spiderweb
   Alas, there is no treasure!
   Going back
   Found a spiderweb
   Found a bolete of the tombs
   Found a trap
   Exiting..
In [30]:
String goal = "the treasure"; 
String[] dungeon = {"a rock","a trap","some swords","the treasure","a spiderweb", "a bolete of the tombs"};

// goal = "the talisman of power";
// String[] dungeon = {"a trap","a bolete of the tombs","a spiderweb"};

// write here

7.1. Intro to ArrayLists¶

In [31]:
import java.util.ArrayList;

ArrayList<String> videogames = new ArrayList();

videogames.add("Prince of Persia");
videogames.add("Legend of Zelda");
videogames.add("Monkey Island");
videogames.add("Doom");

System.out.println(videogames);

[Prince of Persia, Legend of Zelda, Monkey Island, Doom]

mutable size¶

  • fast append at the end
  • fast remove from the end
In [32]:
videogames.remove(3);   // removing from right end is fast
Out[32]:
Doom
In [33]:
System.out.println(videogames);

[Prince of Persia, Legend of Zelda, Monkey Island]

ArrayList: array or list?¶

Internally, it's more like an array

ArrayList: fast read/write at index¶

In [34]:
videogames.get(1)
Out[34]:
Legend of Zelda
In [35]:
videogames.set(1, "Bubble bubble");  // returns the removed element
Out[35]:
Legend of Zelda
In [36]:
System.out.println(videogames);

[Prince of Persia, Bubble bubble, Monkey Island]

7.2. ArrayList Methods¶

videogames.size();   // 3

videogames.add("Street Fighter", 1)`  // inserts at arbitrary position, slow!

search methods¶

In [37]:
videogames.contains("Monkey Island");
Out[37]:
true
In [38]:
videogames.indexOf("Monkey Island");
Out[38]:
2
In [39]:
videogames.indexOf("Gioco del pippero");
Out[39]:
-1
In [40]:
videogames.remove("Monkey Island");    // only first occurrence !
Out[40]:
true
In [41]:
System.out.println(videogames);

[Prince of Persia, Bubble bubble]

ArrayList: TAKE AWAY ?¶

  • videogames.remove("Monkey Island");

  • videogames.remove(2);

  • videogames.remove(videogames.indexOf("Monkey Island"));

ArrayList: TAKE AWAY ?¶

if (videogames.contains("Monkey Island")){
    videogames.remove("Monkey Island");
}

ArrayList: TAKE AWAY ?¶

int i = videogames.indexOf("Monkey Island");

if (i != -1) {
    videogames.remove(i);
}

ArrayList: TAKE AWAY ?¶

In [42]:
import java.util.ArrayList;

ArrayList<String> videogames = new ArrayList<String>();

videogames.add("Prince of Persia");
videogames.add("Monkey Island");
videogames.add("Legend of Zelda");
videogames.add("Monkey Island");
videogames.add("Doom");
System.out.println(videogames);

[Prince of Persia, Monkey Island, Legend of Zelda, Monkey Island, Doom]

videogames.remove("Monkey Island");  
videogames.remove("Monkey Island");  
videogames.remove("Monkey Island");  

System.out.println(videogames);
In [43]:
videogames.remove("Monkey Island");  // removes first occurrence
videogames.remove("Monkey Island");  // removes second

videogames.remove("Monkey Island");  // no third occurrence, doesn't explode

System.out.println(videogames);

[Prince of Persia, Legend of Zelda, Doom]

ArrayList: TAKE AWAY ?¶

7.3. Traversing ArrayLists with Loops

for (String s : videogames){
    if ("Monkey Island".equals(s)){
        videogames.remove(s);
    }
}

Never remove nor add stuff to a sequence you are iterating with a for each

---------------------------------------------------------------------------
java.util.ConcurrentModificationException: null
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
    at .(#187:1)

ArrayList: TAKE AWAY! Algorithmic¶

In [44]:
import java.util.ArrayList;
ArrayList<String> videogames = new ArrayList<String>();
videogames.add("Prince of Persia");
videogames.add("Monkey Island");
videogames.add("Legend of Zelda");
videogames.add("Monkey Island");
videogames.add("Doom");

int i = videogames.indexOf("Monkey Island");

while (i != -1) {
    
    videogames.remove(i);
    
    i = videogames.indexOf("Monkey Island");
}

System.out.println(videogames);

[Prince of Persia, Legend of Zelda, Doom]

ArrayList: TAKE AWAY! Guru¶

videogames.removeAll( Collections.singleton("MonkeyIsland") );

Need mutability?¶

What happens when you allow people to write on stuff you own?

graffiti1

Don't need mutability? - 'unmodifiable' views¶

fenced-house.jpg

Don't need mutability? - 'unmodifiable' views¶

In [45]:
import java.util.ArrayList;
ArrayList<String> videogames = new ArrayList();

videogames.add("Prince of Persia");
videogames.add("Legend of Zelda");
videogames.add("Monkey Island");
Out[45]:
true
In [46]:
List<String> myView = Collections.unmodifiableList(videogames);

myView.get(1);
Out[46]:
Legend of Zelda

Don't need mutability? - 'unmodifiable' views¶

myView.add("Pong");

---------------------------------------------------------------------------
java.lang.UnsupportedOperationException: null
    at java.base/java.util.Collections$UnmodifiableCollection.add(Collections.java:1062)
    at .(#282:1)

Beware you can still change original array!!!

In [47]:
videogames.add("Diablo");
Out[47]:
true
In [48]:
myView
Out[48]:
[Prince of Persia, Legend of Zelda, Monkey Island, Diablo]

Don't need mutability? Java 9 style¶

In [49]:
// Java 9

List<String> computers = List.of("Apple II", "Commodore 64",  "Amiga 500", "486");  

computers.getClass();
Out[49]:
class java.util.ImmutableCollections$ListN
In [50]:
computers.get(1);
Out[50]:
Commodore 64
computers.set(1, "Vic 20");

---------------------------------------------------------------------------
java.lang.UnsupportedOperationException: null
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:127)
    at java.base/java.util.ImmutableCollections$AbstractImmutableList.set(ImmutableCollections.java:160)
    at .(#252:1)
  • ImmutableCollections
  • thread safe
  • very good for concurrent code !

Don't need mutability? Java 9 style from list¶

In [51]:
import java.util.ArrayList;
ArrayList<String> videogames = new ArrayList();

videogames.add("Prince of Persia");
videogames.add("Legend of Zelda");
videogames.add("Monkey Island");


// ugly new String[0] tells java the type ..

List<String> imm = List.of(videogames.toArray(new String[0]));

imm.add("Pong");
---------------------------------------------------------------------------
java.lang.UnsupportedOperationException: null
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:127)
    at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:131)
    at .(#331:1)
In [52]:
videogames.add("Diablo II");

System.out.println(videogames); // changed

[Prince of Persia, Legend of Zelda, Monkey Island, Diablo II]
In [53]:
System.out.println(imm);       // no change

[Prince of Persia, Legend of Zelda, Monkey Island]

Truly immutable ?¶

In [54]:
import java.util.Date;

List<String> computers = List.of("Apple II",       "Commodore 64",      "Amiga 500");  
    
List<Date>   releases  = List.of(new Date(77,5,1), new Date(82,07,1),  new Date(87,03,1));

System.out.println(releases);

[Wed Jun 01 00:00:00 CEST 1977, Sun Aug 01 00:00:00 CEST 1982, Wed Apr 01 00:00:00 CEST 1987]
In [55]:
releases.get(0).setYear(3077);

System.out.println(releases);

[Sun Jun 01 00:00:00 CEST 4977, Sun Aug 01 00:00:00 CEST 1982, Wed Apr 01 00:00:00 CEST 1987]

Truly immutable !¶

In [56]:
import java.time.LocalDate;   // java 8, good stuff

List<LocalDate> releases = List.of(LocalDate.of(1977, 6, 1), 
                                   LocalDate.of(1982, 8, 1), 
                                   LocalDate.of(1987, 4, 1));

//releases.get(0).setYear(3077)  // impossible !

System.out.println(releases);

[1977-06-01, 1982-08-01, 1987-04-01]

Prefer immutable stuff if you:¶

  • use it in many places
  • small data structure
  • you have concurrent threads
  • pass it to untrusted people (your collegues...)
  • don't have to change it too often

Immutability downsides¶

  • java is historically mutability-oriented
  • reconstructing objects from file may be hard
  • not all your colleagues may like it

Exercise: Travelbook¶

Suppose you visited the attic and found a stack of books, which we represent as a list of strings. Each string is prefixed by a label of one character indicating the category (D for Detective story, T for Travel, H for History)

Since we are passionate about travel books, we want to examine stack one book at a time to transfer books into another pile we call ŧravel, which at the beginning is empty. We start from the top book in stack, and transfer into travel only the books starting with the label T like ("T-Australia")

The non-travel books are not interesting and must be discarded.

In [57]:
public static void travelbook(){
    ArrayList<String> stack = new ArrayList();
    stack.add("H-Middle Ages");   // <---- bottom
    stack.add("T-Australia");
    stack.add("T-Scotland");
    stack.add("D-Suspects");
    stack.add("T-Caribbean");     // <---- top

    ArrayList<String> travel = new ArrayList();
}

Write some code that produces the following print:

At the beginning:
    stack:   ["H-Middle Ages", "T-Australia", "T-Scotland", "D-Suspects", "T-Caribbean"]
    travel: []
Taken T-Caribbean
    stack:   ["H-Middle Ages", "T-Australia", "T-Scotland", "D-Suspects"]
    travel: ["T-Caribbean"]
Discarded D-Suspects
    stack:   ["H-Middle Ages", "T-Australia", "T-Scotland"]
    travel: ["T-Caribbean"]
Taken T-Scotland
    stack:   ["H-Middle Ages", "T-Australia"]
    travel: ["T-Caribbean", "T-Scotland"]
Taken T-Australia
    stack:   ["H-Middle Ages"]
    travel: ["T-Caribbean", "T-Scotland", "T-Australia"]
Discarded H-Middle Ages
    stack:   []
    travel: ["T-Caribbean", "T-Scotland", "T-Australia"]

Exercise - Bang!¶

There are two stacks of objects right_stack and left_stack which we represent as lists of strings. A cowboy shoots the objects at the top of the stacks, alternating the stack at each shoot. The cowboy always hits the target, so each shot decreases a stack.

  • Suppose the objects on top are the ones at the end of the list
  • To keep track of which stack to hit, use a variable shoot holding either "R" or "L" character
  • After each shot the cowboy if possible changes the stack , otherwise keeps shooting at the same stack until it’s empty.
  • your code must work for any stack and initial shot

Example - given:

In [58]:
public static void bang(){     
    ArrayList<String> left_stack = new ArrayList();
    left_stack.add("box");
    left_stack.add("boot");
    left_stack.add("horseshoe");
    left_stack.add("bucket");

    ArrayList<String> right_stack = new ArrayList();
    left_stack.add("bin");
    left_stack.add("saddle");
    left_stack.add("tin can");
    
    String shoot = "R";
    
    // write here
}

after your code, it must print:

Ready?
   left_stack: ["box", "boot", "horseshoe", "bucket"]
  right_stack: ["bin", "saddle", "tin can"]
BANG! right:  tin can
   left_stack: ["box", "boot", "horseshoe", "bucket"]
  right_stack: ["bin", "saddle"]
BANG! left:   bucket
   left_stack: ["box", "boot", "horseshoe"]
  right_stack: ["bin", "saddle"]
BANG! right:  saddle
   left_stack: ["box", "boot", "horseshoe"]
  right_stack: ["bin"]
BANG! left:   horseshoe
   left_stack: ["box", "boot"]
  right_stack: ["bin"]
BANG! right:  bin
   left_stack: ["box", "boot"]
  right_stack: []
BANG! left:   boot
   left_stack: ["box"]
  right_stack: []
Nothing to shoot on the right!
   left_stack: ["box"]
  right_stack: []
BANG! left:   box
   left_stack: []
  right_stack: []

7.4. ArrayList Algorithms¶

1) Free Response - String Scramble B

2) Free Response - Climbing Club A

3) Free Response - Climbing Club B

4) Free Response - Climbing Club C

5) Free Response - CookieOrder A

6) Free Response - CookieOrder B

7) Free Response - StringFormatter A

8) Free Response - StringFormatter B

9) Free Response - Delimiters A

10) Free Response - Delimiters B

11) Free Response - Grid World A (Not Complete)

7.5. Searching Algorithms¶

1) Sequential Search

2) Binary Search

3) Runtimes

4) Programming Challenge : Search Runtimes

5) Summary

7.6. Sorting Algorithms - SKIP IT !¶

1) Selection Sort no 2) Insertion Sort no 3) Programming Challenge : Sort Runtimes no

7.7. Ethics of Data Collection and Data Privacy - SKIP IT !¶

1) POGIL Groupwork: Data Privacy

2) Summary