COMP 250

INTRODUCTION TO COMPUTER SCIENCE

11 - Arraylist

Giulia Alberini, Fall 2022

ANNOUNCEMENTS

 Classes cancelled on Oct. 3rd

 INSTEAD:
Info session with the TAs on Internship
HOW/WHERE/WHEN/WHAT DO YOU NEED TO KNOW

 Where: LEA 26
 When: Oct. 3rd – 10:35am
 We will also have a quick interview demo + into on your oral
presentations.
WHAT ARE WE GOING TO DO TODAY?

 Arraylist
ARRAY LISTS
 ARRAYS IN JAVA

 Arrays whose elements have a primitive type

int[] myInts = new int[15];

myInts[3] = -732;

 Arrays whose elements have a reference type

Shape[] myShapes = new Shape[428];

shapes[293] = new Shape( );
 int[] myInts = new int[15]; Shape[] myShapes = new Shape[428];
myInts[3] = -732; shapes[293] = new Shape( );

0 null
1 null
0 0 null
1 0 : null
2 0
myInts 3 -732 myShapes
:
293
:

0 :
14 0 null
427 null

You can think of an array as a block of consecutive slots in memory

ARRAYS HAVE CONSTANT TIME ACCESS

A computer accesses an element in an array in constant time

i.e. constant, independent of the length N of the array.

…. = a[k] ; // read

a[k] = …. ; // write

You will learn more about how this works in COMP 206 and 273.
LIST

An ordered set of elements

𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑁−1

𝑁 is the number of elements in the list, often called the “size” of

the list.
WHAT WOULD WE LIKE TO DO WITH A LIST?

get(i) // Returns the i-th element (but doesn't remove it)

set(i,e) // Replaces the i-th element with e
add(e) // Append element e at the end of the list
add(i,e) // Inserts element e into the i-th position
remove(i) // Removes the i-th element from list
remove(e) // Removes first occurrence of element e
// from the list (if it is there)
clear() // Empties the list.
isEmpty() // Returns true if empty, false if not empty.
size() // Returns number of elements in the list
IMPLEMENTATIONS

There are different implementations of a list:

 Array list
 Singly linked list next time!
 Doubly linked list
IMPLEMENTATIONS

There are different implementations of a list:

 Array list  Use an array to implement a list!
 Singly linked list
 Doubly linked list
 ARRAYLIST

Idea: [Link]

• Use an array to store the elements of the list public class ArrayList {
private Shape[] arr;
• Keep track of how many elements we have
private int size;
inserted in the list

:
To decide: }

• How big should the underlying array be when we

first create an object of type ArrayList?
(this is referred to as the initial capacity of the list)
 ARRAYLIST

Idea: [Link]

public class ArrayList {

• Use an array to store the elements of the list
private Shape[] arr;
• Keep track of how many elements we have private int size;
inserted in the list
public ArrayList() {
arr = new Shape[10];
To decide:
size = 0;
• How big should the underlying array be when we }
first create an object of type ArrayList? :
 Java’s ArrayList creates an array of length 10. }
 EXAMPLE
[Link]

public class ArrayList {

private Shape[] arr;
private int size; 0 null
1 null

public ArrayList() { 2 null

arr = new Shape[10]; arr 3 null

list
size = 0; 4 null
size 0
} 5 null
} 6 null
7 null
ArrayList list = new ArrayList(); 8 null
9 null
 EXAMPLE – WHAT WE WANT WHEN ADDING ELEMENTS
[Link]

public class ArrayList {

private Shape[] arr;
private int size; 0
1

public ArrayList() { 2
arr = new Shape[10]; arr 3
list
size = 0; 4
size 5
2
1
4
7
0
3
6
} 5
} 6
7 null
ArrayList list = new ArrayList(); 8 null
// add 7 elements… 9 null
 HOW TO IMPLEMENT VARIOUS OPERATIONS? – get()
Returns the element at the specified position in this list.

public class ArrayList {

private Shape[] arr; 0
private int size; 1
2
: arr 3
list
4
public Shape get(int i) { size 7
5
if( i>=0 && i<size )
6
return arr[i];
7 null
// otherwise?
8 null
}
9 null
}
 HOW TO IMPLEMENT VARIOUS OPERATIONS? – get()
Returns the element at the specified position in this list.

public class ArrayList {

private Shape[] arr; 0
private int size; 1
2
: arr 3
list
4
public Shape get(int i) { size 7
5
if( i>=0 && i<size )
6
return arr[i];
7 null
// otherwise?
throw new IndexOutOfBoundsException();
8 null
}
I will not mention this for all the other methods
9 null
} today, but it should be added for proper
implementations.
 HOW TO IMPLEMENT VARIOUS OPERATIONS? – set()
Replaces the element at the specified position in this list with the specified element.

public class ArrayList {

private Shape[] arr;
private int size; 0
1
: 2
arr 3
public Shape set(int i, Shape e) list
4
{ size 7
if(i>=0 && i<size) { 5
Shape tmp = arr[i]; 6
arr[i] = e; For example: 7 null
return tmp; [Link](5,e); 8 null
}
9 null
} e
}
 HOW TO IMPLEMENT VARIOUS OPERATIONS? – add()
Appends the specified element to the end of this list.

public class ArrayList { 0

private Shape[] arr;
1
private int size;
2

: arr 3
list
4
size 7
public void add(Shape e) 5
{
6
arr[size] = e;
For example: 7 null
size = size + 1;
[Link](e); 8 null
}
} 9 null

What if the array arr is full? e

 HOW TO IMPLEMENT VARIOUS OPERATIONS? – add()
Appends the specified element to the end of this list.

public class ArrayList { 0

private Shape[] arr;
1
private int size;
2

: arr 3
list
4
size 7
public void add(Shape e) 5
{
6
arr[size] = e;
For example: 7 null
size = size + 1;
[Link](e); 8 null
}
} 9 null

What if the array arr is full? e

HOW TO IMPLEMENT VARIOUS OPERATIONS? – add()
Appends the specified element to the end of this list.

What if the array arr is already full?

public void add(Shape e) {
if ([Link] == size)
resize();
arr[size] = e;
size = size + 1;
}

private void resize() {

Shape[] bigger = new Shape[[Link]*2]; // example
for(int i=0; i < size; i++) {
bigger[i] = arr[i];
}
arr = bigger;
}
HOW TO IMPLEMENT VARIOUS OPERATIONS? – add()
Appends the specified element to the end of this list.

What if the array arr is already full?

public void add(Shape e) {
if ([Link] == size)
resize();
arr[size] = e;
size = size + 1;
}

private void resize() {

Shape[] bigger = new Shape[[Link]*2]; // example
for(int i=0; i < size; i++) {
bigger[i] = arr[i];
}
arr = bigger;
}
OVERLOADING

add( e ) // inserts element e at end of list

add( i ,e) // Inserts element e into the i-th position

remove(i) // Removes the i-th element from list

remove(e) // Removes first occurrence of element e
// from the list (if it is there)
 HOW TO IMPLEMENT add(i,e)
Inserts the specified element at the specified position in the list.

For example:
[Link](3, e);
e
0
1
2
arr 3
list
4
size 7
5
6
7 null
8 null
9 null
 HOW TO IMPLEMENT add(i,e)
Inserts the specified element at the specified position in the list.

IDEA: make room by shifting the elements, then add e

For example:
[Link](3, e);
e
0
1
2
arr 3
list
4
size 8
5
6
7
8 null
9 null
HOW TO IMPLEMENT add(i,e)
Inserts the specified element at the specified position in the list.

public void add(int i, Shape e) {

// Throw exception if i is out of bounds

// Resize if not enough space

// Shift elements down

// Add the new element

}
ADDING N ELEMENTS TO AN ARRAY LIST

Suppose we initialize an array list with an empty array of length 1.

We then add an element.

arraylist of arraylist of
size 0 size 1
(length 1) (length 1) What do we do to add
a second element?

add first
element
ADDING N ELEMENTS TO AN ARRAY LIST

Suppose each time we add to a full array list, we double the length of
the array.

arraylist of arraylist of arraylist of

size 1 size 1 size 2
(length 1) (length 2) (length 2)

add second
element
ADDING N ELEMENTS TO AN ARRAY LIST

arraylist of arraylist of arraylist of

size 2 size 2 size 3
(length 2) (length 4) (length 4)

add third element

ADDING N ELEMENTS TO AN ARRAY LIST

arraylist of arraylist of
size 3 size 4
(length 4) (length 4)

add fourth
element
ADDING N ELEMENTS TO AN ARRAY LIST

. arraylist of arraylist of arraylist of

size 4 size 4 size 5
(length 4) (length 8) (length 8)

add fifth element

 ADDING N ELEMENTS TO AN ARRAY LIST

Double length and Double length and Double length and

copy one element copy two elements copy four elements

add two elements add 3-4 elements add 5-8 elements

Q: How many times 𝑘 do we need to double the length of
the array so that it is of length 𝑁 ?

A:

Q: How many copy operations are required to add N

elements to an empty array list ?

A:
Q: How many times 𝑘 do we need to double the length of
the array so that it is of length 𝑁 ?

A: 2 ⋅ 2 ⋯ 2 = 2𝑘 = 𝑁 → 𝑘 = log 2 𝑁

Q: How many copy operations are required to add N

elements to an empty array list ?

A:
Q: How many times 𝑘 do we need to double the length of
the array so that it is of length 𝑁 ?

A: 2 ⋅ 2 ⋯ 2 = 2𝑘 = 𝑁 → 𝑘 = log 2 𝑁

Q: How many copy operations are required to add N

elements to an empty array list ?

1−2𝑘
A: 1 + 2 + 4 + … + 2𝑘−1
= σ𝑘−1
𝑖=0 2𝑖
= = 2𝑘 − 1 = 𝑁 − 1
1−2
 SERIES

 Geometric series
𝑛
1 − 𝑥 𝑛+1
෍ 𝑥𝑖 = 1 + 𝑥 + 𝑥2 + ⋯ + 𝑥𝑛 =
1−𝑥
𝑖=0

 Arithmetic series
𝑛
1
෍𝑖 = 1 +2 + ⋯+ 𝑛 = 𝑛 𝑛 + 1
2
𝑖=1
Q: How many times 𝑘 do we need to double the length of
the array so that it is of length 𝑁 ?

A: 2 ⋅ 2 ⋯ 2 = 2𝑘 = 𝑁 → 𝑘 = log 2 𝑁

Q: How many copy operations are required to add N

elements to an empty array list ?

1−2𝑘
A: 1 + 2 + 4 + … + 2𝑘−1
= σ𝑘−1
𝑖=0 2𝑖
= = 2𝑘 − 1 = 𝑁 − 1
1−2
 JAVA ARRAYLIST CLASS

[Link]

 It uses an array as the underlying data structure

 It grows the array (by 50%, not 100%) when the array is full and a new element is
added.

 As a client, we don’t have access to the fields directly. We need to use the methods
provided (get(), set(), …) to manipulate the list.
JAVA ARRAYLIST – GENERIC CLASS

 ArrayList is a generic class with a type parameter.

 When you create an object of type ArrayList you specify the

type of the elements stored by the list by appending to
ArrayList a class name enclosed in angle brackets.
If we write int instead we
 Example: get a compile-time error!

// creates an arraylist of integers with initial capacity 10

ArrayList<Integer> words = new ArrayList<Integer>();

// creates an arraylist of shapes with initial capacity 23

ArrayList<Shape> myShapes = new ArrayList<Shape>(23);
 WRAPPER CLASSES

 Integer, Double, and Character wrap a value of the primitive type int,
double, and char (respectively) in an object. Thus, they turn primitive types
into reference types.

 The conversion between the primitive types and their wrappers is done
automatically. For example, the following would not cause a compile-time
error:
Integer x = 5;

 Note that these classes have static methods/attributes that you might have
already used. For example: Integer.MAX_VALUE, [Link]()
AUTOBOXING AND UNBOXING

 Autoboxing is the automatic conversion that the Java compiler makes

between the primitive types and their corresponding object wrapper
classes. For example converting an int to an Integer.

Integer x = 5;

 If the conversion goes the other way, this is called unboxing.

Integer x = new Integer(5);

int y = x;

 [Link]
IMMUTABLE TYPES

 Note that Integer, Double, and Character are

immutable reference types (like String).

 As with String, you can appear to updates values, but

you are never changing the actual Object. A new
Object gets created each time we “change” a value.
WHY WRAPPER CLASSES?

It is much simpler (in terms of code re-use) to have

ArrayList require the input to be an Object (a reference
type), instead of using primitive types.

For example, all reference types can be compared using

.equals(), while we have to use == for primitive types.
THE FOREACH LOOP

int[] numbers = {1,2,3,4,5};

for(int element: numbers) {
[Link](element);
}

The foreach loop (also called enhanced for loop) can make
your code more readable and can be convenient to use. It is
not helpful when you need to refer to the index of an element.
Next time:
 Linked lists