Lists
> Click or hit Control-Enter to run Example.main above
Algorithms and Data Structures
For the next two weeks we’ll be discussing fundamental computer science algorithms and data structures.
-
Algorithm: a way of doing something
-
Data structure: a way of storing data that enables certain algorithms
Arrays
int[] values = new int[10];At this point the only data structure we’ve discussed is the array.
-
Good: looking up an element in an array is O(1) 1.
-
Bad: the size of a Java array cannot be changed once it is created.
So How Do We Add Items?
Hint: it’s possible.
> Click or hit Control-Enter to run the code above
Array Append Performance
int[] append(int[] inputArray, int newValue) {
// Create a new array one larger than the existing array
// Copy all values over
// Add the new value at the end
// Return the new array
}-
What is n—or what feature drives performance? The length of
inputArray. -
Best case runtime: O(n)
-
Worst case runtime: O(n)
-
Average case runtime: O(n)
> Click or hit Control-Enter to run the code above
Array Insert Performance
int[] append(int[] inputArray, int newValue, int position) {
// Create a new array one larger than the existing array
// Copy all values over, adding the new value at the right spot
// Return the new array
}-
What is n—or what feature drives performance? The length of
inputArray. -
Best case runtime: O(n)
-
Worst case runtime: O(n)
-
Average case runtime: O(n)
Lists
Lists are a tremendously useful data structure. Every modern language has them 2.
-
The size of a list can change at runtime.
-
Items can be added and removed from the front or back:
-
Add to front (
prepend,unshift) or back (append,push) -
Remove from front (
shift) or back (pop)
-
-
Items can be added or removed from anywhere in the list (
insertorremove) -
Items can be retrieved and set by index (
getandset)
Why ArrayList?
ArrayList: get and set
public class ArrayList {
private int[] data;
ArrayList() {
this.data = new int[0];
}
public int get(int index) {
return this.data[index];
}
public void set(int index, int value) {
this.data[index] = value;
}
}-
What is n—or what feature drives performance? The length of the list.
-
What is the performance of
get? O(1): constant time! -
What is the performance of
set? O(1): constant time!
ArrayList: insert and remove
public class ArrayList {
private int[] data;
ArrayList() {
this.data = new int[0];
}
public void insert(int index, int value) {
...
}
public int remove(int index) {
...
}
}-
What is the performance of
insert? O(n): have to copy the entire list. -
What is the performance of
remove? O(n): have to copy the entire list.
Another Option: Linked Lists
public class Item {
private int value;
private Item next;
Item(int setValue, Item setNext) {
this.value = setValue;
this.next = setNext;
}
}Another Option: Linked Lists
public class Item {
private int value;
private Item next;
Item(int setValue, Item setNext) {
this.value = setValue;
this.next = setNext;
}
}
Item items = new Item(0, null);Another Option: Linked Lists
public class Item {
private int value;
private Item next;
Item(int setValue, Item setNext) {
this.value = setValue;
this.next = setNext;
}
}
Item items = new Item(0, null);
items = new Item(8, items);Another Option: Linked Lists
public class Item {
private int value;
private Item next;
Item(int setValue, Item setNext) {
this.value = setValue;
this.next = setNext;
}
}
Item items = new Item(0, null);
items = new Item(8, items);
items = new Item(5, items);Another Option: Linked Lists
public class LinkedList {
private Item start;
public addToFront(int value) {
start = new Item(value, start);
}
}public class Item {
private int value;
private Item next;
Item(int setValue, Item setNext) {
this.value = setValue;
this.next = setNext;
}
public void setNext(Item setNext) {
this.next = setNext;
}
public Item getNext() {
return this.next;
}
public int getValue() {
return this.value;
}
}> Click or hit Control-Enter to run Example.main above
LinkedList: addToFront
public class LinkedList {
private Item start;
public void addToFront(int 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 LinkedList {
private Item start;
public void addToFront(int value) {
start = new Item(value, start);
}
public int get(int index) {
// This should be easy...
}
}> Click or hit Control-Enter to run Example.main above
LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.get(2);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.get(2);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.get(2);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.get(2);LinkedList: get
public class LinkedList {
public int get(int index) {
// until I get to the index
// follow each Item to the next
}
}
LinkedList list = new LinkedList();
list.addToFront(1);
list.addToFront(2);
list.addToFront(3);
list.get(2);ArrayList v. LinkedList
Both provide the same functionality, but with different performance characteristics.
| Operation | ArrayList |
LinkedList |
|---|---|---|
|
O(n) |
O(1) |
|
O(1) |
O(n) |
|
O(n) |
O(n) |
Announcements
-
MP4 is due Friday. The early deadline is today.
-
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
-
Continue to communicate with the course staff about the strike as needed. We’re trying to keep everything up and running.
-
My office hours continue today at 11AM in the lounge outside of Siebel 0226.