Announcement
My office hours are in 779 Soda:
Come talk about anything.
SLLists, Nested Classes, Sentinel Nodes
2
Lecture 4 (Lists 2)
CS61B, Fall 2025 @ UC Berkeley
Slides credit: Josh Hug
Getting Started:
IntList → IntNode
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
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.
Creating the SLList Class
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
}
SLList.java
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
public IntNode first;
}
SLList.java
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
public IntNode first;
public SLList(int x) {
}
}
SLList.java
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
}
SLList.java
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public static void main(String[] args) {
}
}
SLList.java
Coding Demo: Bureaucracy
/** An SLList is a list of integers, which hides the terrible truth
* of the nakedness within. */
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
public static void main(String[] args) {
/** Creates a list of one integer, namely 10 */
SLList L = new SLList(10);
}
}
SLList.java
Improvement #2: Bureaucracy
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
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.
public class SLList {
public IntNode first;
public SLList(int x) {
first = new IntNode(x, null);
}
...
}
IntList X = new IntList(10, null);
SLList Y = new SLList(10);
addFirst and getFirst
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
}
SLList.java
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
/** Adds x to the front of the list. */
public void addFirst(int x) {
}
}
SLList.java
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
}
}
SLList.java
This is how we added to the front of an IntList in the previous lecture.
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
}
/** Returns the first item in the list. */
public int getFirst() {
}
}
SLList.java
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
}
/** Returns the first item in the list. */
public int getFirst() {
return first.item;
}
}
SLList.java
Coding Demo: addFirst and getFirst
public class SLList {
public IntNode first;
public static void main(String[] args) {
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
System.out.println(L.getFirst()); // should print 5
}
}
SLList.java
The Basic SLList and Helper IntNode Class
public class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
Example
usage:
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;
}
}
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
int x = L.getFirst();
SLLists vs. IntLists
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
SLLists vs. IntLists
While functional, “naked” linked lists like the IntList class are hard to use.
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
int x = L.first;
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
int x = L.getFirst();
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.
Access Control: Public vs. Private
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
The SLList So Far
SLList L = new SLList(15);
L.addFirst(10);
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()
first
getFirst()
item
next
10
15
A Potential SLList Danger
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!
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;
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;
Users of our class might be tempted to try to manipulate our secret IntNode directly in uncouth ways!
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
SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;
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.
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:
Nested Classes
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
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.
Creating addLast and size
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
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 lectureCode Repository for starter code!
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
IntNode p = first;
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
IntNode p = first;
while (p.next != null) {
}
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
IntNode p = first;
while (p.next != null) {
p = p.next;
}
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
IntNode p = first;
/* Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Adds an item to the end of the list. */
public void addLast(int x) {
IntNode p = first;
/* Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
public static void main(String[] args) {
SLList L = new SLList(15);
L.addFirst(10);
L.addFirst(5);
L.addLast(20);
System.out.println(L.getFirst()); // should print 5
}
}
SLList.java
Running this code doesn't actually prove that our addLast works. More about testing in a later lecture.
Coding Demo: size
public class SLList {
private IntNode first;
public int size() {
}
}
SLList.java
Coding Demo: size
public class SLList {
private IntNode first;
public int size() {
}
}
SLList.java
Writing a recursive size method is tricky, because SLList itself is not recursive.
The size method doesn't take in any arguments, so calling size recursively is strange. What is the base case? How do you call size recursively to get closer to the base case?
Coding Demo: addLast
public class SLList {
private IntNode first;
private static int size(IntNode p) {
}
public int size() {
}
}
SLList.java
Solution: Write a private static helper method that takes in an extra argument to help with recursion.
(This can be static because we don't need to reference first.)
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Returns the size of the list that starts at IntNode p. */
private static int size(IntNode p) {
}
public int size() {
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Returns the size of the list that starts at IntNode p. */
private static int size(IntNode p) {
if (p.next == null) {
}
}
public int size() {
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Returns the size of the list that starts at IntNode p. */
private static int size(IntNode p) {
if (p.next == null) {
return 1;
}
}
public int size() {
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Returns the size of the list that starts at IntNode p. */
private static int size(IntNode p) {
if (p.next == null) {
return 1;
}
return 1 + size(p.next);
}
public int size() {
}
}
SLList.java
Coding Demo: addLast
public class SLList {
private IntNode first;
/** Returns the size of the list that starts at IntNode p. */
private static int size(IntNode p) {
if (p.next == null) {
return 1;
}
return 1 + size(p.next);
}
public int size() {
return size(first);
}
}
SLList.java
Private Recursive Helper Methods
To implement a recursive method in a class that is not itself recursive (e.g. SLList):
public class SLList {
private IntNode first;
private int size(IntNode p) {
if (p.next == null) {
return 1;
}
return 1 + size(p.next);
}
public int size() {
return size(first);
}
}
size Efficiency, caching
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
Efficiency of Size: https://www.yellkey.com/second
How efficient is size?
public class SLList {
private IntNode first;
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:
(video viewers only, time is too tight in class to think carefully about this)
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);
}
private int size(IntNode p) {
if (p.next == null)
return 1;
return 1 + size(p.next);
}
public int size() {
return size(first);
}
}
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
}
SLList.java
Instead of re-calculating size on demand every time size is called, we'll keep track of the current size in a private variable.
Then, we'll update the size variable every time the list is changed.
This variable is redundant (we could calculate the size from the list), but will save us time.
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
}
}
SLList.java
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
}
SLList.java
New line added to existing function.
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
}
}
SLList.java
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
size += 1;
}
}
SLList.java
New line added to existing function.
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
/** Returns the first item in the list. */
public int getFirst() {
return first.item;
}
}
SLList.java
No modification needed. getFirst doesn't change the size of the list.
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
/** Adds x to the end of the list. */
public void addLast(int x) {
IntNode p = first;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
/** Adds x to the end of the list. */
public void addLast(int x) {
size += 1;
IntNode p = first;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
New line added to existing function.
Coding Demo: Fast size
public class SLList {
private IntNode first;
private int size;
public int size() {
return size;
}
}
SLList.java
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()
The Empty List and the addLast Bug
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
Coding Demo: The Empty List
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
/** Creates an empty SLList. */
public SLList() {
}
}
SLList.java
Adding a second constructor for empty lists (in addition to the existing constructor for making lists with 1 element).
Coding Demo: The Empty List
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
/** Creates an empty SLList. */
public SLList() {
size = 0;
}
}
SLList.java
Adding a second constructor for empty lists (in addition to the existing constructor for making lists with 1 element).
Coding Demo: The Empty List
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
/** Creates an empty SLList. */
public SLList() {
first = null;
size = 0;
}
}
SLList.java
Adding a second constructor for empty lists (in addition to the existing constructor for making lists with 1 element).
Coding Demo: The Empty List
public class SLList {
private IntNode first;
private int size;
public static void main(String[] args) {
SLList L = new SLList();
L.addFirst(10);
L.addFirst(5);
L.addLast(20);
System.out.println(L.getFirst()); // should print 5
}
}
SLList.java
Improvement #6a: Representing the Empty List
Benefits of SLList vs. IntList so far:
Another benefit we can gain:
15
10
Coding Demo: The addLast Bug
public class SLList {
private IntNode first;
private int size;
public static void main(String[] args) {
SLList L = new SLList();
L.addLast(20); // program crashes!
}
}
SLList.java
Coding Demo: The addLast Bug
public class SLList {
private IntNode first;
private int size;
/** Adds x to the end of the list. */
public void addLast(int x) {
size += 1;
IntNode p = first;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
The NullPointerException traceback identifies this line as where the program crashed.
How Would You Fix addLast?
Your goal:
See lec4_lists2/fixAddLastBug in the lectureCode-sp25 repo 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);
}
}
SLList s1 = new SLList();
s1.addLast(5);
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
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
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.
Coding Demo: Sentinel Nodes
public class SLList {
private IntNode first;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
public SLList() {
first = null;
size = 0;
}
}
SLList.java
In this demo, we'll be modifying our existing code to account for the sentinel node.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
public SLList() {
first = null;
size = 0;
}
}
SLList.java
Renaming first to sentinel.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
public SLList(int x) {
first = new IntNode(x, null);
size = 1;
}
public SLList() {
sentinel = new IntNode(63, null);
size = 0;
}
}
SLList.java
The empty list is no longer null. It's the sentinel node (and no other nodes).
63 is a placeholder. We don't care about the sentinel node's value.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
public SLList(int x) {
sentinel = new IntNode(63, null);
sentinel.next = new IntNode(x, null);
size = 1;
}
public SLList() {
sentinel = new IntNode(63, null);
size = 0;
}
}
SLList.java
The single-element list is no longer just one node. It's two nodes: the sentinel node, followed by the node with the single value.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Adds x to the front of the list. */
public void addFirst(int x) {
first = new IntNode(x, first);
size += 1;
}
}
SLList.java
Need to modify addFirst to be consistent with the sentinel structure.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Adds x to the front of the list. */
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
size += 1;
}
}
SLList.java
We need to reassign sentinel.next here, because "the first item is at sentinel.next."
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Returns the first item in the list. */
public int getFirst() {
return first.item;
}
}
SLList.java
Need to modify getFirst to be consistent with the sentinel structure.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Returns the first item in the list. */
public int getFirst() {
return sentinel.next.item;
}
}
SLList.java
Recall: "the first item is at sentinel.next."
If we returned sentinel.item, we would get the placeholder 63, not the true first item of the list.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Adds x to the end of the list. */
public void addLast(int x) {
size += 1;
IntNode p = first;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
Need to modify addLast to be consistent with the sentinel structure.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
/** Adds x to the end of the list. */
public void addLast(int x) {
size += 1;
IntNode p = sentinel;
/** Move p until it reaches the end of the list. */
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
}
SLList.java
Start p at the sentinel, and move p until it reaches the end of the list.
Sentinel always exists, so the addLast bug doesn't apply anymore.
Coding Demo: Sentinel Nodes
public class SLList {
/** The first item (if it exists) is at sentinel.next. */
private IntNode sentinel;
private int size;
public static void main(String[] args) {
SLList L = new SLList();
L.addLast(20);
System.out.println(L.size()); //should print out 1
}
}
SLList.java
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
Lecture 4, CS61B, Fall 2025
Getting Started
Syntax Improvements:
addLast and size
The Empty List
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. |
Next up: Stacks Homework
If today felt like a lot to digest, don’t worry.
Attendance link: https://www.yellkey.com/sister