Table of contents
We started the course with introducing the idea of the client view (what a piece of code does) from the implementer view (how the code does it). This is a key idea in computer science known as encapsulation, which hides details of our programs inside a class. In practice, we’ve been encapsulating classes by declaring fields as
private and writing comments that avoid exposing implementation details.
Instead of writing programs within the
main method, we instead learned how to design classes that manage state (fields) and provide behavior (methods) that a client can create and use in their programs. This helped us learn to think about what the client does and doesn’t know, and how to make sure the state of our object is consistent between method calls.
We’ve seen how Java evaluates programs, particularly stressing the difference between values and variables. Values are the data in a program, such as integers, booleans, or references to objects. Variables are names that store values. To evaluate
a = b, we ask for the value of
b and assign it to the name,
a. The same rule applies to regardless of whether the data is a primitive type or a reference type.
Runtime analysis is about quantifying the amount of time a program will need to run by estimating the number of steps taken to execute the algorithm as a function of the input size. In the worst case, the order of growth of the runtime of
indexOf is directly proportional to N, the number of elements in the list.
Abstract data types are high-level specifications for the behavior of data types without specifiying concrete implementation details, such as lists, sets, stacks, queues, and maps.
Data structures are the concrete implementations for abstract data types. For example, the linked nodes data structure can implement the list abstract data type, but it can also implement the stack or queue abstract data types as well.
Both abstract data types and data structures are general ideas. Java programmers typically use interfaces to represent abstract data types and implement the interface using classes. The
List interface represents the list abstract data type, and the
LinkedList class implements the
List interface using linked nodes.
- An ordered sequence of elements with indices that has dynamic length. Operations include adding at an index, adding at the end, removing at an index, getting the value at a particular index, checking if the list contains a value, etc.
ArrayListuses a (resizing) array to store the data. Fast access to elements given an index because arrays have random access, but slow to insert at an index since it’s necessary to shift everything over.
LinkedListuses linked nodes to the store the data. Fast to add or remove from the front since we can just change the references, but getting the value at an index is slow.
- A collection of unique values without associated indices. Operations include adding a value, removing a value, checking if the set contains a value, etc.
TreeSetstores the data in sorted order, but is a bit slower than
HashSetstores the data in an unknown order, but is a bit faster than
- A collection that only allows data to be added or removed from the top of the structure.
Stackclass represents a stack. Note that Java’s implementation is “leaky” since it extends
ArrayList) so it inherits all of the methods from the list abstract data type.
- A collection that only allows data to be added at the end and removed from the front.
- Represented by the
Queueinterface and implemented with the
- Represented by the
- A more generic version of an array, with any key type. Operations include adding a key-value mapping, removing a mapping, getting all the keys, getting all the values, etc.
TreeMapis similar to
TreeSetbut implements the map data type instead.
HashMapis similar to
HashSetbut implements the map data type instead.