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.
Positions/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).
The reason this happened is because we completely took away the user's ability to work with pointers; let's add that capability back in by using a "position," which just works as a pointer to a specific spot in the List (in Java, this is done with Iterators). That adds the following methods:
- first() - returns the Position of the first element
- last() - returns the Position of the last element
- prev(Position p) - returns the Position before p
- next(Position p) - returns the Position after p
- add(Position p,e) - insert e at position p
- remove(Position p) - remove element at position p
You didn't realize it, but you did this when you used a foreach loop with ArrayLists or LinkedLists last semester.
| 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) |
| get(p) | O(1) | O(1) |
| set(p,e) | O(1) | O(1) |
| add(p,e) | O(n) | O(1) |
| remove(p) | O(n) | O(1) |