CS61B, 2021
Lecture 5: Node Based Lists
¡ñ From IntList to SLList
¡ð The private keyword
¡ð Nested classes
¡ð Recursive private helper methods
¡ð Caching
¡ð Sentinel nodes
datastructur.es
From IntList to SLList
datastructur.es
Last Time in 61B: Recursive Implementation of a List
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r; }
…
While functional, ¡°naked¡± linked lists like the one above are hard to use.
¡ñ Users of this class are probably going to need to know references very well, and be able to think recursively. Let¡¯s make our users¡¯ lives easier.
datastructur.es
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.
datastructur.es
Improvement #2: Bureaucracy
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.
datastructur.es
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);
} …
}
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);
Example L.addFirst(10);
usage:
L.addFirst(5);
int x = L.getFirst();
datastructur.es
SLLists vs. IntLists
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;
While functional, ¡°naked¡± linked lists like the IntList class are hard to use.
¡ñ Users of IntList are need to know Java references well, and be able to think recursively.
¡ñ SLList is much simpler to use. Simply use the provided methods.
¡ñ Why not just add an addFirst method to the IntList class? Turns out there
is no efficient way to do this. See exercises in lectureCode repository.
datastructur.es
Naked Linked Lists (IntList) vs. SLLists
L1
L2
5
10
15
first rest
Naked recursion: Natural for IntList user to have variables that point to the middle of the IntList.
L1
addFirst()
getFirst()
first
SLList class acts as a middle man between user and raw data structure.
5
10
15
item next
datastructur.es
Public vs. Private Nested Classes
datastructur.es
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);
}
… }
L
addFirst()
getFirst()
first
10
15
item next
SLList L = new SLList(15);
L.addFirst(10);
datastructur.es
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);
}
… }
L
addFirst()
getFirst()
first
10
15
item next
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;
datastructur.es
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);
}
… }
L
addFirst()
getFirst()
first
10
15
item next
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;
dat
astructur.es
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.
datastructur.es
Improvement #3: Access Control
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;
datast
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);
}
… }
ructur.es
Why Restrict Access?
Hide implementation details from users of your class.
¡ñ Less for user of class to understand.
¡ñ Safe for you to change private methods (implementation). Car analogy:
¡ñ Public: Pedals, Steering Wheel Private: Fuel line, Rotary valve
¡ñ Despite the term ¡®access control¡¯:
¡ð Nothing to do with protection against hackers, spies, and other evil
entities.
Improvement #4: Nested Classes
Can combine two classes into one file pretty simply.
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.
datastructur.es
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); } …
Why Nested Classes?
Nested Classes are useful when a class doesn¡¯t stand on its own and is obviously subordinate to another class.
¡ñ Make the nested class private if other classes should never use the nested class.
In my opinion, probably makes sense to make IntNode a nested private class. ¡ñ Hard to imagine other classes having a need to manipulate IntNodes.
datastructur.es
Static Nested Classes
If the nested class never uses any instance variables or methods of the outer class, declare it static.
¡ñ Static classes cannot access outer class¡¯s instance variables or methods.
¡ñ Results in a minor savings of memory. See book for more details / exercise. 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.
datastructur.es
public class SLList {
private static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n; }
…
addLast() and size()
datastructur.es
Adding More SLList Functionality
To motivate our remaining improvements, and to give more functionality to our SLList class, let¡¯s add:
¡ñ .addLast(int x) ¡ñ .size()
See study guide for starter code!
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
Answers not shown in slides. See fa20-lectureCode or video for answers.
datastructur.es
Private Recursive Helper Methods
To implement a recursive method in a class that is not itself recursive (e.g. SLList):
¡ñ Create a private recursive helper method.
¡ñ Have the public method call the private recursive helper method.
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);
} }
datastruct
ur.es
Efficiency of Size: http://yellkey.com/design How efficient is size?
¡ñ Suppose size takes 2 seconds on a list of size 1,000.
¡ñ How long will it take on a list of size 1,000,000?
a. 0.002 seconds.
b. 2 seconds.
c. 2,000 seconds.
d. 2,000,000 seconds.
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);
} }
datastruct
ur.es
Improvement #5: Fast size()
Your goal:
¡ñ Modify SLList so that the execution time of size() is always fast (i.e. independent of the size of the list).
private IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public void addFirst(int x) { first = new IntNode(x, first);
}
private int size(IntNode p) { if (p.next == null)
return 1;
return 1 + size(p.next);
}
public int size() { return size(first);
}
datastructur.
es
Improvement #5: Fast size()
Solution: Maintain a special size variable that caches the size of the list. ¡ñ Caching: putting aside data to speed up retrieval.
TANSTAAFL: There ain’t no such thing as a free lunch.
¡ñ But spreading the work over each add call is a net win in almost any circumstance.
http://www.ensler.us/ensler.us/images/nolnchsmalla.jpg
datastructur.es
Naked Linked Lists (IntList) vs. SLLists
x
5
10
15
first rest
x
addFirst() size first getFirst()
addLast()
size()
3
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.
5
10
15
item next
datastructur.es
Improvement #6a: Representing the Empty List
Benefits of SLList vs. IntList so far:
¡ñ Faster size() method than would have been convenient for IntList.
¡ñ User of an SLList never sees the IntList class.
¡ð Simpler to use.
¡ð More efficient addFirst method (see exercises).
¡ð Avoids errors (or malfeasance):
Another benefit we can gain:
¡ñ Easy to represent the empty list. Represent the empty list by setting first to null. Let¡¯s try!
10
15
datastructur.es
How Would You Fix addLast?
Your goal:
¡ñ Fix addLast so that we do not get a null pointer exception when we try to add to the back of an empty SLList:
SLList s1 = new SLList();
s1.addLast(5);
See study guide for starter code if you want to try on a computer.
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);
} …
datastructur.es
One Solution
One possible solution:
¡ñ Add a special case for the empty list.
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); datastructur.es
}
Sentinel Nodes
datastructur.es
Tip For Being a Good Programmer: Keep Code Simple
As a human programmer, you only have so much working memory.
¡ñ You want to restrict the amount of complexity in your life!
¡ñ Simple code is (usually) good code. ¡ð Special cases are not ¡®simple¡¯.
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);
}
datastructur.
es
addLast¡¯s Fundamental Problem
The fundamental problem:
¡ñ The empty list has a null first. Can¡¯t access first.next!
Our fix is a bit ugly:
¡ñ Requires a special case.
¡ñ More complex data structures will have many more special cases (gross!!)
How can we avoid special cases?
¡ñ Make all SLLists (even empty) the ¡°same¡±.
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);
}
datastructur.es
Improvement #6b: Representing the Empty List Using a Sentinel
Create a special node that is always there! Let¡¯s call it a ¡°sentinel node¡±.
addFirst() size first getFirst()
addLast()
size()
0
??
item next
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.
addFirst() size first getFirst()
addLast()
size()
3
??
5
10
15
item next
datastructur.es
Sentinel Node
The sentinel node is always there for you.
Notes:
¡ñ I¡¯ve renamed first to be
sentinel.
¡ñ sentinel is never null,
always points to sentinel node.
¡ñ Sentinel node¡¯s item needs to
be some integer, but doesn¡¯t
matter what value we pick.
¡ñ Had to fix constructors and
methods to be compatible with sentinel nodes.
addFirst() size sentinel getFirst()
addLast()
size()
0
63
item next
addFirst() size sentinel getFirst()
addLast()
size()
3
63
5
10
15
item next
datastructur.es
addLast (with Sentinel Node)
Bottom line: Having a sentinel simplifies our addLast method.
¡ñ No need for a special case to check if sentinel is null (since it is never null).
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);
}
addFirst() size sentinel getFirst()
addLast()
size()
0
??
item next
datastructur.es
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:
¡ñ The sentinel reference always points to a sentinel node.
¡ñ The first node (if it exists), is always at sentinel.next.
¡ñ The size variable is always the total number of items that have been added.
Invariants make it easier to reason about code:
¡ñ Can assume they are true to simplify code (e.g. addLast doesn¡¯t need to worry about nulls).
¡ñ Must ensure that methods preserve invariants.
datastructur.es
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.
datastructur.es
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.
datastructur.es
Old Deprecated Slides
datastructur.es
Improvement #7: Helper Methods
Suppose we wanted to write a getBack() method.
¡ñ Would be quite similar to insertBack()
¡ñ Make sense to create a getBackNode() method that can be used by both
getBack() and insertBack()
datastructur.es