Abstract Data Types
Allegedly, this course is about Data Structures. In actuality, it is about Abstract Data Types (ADTs) and their implementation with Data Structures. An ADT is a description of an interface, and the data structures are how we make them work. For instance, last semester, we built a Queue. A Queue is an ADT; the linked list is the data structure.
Lists
Our first ADT is a List. A List is a container that holds data in some order, and can perform the following methods:
- get(i) - return the data at the i-th place in the list.
- set(i,e) - return the i-th piece of data, and also replace it with e.
- add(i,e) - insert e in the list at location i. All data with locations greater than i are shifted to a location one greater.
- remove(i) - remove and return the data at i. Shift all data at higher indices down.
This is all an ADT is! Any way of making this work, no matter how stupid or slow, still means it is a list. However, implementing it with different data structures gives us different run times.
So how would we implement this? Perhaps, arrays or linked lists. Presumably, you could implement all four of those methods with both, and analyze the run times.
Iterators
Assume we have a list aList, and we have the following code:
for (int i = 0; i < n; i++) aList.get(i);
What is the runtime if our list is implemented with an array? O(n), right? What if it's implemented with a LL? Well, each get is O(n), and we've got n of them, so it's \(O(n^2)\). That's stupid! This should clearly be O(n).
We can get this to be O(n) by using an "iterator," an object which keeps track of the last element it looked at, and can return the next one. In this way, we can jump from element to element, doing a \(O(1)\) update \(n\) times. We're not going to spend any time implementing Iterators in Java, but suffice to say they exist ("Iterator" is an interface). Just so you'll believe me, an example of an Iterator for our in-class example of ListLL is below:
import java.util.Iterator;
public class ListLLIterator implements Iterator {
private ListLLSoln list;
private Node p;
public ListLLIterator(ListLLSoln list) {
this.list = list;
p = list.getFirst();
}
public boolean hasNext() {
return p != null;
}
public Object next() {
Object o = p.getData();
p = p.getNext();
return o;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
Did you use a foreach loop last semester to work with Java's ArrayLists or LinkedLists? Then you used an Iterator, and just didn't know it.
| Array | Linked List | |
| get(i) | O(1) | O(n) |
| set(i,e) | O(1) | O(n) |
| add(i,e) | O(n) | O(n) |
| remove(i) | O(n) | O(n) |
| for all i, get(i) | O(n) | O(n) |