Today’s Musical Selections
"Gypsy" by Fleetwood Mac.
Stevie Nicks has such a wonderfully distinct voice. One of my favorite samples of all time is Bon Iver inserting a bit of this off camera Stevie Nicks gem into 10 d e a t h b r e a s t ⚄ ⚄.
This song buries some of its nicest bits at the end 1.
Linked Lists
> Click or hit Control-Enter to run Example.main above
Review: Lists
What you have been building on the last few homework problems is a more general data structure called a list.
Lists are an ordered 2 data structure that allow us to:
-
Get and set values at any index (like an array)
-
Add or remove values at any index (this is new)
-
Lists are one of the two data structures you meet in heaven—maps are the other and we’ll get to them in a few weeks
Review: Data Structure Tradeoffs
Depending on how we structure data different implementations of the same interface can have different performance characteristics.
-
We’ll start by looking at this with lists
-
Lists that store items using arrays have fast (O(1)) lookups but slow (O(n)) modifications
-
Lists that store items using linked lists have slow lookups (O(n)) but some insertions are fast (O(1))
-
Both also present different memory usage tradeoffs
Our List Interface
interface SimpleList {
/** Get the object at this index. */
Object get(int index);
/** Set the object at this index to the passed element. */
void set(int index, Object element);
/** Add the object at the specified location in the list. */
void add(int index, Object element);
/** Remove and return the object at the specified location in the list. */
Object remove(int index);
/** Return the number of elements in the list. */
int size();
}(The official Java one contains a bunch of convenience methods that we don’t want.)
Another Option: Linked Lists
public class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}Another Option: Linked Lists
public class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
Item items = new Item((Integer) 0, null);Another Option: Linked Lists
public class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);Another Option: Linked Lists
public class Item {
private Object value;
private Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);
items = new Item((Integer) 5, items);Another Option: Linked Lists
interface SimpleList {
Object get(int index);
void set(int index, Object element);
void add(int index, Object element);
Object remove(int index);
int size();
}
public class SimpleLinkedList implements SimpleList {
class Item {
Object value;
Item next;
Item(Object setValue, Item setNext) {
value = setValue;
next = setNext;
}
}
private Item start;
}Review: LinkedList addToFront
public class SimpleLinkedList {
private Item start;
public void addToFront(Object value) {
start = new Item(value, start);
}
}-
What is n—or what feature drives performance? The length of the list.
-
What is the performance of
addToFront? O(1): constant time!
Wow! What’s the catch?
(There’s always a catch.)
LinkedList: get
public class SimpleLinkedList {
private Item start;
public void addToFront(Object value) {
start = new Item(value, start);
}
public Object get(int index) {
// This should be easy...
}
}LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);LinkedList: get
public class SimpleLinkedList {
public Object get(int index) {
// until I get to the index
// follow each Item to the next
}
}
SimpleLinkedList list = new SimpleLinkedList();
list.addToFront((Integer) 1);
list.addToFront((Integer) 2);
list.addToFront((Integer) 3);
list.get(2);Linked Lists: Iteration
public class SimpleLinkedList {
private Item start;
}
public class Item {
public int value;
public Item next;
}We can iterate through our LinkedList using a for loop.
> Click or hit Control-Enter to run Example.main above
But How Do We Insert?
LinkedList Insertion Algorithm
-
Find the right spot.
-
Set the reference on the preceding item to point to the new item.
-
Set the reference on the new item to point to the former next item.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
But wait, now we can’t change the preceding reference.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Insertion Example
Let’s insert value 7 at index 1.
Questions About Lists?
Midterm Overview and Review
Midterm format:
-
40 points: 10 4-point multiple-choice questions drawn from previous quizzes
-
60 points: 3 20-point programming questions, all including partial credit
Midterm Topic Coverage
Midterm Questions?
> Click or hit Control-Enter to run Example.main above
Reminders
-
You’re all doing great! Particularly given the circumstances.
-
The point of the exams (and quizzes) is to get you to do the homework problems.
How to Get Help
We’re still finalizing a new office hour schedule intended to accommodate students in different time zones. Stay tuned.
Announcements
-
Midterm 1 will be run on Wednesday at your assigned quiz time. It’s worth the same amount as a quiz but cannot be dropped.
-
No labs tomorrow.
-
We’ll have drop-in office hours online all day for midterm help.
-
Today’s homework isn’t due until Wednesday, to give you a bit more time to prepare for the midterm. Daily homework resumes on Thursday.
-
Coders Chapter #7 for next week’s quiz.
-
I have virtual office hours today from 4–5PM. Please stop by!