Announcements
Reminder: Project 1A is out.
CS61B, 2021
Lecture 7: Arrays and Lists
A Last Look at Linked Lists
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
Naive Array Lists
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
Naive AList Code
AList Invariants:
Let’s now discuss delete operations.
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 last lecture, “things that must be true”.
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 97 98 99
Actual truth:
Deletion: yellkey.com/enter
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.
Naive AList Code
AList Invariants:
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;
}
}
public int removeLast() {
int returnItem = items[size - 1];
items[size - 1] = 0;
size -= 1;
return returnItem;
}
Setting deleted item to zero is not necessary to preserve invariants, and thus not necessary for correctness.
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
Resizing Arrays
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
size==items.length
We call this process “resizing”
Implementation
Let’s implement the resizing capability.
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
Runtime and Space Usage Analysis: yellkey.com/camera
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 and Space Usage Analysis: yellkey.com/focus
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;
}
Resizing Slowness
Inserting 100,000 items requires roughly 5,000,000,000 new containers.
Note: Insert here is addFirst
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;
}
(Probably) Surprising Fact
Geometric resizing is much faster: Just how much better will have to wait.
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 ALists
Generic ALists (similar to generic SLists)
bleepblrop
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 deleteBack() {
Glorp returnItem = getBack();
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
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.
Citations
Hanging Containers: http://www.portcalls.com/wp-content/uploads/2012/04/hanging_containers1.jpg
http://images.mysecuritysign.com/img/lg/K/No-Loitering-Sign-K-5418.gif�http://3.bp.blogspot.com/-NV3y2NQDFy0/UAAXB5gINoI/AAAAAAAALi8/F_bM4-dmsm4/s1600/DVC00575.JPG
Red pill/blue pill: https://en.wikipedia.org/wiki/Red_pill_and_blue_pill