COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 5-1: Arraylist
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
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];
myInts[3] = -732;
0
0
0
-732
:
0
0
0 1 2
myInts 3 :
14
Shape[] myShapes = new Shape[428]; shapes[293] = new Shape( );
null
null
null
null
null
null
myShapes
0 1
:
293 : 427
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) set(i, e) add(e) add(i, e) remove(i) remove(e)
clear() isEmpty() size()
// Returns the i-th element (but doesn’t remove it) // Replaces the i-th element with e
// Append element e at the end of the list
// Inserts element e into the i-th position
// Removes the i-th element from list
// Removes first occurrence of element e // from the list (if it is there)
// Empties the list.
// Returns true if empty, false if not empty. // Returns number of elements in the list
IMPLEMENTATIONS
There are different implementations of a list: Array list
Singly linked list Doubly linked list
next two videos
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:
• Use an array to store the elements of the list
• Keep track of how many elements we have 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.java
public class ArrayList {
private Shape[] arr;
private int size;
: }
ARRAYLIST
Idea:
• Use an array to store the elements of the list
• Keep track of how many elements we have inserted in the list
To decide:
• 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.
ArrayList.java
public class ArrayList {
private Shape[] arr;
private int size;
public ArrayList() {
arr = new Shape[10];
size = 0;
}
: }
EXAMPLE
ArrayList.java
public class ArrayList { private Shape[] arr; private int size;
public ArrayList() {
arr = new Shape[10];
size = 0;
} }
null
null
null
null
null
null
null
null
null
null
list
0 1
2 arr 3
size 4 5
6 7
8 9
0
ArrayList list = new ArrayList();
EXAMPLE – WHAT WE WANT WHEN ADDING ELEMENTS
ArrayList.java
public class ArrayList { private Shape[] arr; private int size;
public ArrayList() {
arr = new Shape[10];
size = 0;
} }
null
null
null
null
null
null
null
null
null
null
list
0 1
2 arr 3
size 4 5
6 7
8 9
52471360
ArrayList list = new ArrayList();
// add 7 elements…
HOW TO IMPLEMENT VARIOUS OPERATIONS? – get() Returns the element at the specified position in this list.
public class ArrayList {
private Shape[] arr;
private int size;
:
public Shape get(int i) { if( )
return arr[i];
// otherwise?
} }
i>=0 && i
// creates an arraylist of shapes with initial capacity 23
ArrayList
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:
Note that these classes have static methods/attributes that you might have already used. For example: Integer.MAX_VALUE, Double.parseDouble()
Integer x = 5;
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;
https://docs.oracle.com/javase/tutorial/java/data/autoboxing.html
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) {
System.out.println(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.
In the next videos: Linked lists