Arrays and Lists
1
Lecture 7
CS61B, Spring 2024 @ UC Berkeley
Slides credit: Josh Hug
A Last Look at Linked Lists
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Doubly Linked Lists
Behold. The state of the art as we arrived at in last week’s lecture. Through various improvements, we made all of the following operations fast:
??
3
5
size
17
next
value
prev
addLast()
getLast()
get(int i)
removeLast()
38
sentinel
Arbitrary Retrieval
Suppose we added get(int i), which returns the ith item from the list.
Why would get be slow for long lists compared to getLast()? For what inputs?
??
3
5
size
17
next
value
prev
addLast()
getLast()
get(int i)
removeLast()
38
sentinel
Arbitrary Retrieval
Suppose we added get(int i), which returns the ith item from the list.
Why would get be slow for long lists compared to getLast()? For what inputs?
??
3
5
size
17
next
value
prev
addLast()
getLast()
get(int i)
removeLast()
38
sentinel
Arbitrary Retrieval
Suppose we added get(int i), which returns the ith item from the list.
Why would get be slow for long lists compared to getLast()? For what inputs?
??
3
5
size
17
next
value
prev
addLast()
getLast()
get(int i)
removeLast()
38
sentinel
Basic ArrayList Implementation
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Random Access in Arrays
Retrieval from any position of an array is very fast.
Our Goal: AList.java
Want to figure out how to build an array version of a list:
addLast()
getLast()
get(int i)
removeLast()
???
Let’s try it out...
??
3
5
size
17
next
value
prev
addLast()
getLast()
get(int i)
removeLast()
38
sentinel
SLList
AList
Coding Demo: Basic ArrayList Constructor
public class AList {
/** Creates an empty list. */
public AList() {
}
}
AList.java
Coding Demo: Basic ArrayList Constructor
public class AList {
private int size;
/** Creates an empty list. */
public AList() {
}
}
AList.java
Coding Demo: Basic ArrayList Constructor
public class AList {
private int[] items;
private int size;
/** Creates an empty list. */
public AList() {
}
}
AList.java
Coding Demo: Basic ArrayList Constructor
public class AList {
private int[] items;
private int size;
/** Creates an empty list. */
public AList() {
items = new int[100];
}
}
AList.java
The choice of array size (100) was arbitrary. We'll fix this limitation later.
Coding Demo: Basic ArrayList Constructor
public class AList {
private int[] items;
private int size;
/** Creates an empty list. */
public AList() {
items = new int[100];
size = 0;
}
}
AList.java
Coding Demo: Basic ArrayList addLast
public class AList {
private int[] items;
private int size;
/** Inserts x into the back of the list. */
public void addLast(int x) {
}
}
AList.java
Let's write a small example to help us think about addLast.
Coding Demo: Basic ArrayList addLast
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
6 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
6 | 9 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
size=0
size=1
size=2
size=3
What patterns do we spot?
The next item we want to add will go into position size.
Call constructor to get empty array.
addLast(6)
addLast(9)
addLast(-1)
Coding Demo: Basic ArrayList addLast
/** Invariants:
addLast: The next item we want to add, will go into position size
*/
public class AList {
private int[] items;
private int size;
/** Inserts x into the back of the list. */
public void addLast(int x) {
}
}
AList.java
Coding Demo: Basic ArrayList addLast
/** Invariants:
addLast: The next item we want to add, will go into position size
*/
public class AList {
private int[] items;
private int size;
/** Inserts x into the back of the list. */
public void addLast(int x) {
items[size] = x;
}
}
AList.java
Coding Demo: Basic ArrayList addLast
/** Invariants:
addLast: The next item we want to add, will go into position size
*/
public class AList {
private int[] items;
private int size;
/** Inserts x into the back of the list. */
public void addLast(int x) {
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Basic ArrayList getLast
/** Invariants:
addLast: The next item we want to add, will go into position size
*/
public class AList {
private int[] items;
private int size;
/** Returns the item from the back of the list. */
public int getLast() {
}
}
AList.java
Coding Demo: Basic ArrayList getLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
*/
public class AList {
private int[] items;
private int size;
/** Returns the item from the back of the list. */
public int getLast() {
}
}
AList.java
Coding Demo: Basic ArrayList getLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
*/
public class AList {
private int[] items;
private int size;
/** Returns the item from the back of the list. */
public int getLast() {
return items[size - 1];
}
}
AList.java
Coding Demo: Basic ArrayList get
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
*/
public class AList {
private int[] items;
private int size;
/** Gets the ith item in the list (0 is the front). */
public int get(int i) {
}
}
AList.java
Coding Demo: Basic ArrayList get
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
*/
public class AList {
private int[] items;
private int size;
/** Gets the ith item in the list (0 is the front). */
public int get(int i) {
return items[i];
}
}
AList.java
Coding Demo: Basic ArrayList size
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
*/
public class AList {
private int[] items;
private int size;
/** Returns the number of items in the list. */
public int size() {
}
}
AList.java
Coding Demo: Basic ArrayList size
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Returns the number of items in the list. */
public int size() {
}
}
AList.java
Coding Demo: Basic ArrayList size
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Returns the number of items in the list. */
public int size() {
return size;
}
}
AList.java
Naive AList Code
AList Invariants:
We could also add error checking code, e.g.
public class AList {
private int[] items;
private int size;
public AList() {
items = new int[100]; size = 0;
}
public void addLast(int x) {
items[size] = x;
size += 1;
}
public int getLast() {
return items[size - 1];
}
public int get(int i) {
return items[i];
}
public int size() {
return size;
}
}
From SLList lecture: “things that must be true”.
public int get(int i) {
if (i >= items.length) {
throw new IllegalArgumentException();
}
return items[i];
}
Naive AList Code
AList Invariants:
Let’s now discuss delete operations.
From SLList lecture: “things that must be true”.
public class AList {
private int[] items;
private int size;
public AList() {
items = new int[100]; size = 0;
}
public void addLast(int x) {
items[size] = x;
size += 1;
}
public int getLast() {
return items[size - 1];
}
public int get(int i) {
return items[i];
}
public int size() {
return size;
}
}
The Allegory of the Cave
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
The Abstract vs. the Concrete
When we removeLast(), which memory boxes need to change? To what?-
User’s mental model: {5, 3, 1, 7, 22, -1} → {5, 3, 1, 7, 22}
0
0
...
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
0
0
6
size
0 1 2 3 4 5 6 7 98 99
Actual truth:
Deletion: yellkey.com/look
When we removeLast(), which memory boxes need to change? To what?
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
0
0
0
0
0
...
6
size
0 1 2 3 4 5 6 7 97 98 99
AList invariants.
removeLast Implementation
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Deletion Debrief
When we removeLast(), which memory boxes need to change? To what?
AList invariants.
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
0
0
0
0
0
...
6
size
0 1 2 3 4 5 6 7 97 98 99
Coding Demo: Basic ArrayList removeLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Deletes item from back of list and returns deleted item. */
public int removeLast() {
}
}
AList.java
Coding Demo: Basic ArrayList removeLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Deletes item from back of list and returns deleted item. */
public int removeLast() {
int x = getLast();
}
}
AList.java
Coding Demo: Basic ArrayList removeLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Deletes item from back of list and returns deleted item. */
public int removeLast() {
int x = getLast();
return x;
}
}
AList.java
Coding Demo: Basic ArrayList removeLast
/** Invariants:
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1.
size: The number of items in the list should be size.
*/
public class AList {
private int[] items;
private int size;
/** Deletes item from back of list and returns deleted item. */
public int removeLast() {
int x = getLast();
size = size - 1;
return x;
}
}
AList.java
Naive AList Code
AList Invariants:
public int removeLast() {
int x = items[size - 1];
items[size - 1] = 0;
size -= 1;
return x;
}
Setting deleted item to zero is not necessary to preserve invariants, and thus not necessary for correctness.
public class AList {
private int[] items;
private int size;
public AList() {
items = new int[100]; size = 0;
}
public void addLast(int x) {
items[size] = x;
size += 1;
}
public int getLast() {
return items[size - 1];
}
public int get(int i) {
return items[i];
}
public int size() {
return size;
}
}
Note
What about get?
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
0
0
0
0
0
...
5
size
0 1 2 3 4 5 6 7 97 98 99
Resizing Array Theory
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
The Mighty AList
Key Idea: Use some subset of the entries of an array.
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
3
2
7
12
4
...
6
size
0 1 2 3 4 5 6 7 97 98 99
The Mighty (?) AList
Key Idea: Use some subset of the entries of an array.
What happens if we insert into the AList above? What should we do about it?
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
5
7
-1
5
7
...
100
size
0 1 2 3 4 5 6 7 97 98 99
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
5
7
-1
5
7
...
100
size
0 1 2 3 4 5 6 7 97 98 99
size==items.length
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
5
7
-1
5
7
...
100
size
0 1 2 3 4 5 6 7 97 98 99
0
0
0
0
0
0
0
0
0
0
0
...
0 1 2 3 4 5 6 7 97 98 99 100
0
a
size==items.length
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
5
7
-1
5
7
...
100
size
0 1 2 3 4 5 6 7 97 98 99
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100
0
a
size==items.length
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
5
7
-1
5
7
...
100
size
0 1 2 3 4 5 6 7 97 98 99
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100
11
a
size==items.length
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
101
size
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100
11
a
size==items.length
Array Resizing
When the array gets too full, e.g. addLast(11), just make a new array:
addLast()
getLast()
get(int i)
removeLast()
items
101
size
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100
11
a
We call this process “resizing”
size==items.length
Resizing Array Implementation
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Implementation
Let’s implement the resizing capability.
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
items[size] = x;
size += 1;
}
}
AList.java
The resizing functionality is really its own independent operation, separate from addLast.
We could organize our code better by moving this code into its own function.
Coding Demo: Resizing Array
public class AList {
/** Resizes the underlying array to the target capacity. */
private void resize(int capacity) {
}
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Resizes the underlying array to the target capacity. */
private void resize(int capacity) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Resizes the underlying array to the target capacity. */
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
}
items[size] = x;
size += 1;
}
}
AList.java
Coding Demo: Resizing Array
public class AList {
/** Resizes the underlying array to the target capacity. */
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
/** Inserts x into the back of the list. */
public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}
}
AList.java
Resizing Array Code
public void addLast(int x) {
if (size == items.length) {
int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
items[size] = x;
size += 1;
}
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}
Works
Much Better
Easier to read and understand.
Easier to test the correctness of each function.
Runtime Analysis (Warmup)
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Runtime and Space Usage Analysis: yellkey.com/think
Suppose we have a full array of size 100. If we call addLast two times, how many total array memory boxes will we need to create and fill (for just these 2 calls)?
Bonus question: What is the maximum number of array boxes that Java will track at any given time? Assume that “garbage collection” happens immediately when all references to an object are lost.�
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}
Array Resizing
Resizing twice requires us to create and fill 203 total memory boxes.
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100
11
5
3
1
7
22
-1
5
7
-1
5
7
...
0 1 2 3 4 5 6 7 97 98 99 100 101
11
3
101
102
100
Runtime Analysis
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Demo: Speed Testing the ArrayList
public class SpeedTestSLList {
public static void main(String[] args) {
SLList<Integer> L = new SLList<>();
int i = 0;
while (i < 100000) {
L.addFirst(i);
i = i + 1;
}
}
}
Adding 100,000 items to a new SLList is very fast (~0.05 seconds).
jug ~/.../lists4/speedtest
$ time java SpeedTestSLList
real 0m0.058s
user 0m0.060s
sys 0m0.004s
SpeedTestSLList.java
Demo: Speed Testing the ArrayList
public class SpeedTestAList {
public static void main(String[] args) {
AList L = new AList();
int i = 0;
while (i < 100000) {
L.addLast(i);
i = i + 1;
}
}
}
jug ~/.../lists4/speedtest
$ time java SpeedTestAList
real 0m2.945s
user 0m2.872s
sys 0m0.068s
SpeedTestAList.java
Adding 100,000 items to a new AList is very slow (~3 seconds).
Runtime and Space Usage Analysis: yellkey.com/TODO
Suppose we have a full array of size 100. If we call addLast until size = 1000, roughly how many total array memory boxes will we need to create and fill?
Bonus question: What is the maximum number of array boxes that Java will track at any given time? Assume that “garbage collection” happens immediately when all references to an object are lost.
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}
Runtime and Space Usage Analysis
Suppose we have a full array of size 100. If we call addLast until size = 1000, roughly how many total array memory boxes will we need to create and fill?
B. 500,000
Going from capacity 100 to 101: 101
From 101 to 102: 102
…
From: 999 to 1000: 1000
Total array boxes created/copied: 101 + 102 + … + 1000
Since sum of 1 + 2 + 3 + … + N = N(N+1)/2, sum(101, …, 1000) is close to 500,000.
See: http://mathandmultimedia.com/2010/09/15/sum-first-n-positive-integers
We’ll be doing a lot of this after the midterm.
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
Runtime and Space Usage Analysis
Since sum of 1 + 2 + 3 + … + N = N(N+1)/2, sum(101, …, 1000) is close to 500,000.
Rough intuition: Form pairs that all sum to N+1:
N + 1
(N-1) + 2
(N-2) + 3
...
There are N/2 such pairs.
1 + 2 + 3 + 4 + 5 + ... + (N-4) + (N-3) + (N-2) + (N-1) + N
Resizing Slowness
Inserting 100,000 items requires roughly 5,000,000,000 new containers.
Note: Insert here is addFirst
Resizing Slowness
Inserting 100,000 items requires roughly 5,000,000,000 new containers.
Number of inserts into list
The same graphs from the previous slide, placed on top of each other.
Red line = SLList
Teal line = AList
Better Resizing Strategy
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Fixing the Resizing Performance Bug
How do we fix this?
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0, a, 0, size);
items = a;
}
public void addLast(int x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size += 1;
}
Demo: Speed Testing the ArrayList
jug ~/.../lists4/speedtest
$ time java SpeedTestAList
real 0m0.373s
user 0m0.328s
sys 0m0.044s
Resizing by 10 elements instead of 1 seems to speed up adding 100,000 items…
jug ~/.../lists4/speedtest
$ time java SpeedTestAList
real 0m16.572s
user 0m15.968s
sys 0m0.284s
…but the problem re-emerges if we try to add 1,000,000 items.
public void addLast(int x) {
if (size == items.length) {
resize(size + 10);
}
items[size] = x;
size += 1;
}
Demo: Speed Testing the ArrayList
jug ~/.../lists4/speedtest
$ time java SpeedTestAList
real 0m0.069s
user 0m0.068s
sys 0m0.008s
If we double the array capacity every time it's full, then adding 100,000 items is fast…
jug ~/.../lists4/speedtest
$ time java SpeedTestAList
real 0m0.112s
user 0m0.088s
sys 0m0.028s
…and adding 1,000,000 items is also fast.
public void addLast(int x) {
if (size == items.length) {
resize(size * 2);
}
items[size] = x;
size += 1;
}
(Probably) Surprising Fact
Geometric resizing is much faster.
We can't prove this until later. See this video for a more detailed analysis.
Rough intuition: As the array grows larger, we resize less often.
Unusably bad.
Great performance.
This is how the Python list is implemented.
public void addLast(int x) {
if (size == items.length) {
resize(size + RFACTOR);
}
items[size] = x;
size += 1;
}
public void addLast(int x) {
if (size == items.length) {
resize(size * RFACTOR);
}
items[size] = x;
size += 1;
}
Performance Problem #2
Suppose we have a very rare situation occur which causes us to:
Our data structure will execute these operations acceptably fast, but afterwards there is a problem.
�
Memory Efficiency
An AList should not only be efficient in time, but also efficient in space.
Later we will consider tradeoffs between time and space efficiency for a variety of algorithms and data structures.�
5
3
1
7
0
0
0
0
0
0
0
...
0 1 2 3 4 5 6 7 97 98 99
Usage ratio: 4/100 = 0.04
addLast()
getLast()
get(int i)
removeLast()
items
4
size
Generic ArrayLists
Lecture 7, CS61B, Spring 2024
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
Generic ALists (similar to generic SLists)
public class AList {
private int[] items;
private int size;
public AList() {
items = new int[8];
size = 0;
}
private void resize(int capacity) {
int[] a = new int[capacity];
System.arraycopy(items, 0,
a, 0, size);
items = a;
}
public int get(int i) {
return items[i];
}
...
}
public class AList<Glorp> {
private Glorp[] items;
private int size;
public AList() {
items = (Glorp[]) new Object[8];
size = 0;
}
private void resize(int cap) {
Glorp[] a = (Glorp[]) new Object[cap];
System.arraycopy(items, 0,
a, 0, size);
items = a;
}
public Glorp get(int i) {
return items[i];
}
...
}
Generic ALists (similar to generic SLists)
When creating an array of references to Glorps:
Why not just new Glorp[cap];
public class AList<Glorp> {
private Glorp[] items;
private int size;
public AList() {
items = (Glorp[]) new Object[8];
size = 0;
}
private void resize(int cap) {
Glorp[] a = (Glorp[]) new Object[cap];
System.arraycopy(items, 0,
a, 0, size);
items = a;
}
public Glorp get(int i) {
return items[i];
}
...
}
Nulling Out Deleted Items
Unlike integer based ALists, we actually want to null out deleted items.
public Glorp removeLast() {
Glorp returnItem = getLast();
items[size - 1] = null;
size -= 1;
return returnItem;
}
null
0 1 2 3
items
3
size
Loitering Example
Changing size to 2 yields a correct AList.
null
0 1 2 3
items
2
size
Loitering Example
Changing size to 2 yields a correct AList.
By nulling out items[2], Java is free to destroy the unneeded image from memory, which could be potentially megabytes in size.
null
null
0 1 2 3
items
2
size
Loitering Example
Changing size to 2 yields a correct AList.
By nulling out items[2], Java is free to destroy the unneeded image from memory, which could be potentially megabytes in size.
null
null
0 1 2 3
items
2
size
Obscurantism in Java
Lecture 7, CS61B, Spring 2023
A Last Look at Linked Lists
Naive ArrayLists
Resizing ArrayLists
Generic ArrayLists
Obscurantism in Java
One last thought: Obscurantism in Java
We talk of “layers of abstraction” often in computer science.
User’s mental model: {5, 3, 1, 7, 22, -1} → {5, 3, 1, 7, 22}
0
0
0
...
addLast()
getLast()
get(int i)
removeLast()
items
5
3
1
7
22
-1
0
0
5
size
0 1 2 3 4 5 6 7 97 98 99
Actual truth:
One last thought: Obscurantism in Java
We talk of “layers of abstraction” often in computer science.