DLLists and Arrays
1
Lecture 5 (Lists 3)
CS61B, Fall 2024 @ UC Berkeley
Slides credit: Josh Hug
Summary of SLLists So Far
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Summary of Last Time (From IntList to SLList)
Methods | Non-Obvious Improvements | |
addFirst(int x) | #1 | Rebranding: IntList → IntNode |
getFirst() | #2 | Bureaucracy: SLList |
addLast(int x) | #3 | Access Control: public → private |
size() | #4 | Nested Class: Bringing IntNode into SLList |
| #5 | Caching: Saving size as an int. |
| #6 | Generalizing: Adding a sentinel node to allow representation of the empty list. |
addFirst()
sentinel
getFirst()
item
next
63
5
15
10
3
size
size()
addLast()
One Downside of SLLists
Inserting at the back of an SLList is much slower than the front.
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
}
public void addLast(int x) {
size += 1;
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
Improvement #7: (???) Goal: Fast addLast
How could we modify our list data structure so that addLast is also fast?
addFirst()
sentinel
getFirst()
item
next
??
3
50
9
3
size
size()
addLast()
Why a Last Pointer Isn’t Enough
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Is .last enough?
Suppose we want to support add, get, and remove operations for both ends, will having a last pointer result for fast operations on long lists?
addLast()
sentinel
getLast()
item
next
??
3
9
50
3
size
size()
removeLast()
last
.last Is Not Enough
Suppose we want to support add, get, and remove operations, will having a last pointer result for fast operations on long lists?
RemoveLast requires setting 9’s next pointer to null, and point last at the 9 node.
sentinel
item
next
??
3
9
3
size
addLast()
getLast()
size()
removeLast()
last
50
i.e. slow because we have to find the “9” node.
.last Is Not Enough
Suppose we want to support add, get, and remove operations, will having a last pointer result for fast operations on long lists?
RemoveLast requires setting 9’s next pointer to null, and point last at the 9 node.
sentinel
item
next
??
3
9
3
size
addLast()
getLast()
size()
removeLast()
last
50
i.e. slow because we have to find the “9” node.
Improvement #7: .last and ??? Goal: Fast operations on last.
We added .last. What other changes might we make so that remove is also fast?
sentinel
item
next
??
3
9
3
size
addLast()
getLast()
size()
removeLast()
last
50
Doubly Linked Lists
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Improvement #7: .last and .prev
We added .last. What other changes might we make so that remove is also fast?
sentinel
item
next
??
3
2
size
last
prev
addLast()
getLast()
size()
removeLast()
9
item
next
prev
item
next
prev
Note: Arrows point at entire nodes, not fields!
Example: last holds the address of the last node, not the item field of the sentinel node.
Doubly Linked Lists (Naive)
Reverse pointers allow all operations (add, get, remove) to be fast.
sentinel
item
next
??
3
2
size
last
prev
addLast()
getLast()
size()
removeLast()
9
0
sentinel
??
size
last
addLast()
getLast()
size()
removeLast()
item
next
prev
item
next
prev
Doubly Linked Lists (Naive)
Non-obvious fact: This approach has an annoying special case: last sometimes points at the sentinel, and sometimes points at a ‘real’ node.
sentinel
item
next
??
3
2
size
last
prev
addLast()
getLast()
size()
removeLast()
9
item
next
prev
item
next
prev
0
sentinel
??
size
last
addLast()
getLast()
size()
removeLast()
Doubly Linked Lists (Double Sentinel)
One solution: Have two sentinels.
sentFront
item
next
??
3
2
size
sentBack
prev
9
??
0
sentFront
??
size
sentBack
??
addLast()
getBack()
size()
removeLast()
addLast()
getBack()
size()
removeLast()
This is one reasonable approach for Project 1.
Doubly Linked Lists (Circular Sentinel)
Even better topology (IMO):
0
sentinel
??
size
sentinel
3
2
size
9
??
next
item
prev
addLast()
getLast()
size()
removeLast()
addLast()
getLast()
size()
removeLast()
This is my preferred approach for Project 1.
Examples:
Note: arrows are pointing at entire nodes, not specific fields of nodes.
Improvement #8: Fancier Sentinel Node(s)
While fast, adding .last and .prev introduces lots of special cases.
To avoid these, either:
DLList Summary
Still many steps before we have an industrial strength data structure. Will discuss over coming weeks.�
Methods | Non-Obvious Improvements | |
addFirst(int x) | #1 | Rebranding: IntList → IntNode |
getFirst() | #2 | Bureaucracy: SLList |
size() | #3 | Access Control: public → private |
addLast(int x) | #4 | Nested Class: Bringing IntNode into SLList |
removeLast() | #5 | Caching: Saving size as an int. |
| #6 | Generalizing: Adding a sentinel node to allow representation of the empty list. |
| #7 | Looking back:.last and .prev allow fast removeLast |
| #8 | Sentinel upgrade: Avoiding special cases with sentBack or circular list. |
Generic Lists
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Integer Only Lists
One issue with our list classes: They only support integers.
SLListLauncher.java:6: error: incompatible types: String cannot be converted to int
SLList s2 = new SLList("hi");
Works fine!
public class SLList {
private IntNode sentinel;
private int size;
public class IntNode {
public int item;
public IntNode next;
...
}
...
}
SLList s1 = new SLList(5);
s1.addFirst(10);
SLList s2 = new SLList("hi");
s2.addFirst("apple");
Coding Demo: Generic Lists
public class SLList {
private IntNode sentinel;
private int size;
private class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
}
SLList.java
In this demo, we'll modify our SLList to support lists of any data type, not just lists of integers.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private IntNode sentinel;
private int size;
private class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
}
SLList.java
A placeholder name, which will get replaced by the true data type each time a new SLList is created.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private IntNode sentinel;
private int size;
private class IntNode {
public LochNess item;
public IntNode next;
public IntNode(LochNess i, IntNode n) {
item = i;
next = n;
}
}
}
SLList.java
Items are no longer integers, but the LochNess placeholder data type.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private StuffNode sentinel;
private int size;
private class StuffNode {
public LochNess item;
public StuffNode next;
public StuffNode(LochNess i, StuffNode n) {
item = i;
next = n;
}
}
}
SLList.java
Renaming IntNode to StuffNode to be more descriptive.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private StuffNode sentinel;
private int size;
public SLList(LochNess x) {
sentinel = new StuffNode(null, null);
sentinel.next = new StuffNode(x, null);
size = 1;
}
public SLList() {
sentinel = new StuffNode(null, null);
size = 0;
}
}
SLList.java
Replaced int x with LochNess x, the placeholder data type.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private StuffNode sentinel;
private int size;
public void addFirst(LochNess x) {
sentinel.next = new StuffNode(x, sentinel.next);
size += 1;
}
public LochNess getFirst() {
return sentinel.next.item;
}
}
SLList.java
Replaced int x with LochNess x, the placeholder data type.
Return type is LochNess, not int.
Coding Demo: Generic Lists
public class SLList<LochNess> {
private StuffNode sentinel;
private int size;
public void addLast(LochNess x) {
size += 1;
StuffNode p = sentinel;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new StuffNode(x, null);
}
}
SLList.java
Replaced int x with LochNess x, the placeholder data type.
SLists
Java allows us to defer type selection until declaration.
public class SLList<BleepBlorp> {
private IntNode sentinel;
private int size;
public class IntNode {
public BleepBlorp item;
public IntNode next;
...
}
...
}
SLList<Integer> s1 = new SLList<>(5);
s1.addFirst(10);
SLList<String> s2 = new SLList<>("hi");
s2.addFirst("apple");
Generics
We’ll spend a lot more time with generics later, but here are the rules of thumb you’ll need for project 1:
DLList<Double> s1 = new DLList<>(5.3);
double x = 9.3 + 15.2;
s1.addFirst(x);
Array Overview
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Our Long Term Goal (next two lectures): The AList
In the last few lectures, we’ve seen how we can harness a recursive class definition to build an expandable list, ie. the IntList, the SLList, and the DLList.
In the next two, we’ll see how we can harness arrays to build such a list.
Getting Memory Boxes
To store information, we need memory boxes, which we can get in Java by declaring variables or instantiating objects. Examples:
Arrays are a special kind of object which consists of a numbered sequence of memory boxes.
Gives us a memory box of 32 bits that stores ints.
Gives us a memory box of 64 bits that stores Walrus references.
Gives us a memory box of 64 bits that stores Walrus references, and also gives us 96 bits for storing the int size (32 bits) and double tuskSize (64 bits) of our Walrus.
Arrays
Arrays consist of:
Like instances of classes:
Unlike classes, arrays do not have methods.
Basic Array Syntax
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Arrays
Like classes, arrays are (almost always) instantiated with new.
Three valid notations:
�
All three notations create an array, which we saw on the last slide comprises:
x = new int[3];
y = new int[]{1, 2, 3, 4, 5};
int[] z = {9, 10, 11, 12, 13};
Can omit the new if you are also declaring a variable.
Creates array containing 3 int boxes (32 x 3 = 96 bits total). Each container gets a default value.
As an aside: In Oracle’s implementation of Java, all Java objects also have some overhead. Total size of an array=192 + KN bits, where K is the number of bits per item (Sedgewick/Wayne pg. 201 for more)
Array Basics: http://goo.gl/tFyMEJ
int[] z = null;
int[] x, y;
x = new int[]{1, 2, 3, 4, 5};
y = x;
x = new int[]{-1, 2, 5, 4, 99};
y = new int[3];
z = new int[0];
int xL = x.length;
String[] s = new String[6];
s[4] = "ketchup";
s[x[3] - x[1]] = "muffins";
int[] b = {9, 10, 11};
System.arraycopy(b, 0, x, 3, 2);
Array Basics: https://goo.gl/gzAuBa
int[] z = null;
int[] x, y;
x = new int[]{1, 2, 3, 4, 5};
y = x;
x = new int[]{-1, 2, 5, 4, 99};
y = new int[3];
z = new int[0];
int xL = x.length;
String[] s = new String[6];
s[4] = "ketchup";
s[x[3] - x[1]] = "muffins";
int[] b = {9, 10, 11};
System.arraycopy(b, 0, x, 3, 2);
Arraycopy
Two ways to copy arrays:
arraycopy is (likely to be) faster, particularly for large arrays. More compact code.
System.arraycopy(b, 0, x, 3, 2);
(In Python): x[3:5] = b[0:2]
2D Arrays
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Arrays of Array Addresses (http://goo.gl/VS4cOK)
int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];
pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];
rowTwo[1] = -5;
int[][] matrix;
matrix = new int[4][];
matrix = new int[4][4];
int[][] pascalAgain = new int[][]{{1}, {1, 1},
{1, 2, 1}, {1, 3, 3, 1}};
Array Boxes Can Contain References to Arrays!
int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];
pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];
rowTwo[1] = -5;
int[][] matrix;
matrix = new int[4][];
matrix = new int[4][4];
int[][] pascalAgain = new int[][]{{1}, {1, 1},
{1, 2, 1}, {1, 3, 3, 1}};
Array of int array references.
Create four boxes, each can store an int array reference
Create a new array with three boxes, storing integers 1, 2, 1, respectively. Store a reference to this array in pascalsTriangle box #2.
Creates 5 total arrays.
Creates 1 total array.
What Does This Code Do? (Bonus Slides Only Exercise)
What will be the value of x[0][0] and w[0][0] when the code shown completes?
arraycopy parameters are:
Answer: https://goo.gl/CqrZ7Y
int[][] x = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] z = new int[3][];
z[0] = x[0];
z[0][0] = -z[0][0];
int[][] w = new int[3][3];
System.arraycopy(x[0], 0, w[0], 0, 3);
w[0][0] = -w[0][0];
Arrays vs. Classes
Lecture 5, CS61B, Fall 2024
SLLists:
Arrays:
Arrays vs. Classes
Arrays and Classes can both be used to organize a bunch of memory boxes.
public class Planet {
public double mass;
public String name;
...
}
int[] x = new int[]{100, 101, 102, 103};
Planet p = new Planet(6e24, "earth");
Arrays vs. Classes
Array indices can be computed at runtime.
jug ~/Dropbox/61b/lec/lists3
$ javac ArrayDemo.java
$ java ArrayDemo
What index do you want? 2
102
int[] x = new int[]{100, 101, 102, 103};
int indexOfInterest = askUser();
int k = x[indexOfInterest];
System.out.println(k);
Arrays vs. Classes
Class member variable names CANNOT be computed and used at runtime.
jug ~/Dropbox/61b/lec/lists3
$ javac ClassDemo.java
ClassDemo.java:5: error: array required,
but Planet found.
double mass = earth[fieldOfInterest]; ^
String fieldOfInterest = "mass";
Planet earth = new Planet(6e24, "earth");
double mass = earth[fieldOfInterest];
System.out.println(mass);
… if you reallllly want to do this, you can: https://goo.gl/JxpyLq
Arrays vs. Classes
Class member variable names CANNOT be computed and used at runtime.
jug ~/Dropbox/61b/lec/lists3
$ javac ClassDemo.java
ClassDemo.java:5: error: cannot find Symbol
double mass = earth.fieldOfInterest; ^
symbol: variable fieldOfInterest
location: variable earth of type Planet
… if you reallllly want to do this, you can: https://goo.gl/JxpyLq
String fieldOfInterest = "mass";
Planet earth = new Planet(6e24, "earth");
double mass = earth.fieldOfInterest;
System.out.println(mass);
Another view
The only (easy) way to access a member of a class is with hard-coded dot notation.
The Java compiler does not treat text on either side of a dot as an expression, and thus it is not evaluated.
int k = x[indexOfInterest]; /* no problem */
double m = p.fieldOfInterest; /* won't work */
double z = p[fieldOfInterest]; /* won't work */
/* No (sane) way to use field of interest */
double w = p.mass; /* works fine */