Pre-announcements
CS61B: 2019
Lecture 4: Node Based Lists
From IntList to SLList
Last Time in 61B: Recursive Implementation of a List
While functional, “naked” linked lists like the one above are hard to use.
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
...
Improvement #1: Rebranding and Culling
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
Not much of an improvement obviously, but this next weird trick will be more impressive.
IntNode is now dumb, has no methods. We will reintroduce functionality in the coming slides.
Improvement #2: Bureaucracy
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
IntList X = new IntList(10, null);
SLList Y = new SLList(10);
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
...
}
SLList is easier to instantiate (no need to specify null), but we will see more advantages to come.
Next: Let’s add addFirst and getFirst methods to SLList.
IntNode is now dumb, has no methods.
The Basic SLList and Helper IntNode Class
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
public int getFirst() {
return first.item;
}
}
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
int x = L.getFirst();
Example
usage:
SLLists vs. IntLists
While functional, “naked” linked lists like the IntList class are hard to use.
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
int x = L.getFirst();
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
int x = L.first;
Naked Linked Lists (IntList) vs. SLLists
L1
addFirst()
SLList class acts as a middle man between user and raw data structure.
first
getFirst()
5
10
15
L2
L1
item
next
5
10
15
first
rest
Naked recursion: Natural for IntList user to have variables that point to the middle of the IntList.
Public vs. Private
Nested Classes
The SLList So Far
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
...
}
SLList L = new SLList(15);
L.addFirst(10);
L
addFirst()
first
getFirst()
item
next
10
15
A Potential SLList Danger
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
...
}
SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;
L
addFirst()
first
getFirst()
item
next
10
15
Users of our class might be tempted to try to manipulate our secret IntNode directly in uncouth ways!
A Potential SLList Danger
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
...
}
Users of our class might be tempted to try to manipulate our secret IntNode directly in uncouth ways!
SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;
L
addFirst()
first
getFirst()
item
next
10
15
Access Control
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
...
}
We can prevent programmers from making such mistakes with the private keyword.
Improvement #3: Access Control
public class SLList {
private IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
first = new IntNode(x, first);
}
...
}
Use the private keyword to prevent code in other classes from using members (or constructors) of a class.
SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;
jug ~/Dropbox/61b/lec/lists2
$ javac SLListUser.java
SLListUser.java:8: error: first has private access in SLList
L.first.next.next = L.first.next;
Why Restrict Access?
Hide implementation details from users of your class.
Car analogy:
Improvement #4: Nested Classes
Can combine two classes into one file pretty simply.
public class SLList {
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
} ...
Nested class definition.
Could have made IntNode a private nested class if we wanted.
Instance variables, constructors, and methods of SLList typically go below nested class definition.
Why Nested Classes?
Nested Classes are useful when a class doesn’t stand on its own and is obviously subordinate to another class.
In my opinion, probably makes sense to make IntNode a nested private class.
Static Nested Classes
If the nested class never uses any instance variables or methods of the outer class, declare it static.
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
...
We can declare IntNode static, since it never uses any of SLList’s instance variables or methods.
Analogy: Static methods had no way to access “my” instance variables. Static classes cannot access “my” outer class’s instance variables.
Unimportant note: For private nested classes, access modifiers are irrelevant.
addLast() and size()
Adding More SLList Functionality
To motivate our remaining improvements, and to give more functionality to our SLList class, let’s add:
Recommendation: Try writing them yourself before watching how I do it.
Methods | Non-Obvious Improvements | |
addFirst(int x) | #1 | Rebranding: IntList → IntNode |
getFirst | #2 | Bureaucracy: SLList |
| #3 | Access Control: public → private |
| #4 | Nested Class: Bringing IntNode into SLList |
See study guide for starter code!
Answers not shown in slides. See sp19-lectureCode or video for answers.
Private Recursive Helper Methods
To implement a recursive method in a class that is not itself recursive (e.g. SLList):
public class SLList {
private int size(IntNode p) {
if (p.next == null) {
return 1;
}
return 1 + size(p.next);
}
public int size() {
return size(first);
}
}
Efficiency of Size: http://yellkey.com/design
How efficient is size?
public class SLList {
private int size(IntNode p) {
if (p.next == null) {
return 1;
}
return 1 + size(p.next);
}
public int size() {
return size(first);
}
}
Improvement #5: Fast size()
Your goal:
Also I have a gift giveaway: Accidentally some CDs from KALX 10 years ago. Come take one from the front if you want one.
private IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) {
First = new IntNode(x, front);
}
private int size(IntNode p) {
if (p.next == null)
return 1;
return 1 + size(p.next);
}
public int size() {
return size(first);
}
Improvement #5: Fast size()
Solution: Maintain a special size variable that caches the size of the list.
TANSTAAFL: There ain't no such thing as a free lunch.
Naked Linked Lists (IntList) vs. SLLists
x
addFirst()
SLList class acts as a middle man between user and the naked recursive data structure. Allows us to store meta information about entire list, e.g. size.
first
getFirst()
5
10
15
x
item
next
5
10
15
first
rest
3
size
size()
addLast()
Improvement #6a: Representing the Empty List
Benefits of SLList vs. IntList so far:
Another benefit we can gain:
15
10
How Would You Fix addLast?
Your goal:
public class SLList {
private IntNode first;
private int size;
public SLList() {
first = null;
size = 0;
}
public void addLast(int x) {
size += 1;
IntNode p = first;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
} ...
SLList s1 = new SLList();
s1.addLast(5);
See study guide for starter code if you want to try on a computer.
One Solution
One possible solution:
But there are other ways...
public void addLast(int x) {
size += 1;
if (first == null) {
first = new IntNode(x, null);
return;
}
IntNode p = first;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
Sentinel Nodes
Tip For Being a Good Programmer: Keep Code Simple
As a human programmer, you only have so much working memory.
public void addLast(int x) {
size += 1;
if (first == null) {
first = new IntNode(x, null);
return;
}
IntNode p = first;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
addLast’s Fundamental Problem
The fundamental problem:
public void addLast(int x) {
size += 1;
if (first == null) {
first = new IntNode(x, null);
return;
}
IntNode p = first;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
Our fix is a bit ugly:
How can we avoid special cases?
Improvement #6b: Representing the Empty List Using a Sentinel
Create a special node that is always there! Let’s call it a “sentinel node”.
0
addFirst()
first
getFirst()
item
next
??
size
size()
addLast()
addFirst()
first
getFirst()
item
next
??
5
15
10
3
size
size()
addLast()
The empty list is just the sentinel node.
A list with 3 numbers has a sentinel node and 3 nodes that contain real data.
Let’s try reimplementing SLList with a sentinel node.
Sentinel Node
The sentinel node is always there for you.
Notes:
0
addFirst()
sentinel
getFirst()
item
next
63
size
size()
addLast()
addFirst()
sentinel
getFirst()
item
next
63
5
15
10
3
size
size()
addLast()
addLast (with Sentinel Node)
Bottom line: Having a sentinel simplifies our addLast method.
public void addLast(int x) {
size += 1;
if (sentinel == null) {
sentinel = new IntNode(x, null);
return;
}
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
0
addFirst()
sentinel
getFirst()
item
next
??
size
size()
addLast()
Invariants
An invariant is a condition that is guaranteed to be true during code execution (assuming there are no bugs in your code).
An SLList with a sentinel node has at least the following invariants:
Invariants make it easier to reason about code:
Summary
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 |
| #5 | Caching: Saving size as an int. |
| #6 | Generalizing: Adding a sentinel node to allow representation of the empty list. |
For Those Who Were a Bit Bewildered!
Don’t panic if it felt fast!
The LinkedListDeque class that you’ll build in project 1 (to be officially released Friday) will give you practice so that you can deeply understand the ideas from today’s lecture.
Old Deprecated Slides
Improvement #7: Helper Methods
Suppose we wanted to write a getBack() method.