Linear Collections

Dynamic arrays, linked nodes, asymptotic analysis, and iterative sorts.

1. Dynamic Arrays
   1. Designing an abstraction
2. Linked Nodes
   1. Encapsulation
3. Asymptotic Analysis
   1. Model the number of steps
   2. Formalize the runtime model
   3. Asymptotic notation
   4. Duplicate finding case study
4. Iterative Sorts
   1. Sorting definitions
   2. Selection sort
   3. Insertion sort

Dynamic Arrays

ResizingArrayStack.java

1. Design abstractions that hide internal implementation details from clients.
2. Explain the class invariants for the dynamic array data structure.
3. Write a unit test representing a test case involving a single program.

By writing Python code that use lists to solve a problem, you’ve been a client of the list data type. But have you ever wondered how lists are implemented in Python? Someone had to write an implementation for the list data type. This week, we’ll investigate several different ways to implement the list data type.

In software engineering, there’s a distinction between being a client of a program versus being an implementer of a program. If you’re working with a team of people on a software project, one person on your team might be responsible for writing the client while another person is responsible for writing the implementation. This distinction not only provides a blueprint for dividing a programming project into independent components, but it also allows for abstraction: the idea that we can change the implementation of the program without needing to rewrite all the client code too!

What would programming without abstraction look like? Without abstraction, everyone who wrote a program using lists would have to go back and fix their code every time the list data type is updated in Python. There are millions of people using Python, and many of them use lists. Software development would grind to a halt if every update to Python required everyone who used Python to also make many changes so that their code would work with the updates.

In this course, we’ll focus on being the implementer of data types like lists. How might we actually implement an ArrayList in Java? What design decisions were made to implement the ArrayList? By studying the implementation for ArrayList, we’ll not only learn about how it works but also when and why we might choose to use an ArrayList in the future.

ArrayList is the first of many Java collections that we’ll learn about in this course.

Collection

An object that represents a group of zero or more objects called elements. Lists and dictionaries are two examples of collections.

In this lesson, we’ll study two approaches to implement ArrayList. Consider the following code that shows us how an ArrayList changes over time as we add numbers to it.

List<Integer> nums = new ArrayList<>();
nums.add(1); // [1]
nums.add(2); // [1, 2]
nums.add(3); // [1, 2, 3]

This example provides some insight into one possible approach. The brackets notation printed out after each example is what you get if you have exactly those values stored in an array! We can keep track of this array with a private field called elementData. Read the comments to see what’s happening in each step of the constructor and the add method.

// The use of E here indicates the type of elements in the ArrayList.
// Clients can say ArrayList<Integer> to represent a list of integers.
public class ArrayList<E> implements List<E> {
    private E[] elementData;

    public ArrayList() {
        // Create a zero-length array because it has exactly the
        // string representation that we want: []
        elementData = new E[0];
    }

    public void add(E element) {
        // Make space by creating a slightly longer new array.
        E[] newData = new E[elementData.length + 1];

        // Copy everything over from the old array to the new array.
        for (int i = 0; i < elementData.length; i += 1) {
            newData[i] = elementData[i];
        }

        // Add the element to the end of the new array.
        newData[newData.length - 1] = element;

        // Re-assign the private field to the new array.
        elementData = newData;
    }

    public int size() {
        return elementData.length;
    }

    public String toString() {
        return Arrays.toString(elementData);
    }
}

In this approach, our internal representation is exactly identical to the result that’s printed-out. So we have a working ArrayList. Job well done, right?

Optionally, open the preloaded Java Tutor environment and see how it takes 45 steps just to add the numbers 1, 2, 3 into an empty list! This approach takes a lot of time!

Java Tutor

Designing an abstraction

To address this inefficiency, we can introduce a second field called size.

public class ArrayList<E> implements List<E> {
    private E[] elementData;
    private int size;

    public ArrayList() {
        // Create a length-10 array to store elements.
        elementData = new E[10];

        // Assign size to 0 for an initially-empty list.
        size = 0;
    }

    public void add(E element) {
        // Add the element to the next space in the array.
        elementData[size] = element;

        // Increment the size to indicate the list has grown.
        size += 1;
    }

    public int size() {
        // Return the current size of the list.
        return size;
    }

    public String toString() {
        // To be discussed later.
    }
}

Initially, size is 0. But, when we call add, the size is incremented by 1 to reflect the new element added to the array. The size tells us which values in the array are actually in-use by the list. Even though elementData has space for 10 elements, a new ArrayList should function as if it were empty. The size variable helps maintain the appearance of a dynamically-resizing list by treating only the first size-number of elements as actually in the list.

Open the preloaded Java Tutor environment and step through to see how the size field changes to match the actual number of elements added into the list. Note that this version only takes 28 steps to add the numbers 1, 2, 3. The difference will only become more appreciable as the number of elements increases.

Java Tutor

This approach avoids creating a new array each time we need to add an element, though this particular implementation is limited to just 10 elements. The actual Java implementation of the ArrayList class contains a little more code to create a new array double the current capacity when more space is needed, which is why we call this data structure the dynamic array.

Linked Nodes

LinkedStack.javaLinkedQueue.java

1. Trace the execution of a program with primitive types and reference types.
2. Define methods that manipulate nodes at the beginning and end of a list.
3. Write a unit test for comparing the output of two programs.

Dynamic arrays aren’t the only way to implement lists. In fact, for some methods, they can actually be quite slow. Lists not only allow adding elements, but also removing elements by a given index. How might we implement the remove(int index) method for the above ArrayList class?

// This method also returns the element that was removed.
public E remove(int index) {
    // Return null if the index is not in the given list.
    if (index >= size) {
        return null;
    }

    // Hold onto the element so that it can be returned later.
    E result = elementData[index];

    // Shift all following elements left by 1 position, thereby
    // removing the element at the given index.
    for (int i = index + 1; i < size; i += 1) {
        elementData[i - 1] = elementData[i];
    }

    // Decrement the size to indicate the list has shrunk.
    size -= 1;

    // Return the saved element.
    return result;
}

Shifting elements can take a lot of time: if we want to remove the first element in an ArrayList, every other element needs to move over too. Linked nodes are an alternative to arrays for representing an ordered sequence of elements. Whereas arrays store all the elements together in memory, each linked node contains its own element and a “link” or reference to the next node. For example, our LinkedList class can represent linked nodes with a Node class consisting of two fields:

• The value of the node’s element as the value field.
• A reference to the next element in the list.

public class Node<E> {
    private final E value;
    private Node<E> next;

    public Node(E value) {
        // Calls the other constructor to set the next field to null,
        // meaning that there is no next linked node in the sequence.
        this(value, null);
    }

    public Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }
}

It might seem strange for the Node class to contain a field referencing itself, but this is allowed in Java. We use the next field to access the node in the list after the current one. Remember that this is only a reference and does not store the actual object itself. A null next field indicates the end of a sequence of linked nodes.

The value field is marked final to prevent changes to value after the Node is created. In this course, we focus our study of linked nodes on changing only the references to next. For example, the following code represents the linked list [1, 2, 3].

Node<Integer> n1 = new Node<>(1);
Node<Integer> n3 = new Node<>(3);
Node<Integer> n2 = new Node<>(2, n3);
n1.next = n2;

Open the preloaded Java Tutor environment to visualize this code one step at a time. Before each time you press Next >, predict what will change in the visualization.

Java Tutor

Encapsulation

Where do we write the add, remove, size, and toString methods? If each Node stores a single element’s value, how do we refer to all the elements? We need a LinkedList class that encapsulates all the Node objects by bundling together all the data with the methods for operating on all of it.

public class LinkedList<E> implements List<E> {
    // Reference to the first node in the sequence
    private Node front;

    public void add(E element) {
        if (front == null) {
            // If the list is empty, assign the new node to the front.
            front = new Node(element);
        } else {
            // Otherwise, add the element to the end of the list.
            Node current = front;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new Node(element);
        }
    }

    public E remove(int index) {
        // To be discussed later.
    }

    public int size() {
        // Count the number of nodes starting from front.
        int result = 0;
        Node current = front;
        while (current != null) {
            result += 1;
            current = current.next;
        }
        return result;
    }

    public String toString() {
        // To be discussed later.
    }

    private class Node {
        private final E value;
        private Node next;

        public Node(E value) {
            this(value, null);
        }

        public Node(E value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

Java allows classes to be nested within other classes. In this case, we say that Node is an inner class of LinkedList. Note that the <E> generic type does not have to be repeated in the inner class because each Node is associated with its encapsulating LinkedList. We also changed the Node access modifier from public to private to indicate that Node is only relevant to the implementer of LinkedList.

Encapsulation doesn’t only describe the relationship between linked lists and their linked nodes. It can also be used to describe the relationship between array lists and their underlying arrays. Or really any class whose implementation details are hidden from clients—which is just about any program that we will write in this course! Encapsulation is the most common way to define an abstraction in data structures and algorithms.

Asymptotic Analysis

1. Compare and contrast runtime analysis, asymptotic analysis, and case analysis.
2. Analyze the order of growth of a function as constant, linear, or quadratic.
3. Identify big-theta asymptotic notation for the order of growth of a function.

In your previous programming experience, we focused on correctness and maintainability—code that produces the expected output given a particular input, and code that is easy to improve or extend in the future. But, as you’ve already seen in the preceding lessons, it’s also important that we design programs with a focus on efficiency too. Computing and data scientists want to quantify the efficiency of programs so that we can compare different approaches and select the most efficient one.

Experimental runtime analysis is a method for empirically measuring how long a program takes to run by recording exactly how long it takes to run on different inputs. Experimental analysis is particularly helpful for identifying and addressing performance issues by recording exactly which operations are contributing to high runtime. This data can be used to create graphs that can be used to plot the runtime as the input to the program grows larger and larger.

But what if we want to predict the runtime of a program before writing any code? What other methods can we use to help us design the specification to a program so that it meets our performance needs?

Asymptotic runtime analysis is the process of predicting the amount of time an algorithm will take to run on large inputs. Asymptotic analysis focuses on analyzing algorithms, the concepts underlying how programs work. Compared to experimental analysis, which focuses on empirical measurement, asymptotic analysis focuses on reasoning and logic to analyze the runtime of an algorithm.

Computer scientists specifically focus on large inputs (as the size of the input approaches infinity, or its asymptote) rather than small inputs because larger inputs more clearly demonstrate differences in efficiency. For example, the performance issue in ArrayListDeque only appears when a large number of web pages have been stored in browser history; ArrayListDeque is quite fast when only a few web pages have been stored. The differences in runtime become more appreciable when we’re working with a very large number of elements.

The goal of asymptotic runtime analysis is to produce a (1) predictive and (2) easy-to-compare description of the running time of an algorithm. Consider the indexOf method, which returns the index of a target number in an int[] A or -1 if target is not in the array.

static int indexOf(int[] A, int target) {
    for (int i = 0; i < A.length; i += 1) {
        if (A[i] == target) {
            return i;
        }
    }
    return -1;
}

The behavior of the indexOf algorithm depends on the input values.

1. Initialize an integer index counter, i.
2. Loop over the length of the array. On each iteration, if the A[i] is the same as the given target, return the current index. Otherwise, increment i.
3. If no elements in the array are the same as the given target, return -1.

Model the number of steps

How many steps (or operations) are needed to run the algorithm? Operations include assignments, boolean evaluations, arithmetic operations, method calls, etc.

Let’s take a look at these two assignment statements to illustrate how to count steps.

int a = 4 * 6;
int b = 9 * (a - 24) / (8 - 7);

1. The first assignment to a takes one step (1) to compute 4 * 6 and another step (2) to assign the result to the variable a.
2. The second assignment to b takes one step (1) to compute a - 24, another step (2) to compute 9 * (a - 24), another step (3) to compute 8 - 7, another step (4) to compute 9 * (a - 24) / (8 - 7), and a final step (5) to assign the result to the variable b.

In total, these two lines of code take 7 steps for the computer to run. The first goal of runtime analysis was to produce a predictive description of the runtime of an algorithm, but in this example, there’s not much to predict: the two assignment statements always take precisely 7 steps.

indexOf is different: it has a loop and an if statement that depends on the values in the A compared to the target. How do we model the number of steps it takes to run an algorithm in general? Here are two factors that can affect the number of steps to compute indexOf.

1. The length of the A.
2. The values of each int in the A compared to the value of the target.

The runtime of many algorithms is greatly affected by the size of the input. A small array typically takes little time to run regardless of whether the algorithm is fast or slow. Where we really start to appreciate the differences in runtime is when the array is very large. Therefore, when computer scientists talk about runtime analysis, the default assumption is asymptotic analysis.

Asymptotic analysis is a way of evaluating the efficiency of an algorithm on large inputs. The choice for the “large input” is called the asymptotic variable. For indexOf, the length of the A can be the asymptotic variable.

In this course, we’ll usually tell you the asymptotic variable using the phrases, “with respect to” or “in terms of”. Asymptotic analysis is defined in terms of the asymptotic variable, so make sure to confirm the asymptotic variable before analyzing a program.

But we also know that the runtime depends on other factors such as the relationship between the target and the numbers in the A. Case analysis is a way to account for variation in the model based on interactions between other factors besides the asymptotic variable.

Best case indexOf

The best case (most efficient or fastest) occurs when the target is the same as the A[0]—even when the array is very large.

Worst case indexOf

The worst case (least efficient or slowest) occurs when the target is the same as the last element in the A or not even in the A at all.

All other factors not covered by the asymptotic variable are considered in case analysis. In this course, we’ll focus only on the best and worst case: take all the remaining factors that you have at your disposal and choose a situation that produces the fastest (best case) or the slowest (worst case) runtime.

We now have a predictive model for the number of steps (a proxy for the time) it takes to run an algorithm. But this model is not easy to compare. To communicate our model, we’ll introduce some new vocabulary used to express asymptotic analysis.

Formalize the runtime model

How do we express our model to others so that we can communicate results?

The order of growth relates the size of the input to the time that it takes to run the algorithm on that input. Often, we’ll use a mathematical variable like N to refer to the asymptotic variable.

Best case indexOf orders of growth

In the best case, the order of growth for the runtime of indexOf is constant.

Worst case indexOf orders of growth

In the worst case, the order of growth for the runtime of indexOf is linear with respect to N, the length of A.

When the order of growth is constant, we don’t specify “with respect to N” because constant order of growth implies that the runtime does not scale with N.

Orders of growth help us compare runtime in terms of words like constant, linear, and quadratic. In practice, though, you’ll rarely see computer scientists writing out the full orders of growth sentence. Instead, computer scientists communicate orders of growth using asymptotic notation.

Asymptotic notation

Asymptotic notation provides precise, mathematical shorthand for orders of growth.

Consider this graph that depicts three functions of N.

The three functions depicted in the graph are:

1. The top blue function depicts 5N².
2. The middle red function depicts 40 sin(N) + 4N².
3. The bottom green function depicts 3N².

The shaded area represents the range between the top and bottom functions.

This graph provides a visual demonstration of the big-theta definition. We can say that the function 40 sin(N) + 4N² is in Θ(N²) because because it is bounded below by the green function 3N² (k₁ = 3) and bounded above by the blue function 5N² (k₂ = 5).

The red function is only “squeezed” between the blue and green functions for N > 6. This is why big-theta is an asymptotic notation: its logic applies to all values of N greater than some initial N₀. When we make a claim about asymptotic runtime, we can’t just pick N = 1 billion. We have to make sure that our analysis holds true for all possible “large inputs” N.

During class, we’ll also introduce two other asymptotic notation called big-oh and big-omega.

Duplicate finding case study

dup1 is an algorithm for determining if an array A contains any duplicate values by checking every possible pair of values until a duplicate is found. We’ve chosen N = A.length as the asymptotic variable.

boolean dup1(int[] A) {
    int N = A.length;
    for (int i = 0; i < N; i += 1)
        for (int j = i + 1; j < N; j += 1)
            if (A[i] == A[j])
                return true;
    return false;
}

Model the number of steps

Describe a best case situation for the runtime.

A very long array where the first pair of elements A[0] and A[1] are duplicates!

Suppose your teammate answer the above question:

The best case occurs when A.length is 2, so we only need to compare A[0] to A[1].

Explain why this answer is not an asymptotic analysis.

Although your teammate makes a good observation about the runtime of the program, asymptotic analysis focuses on large inputs. We can’t use an empty, 1-element, or 2-element array as an example.

Formalize the runtime model

In the best case, the order of growth for the runtime of dup1 is constant.

In the worst case, the order of growth for the runtime of dup1 is quadratic with respect to N, the length of A.

In the worst case, there are no duplicates in A. If we need to go through all the iterations of the nested for loop, then on the first iteration i = 0, the inner loop runs from j = 1 to j = N; then from j = 2 to j = N; then from j = 3 to j = N; and so forth. In total, we end up checking A[i] == A[j] exactly (N - 1) + (N - 2) + … + 3 + 2 + 1 times. The sum of this series is about N² / 2, which is quadratic.

Apply asymptotic notation

In the best case, the runtime of dup1 is in Θ(1).

In the worst case, the runtime of dup1 is in Θ(N²) with respect to N, the length of A.

Iterative Sorts

Insertion.javaSelection.java

1. Describe the problem of sorting, ordering relations, and stability.
2. Trace each iteration of selection sort and insertion sort.
3. Identify a run of selection sort and insertion sort on an array.

There are different ways to find duplicates in an array. dup1 represents one way to solve the problem: exhaustively check all possible pairs of elements and return whether a duplicate exists among them. In the worst case, dup1 required quadratic time to return an answer.

How long might a quadratic time algorithm need to run?

• When N = 10, less than 1 second.
• When N = 100, less than 1 second.
• When N = 1,000, about 1 second.
• When N = 10,000, about 2 minutes.
• When N = 100,000, about 3 hours.
• When N = 1,000,000, about 12 days.

What can we learn from these findings?

Many algorithms (including all algorithms in this course) are fast on tiny inputs when N < 1000

While there may be situations where we care about the efficiency of algorithms processing tiny inputs, these differences are often unnoticeable. When they are noticeable, they may be caused by unanticipated changes in your computer’s workload.

Differences become more appreciable when inefficient algorithms run on inputs of size N > 1000

Whether the runtime is tolerable depends on the problem. An inefficient algorithm may be acceptable if we only need to run it infrequently, the size of the input is not particularly big, or the amount of processing power can make up for the time.

Therefore, efficient algorithms are often needed to process even moderately-large data frequently.

However, if our array is sorted, then returning whether there are duplicates in the array takes much less time in the worst case. In a sorted array, all duplicate elements must be stored right beside each other. It turns out that a significant number of problems in computer science get a lot easier and a lot more efficient to solve if we can first sort our data. Without sorting, many of the systems and software that we have today would not be possible purely because things (like duplicate finding) would take far too long to run.

But data doesn’t always come to us in a pre-sorted form. How do we sort—rearrange into order—an array of elements?

Sorting definitions

Sorting is the problem of rearranging a sequence of elements into non-decreasing order. How do we define the order of elements? For numbers, smaller values appear before larger values in non-decreasing order. But sorting objects are a bit more complicated.

For objects, the implementer of the class is responsible for defining the ordering relation. Just as numbers have a natural definition for less-than, equal-to, and greater-than relationships, the class’s compareTo method provides a way to specify the relative order of any two elements of that class. For example, if we have emails where each Email object has a date, sender, and text, the compareTo method could be defined like an inbox where emails are sorted only by date.

public int compareTo(Email other) {
    // Compare the date of this email to the date of the other email.
    return this.date.compareTo(other.date);
}

In other situations like searching for all the emails from a particular sender (ignoring date), it might be more helpful to sort by the sender primarily and the text of their message secondarily.

public int compareTo(Email other) {
    // Compare the sender of this email to the sender of the other email.
    int cmp = this.sender.compareTo(other.sender);
    if (cmp != 0) {
        // If the senders are different, return the difference.
        return cmp;
    }
    // Otherwise, the senders are the same, so compare by text content.
    return this.text.compareTo(other.text);
}

A sort is stable if it preserves the original order of equivalent keys. Stability can affect the final sorting output when there are two or more elements considered equal according to the ordering relation. For basic data types like numbers, stability doesn’t matter: any two numbers that share the same numeric value are just the same either way. But for objects like emails, stability can make a big difference. Imagine sorting emails by sender name: you’ll often receive many emails from the same sender, so a stable sort for emails will sort by sender name and, for each sender name, maintain the relative order of emails in the original order. An unstable sort doesn’t guarantee the original order of emails for each person.

So how do we sort an array? In this lesson, we’ll introduce two iterative sorting algorithms: selection sort and insertion sort.

Selection sort

In each iteration, selection sort selects the smallest unsorted element and swaps it into its sorted place.

Selection sort has an important invariant that was introduced called iterative improvement. We keep track of a sorted elements portion at the front of the array and gradually grow the number of sorted elements. Once the sorted elements portion reaches the full length of the array, we’re done sorting the array!

Insertion sort

In each iteration, insertion sort inserts the next unsorted element into the sorted elements portion at the front of the array by swapping it left one index at a time until it is in its correct position. Like selection sort, insertion sort is also an iterative improvement sorting algorithm.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose either SEL or INS from the top navigation bar to switch to selection sort or insertion sort respectively. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization