Lists

This song seems fairly appropriate given what’s going on around us. Jenn Champion is a badass.

public interface SimpleList {
  Object get(int index);
  void set(int index, Object element);
  void add(int index, Object element);
  Object remove(int index);
  int size();
}
public class SimpleArrayList implements SimpleList {
  private Object[] array;

SimpleArrayList(Object[] originalArray) {
    if (originalArray != null) {
      array = new Object[originalArray.length];
      for (int i = 0; i < originalArray.length; i++) {
        array[i] = originalArray[i];
      }
    }
  }
  public Object get(int index) {
    if (index < 0 || index >= array.length) {
      return null;
    }
    return array[index];
  }
  public void set(int index, Object element) {
    if (index < 0 || index >= array.length) {
      return;
    }
    array[index] = element;
  }
  public int size() {
    return array.length;
  }
  public Object remove(int removeIndex) {
    if (removeIndex < 0 || removeIndex >= array.length) {
      return null;
    }

Object toReturn = array[removeIndex];

Object[] newArray = new Object[array.length - 1];
    int originalIndex = 0;
    for (int newIndex = 0; newIndex < newArray.length; newIndex++) {
      if (newIndex == removeIndex) {
        originalIndex++;
      }
      newArray[newIndex] = array[originalIndex];
      originalIndex++;
    }
    array = newArray;
    return toReturn;
  }
  public void add(int addIndex, Object toAdd) {
    return;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleList simpleList = new SimpleArrayList(new Integer[] {1, 2});
    simpleList.add(2, (Integer) 5);
    for (int i = 0; i < simpleList.size(); i++) {
      System.out.println(simpleList.get(i));
    }
  }
}

Lists
> Click or hit Control-Enter to run Example.main above

Algorithm analysis: the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

We’re usually want to analyze an algorithm in the general case, rather than for a specific set of input.

How does the algorithm perform on arbitrarily difficult or large inputs?
What are the best, average, and worst-case running times?
How is the algorithm’s performance related to its inputs?

Big-O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Put another way: we want to estimate what happens as the problem gets really, really hard.

What you have been building on the last few homework problems is a more general data structure called a list.

Lists are an ordered 1 data structure that allow us to:

Get and set values at any index (like an array)
Add or remove values at any index (this is new)
Lists are one of the two data structures you meet in heaven—maps are the other and we’ll get to them in a few weeks

Depending on how we structure data different implementations of the same interface can have different performance characteristics.

We’ll start by looking at this with lists
Lists that store items using arrays have fast (O(1)) lookups but slow (O(n)) modifications
Lists that store items using linked lists have slow lookups (O(n)) but some insertions are fast (O(1))
Both also present different memory usage tradeoffs

interface SimpleList {
  /** Get the object at this index. */
  Object get(int index);
  /** Set the object at this index to the passed element. */
  void set(int index, Object element);
  /** Add the object at the specified location in the list. */
  void add(int index, Object element);
  /** Remove and return the object at the specified location in the list. */
  Object remove(int index);
  /** Return the number of elements in the list. */
  int size();
}

(The official Java one contains a bunch of convenience methods that we don’t want.)

public interface SimpleList {
  Object get(int index);
  void set(int index, Object element);
  void add(int index, Object element);
  Object remove(int index);
  int size();
}
public class SimpleArrayList implements SimpleList {
  private Object[] array;

SimpleArrayList(Object[] originalArray) {
    if (originalArray != null) {
      array = new Object[originalArray.length];
      for (int i = 0; i < originalArray.length; i++) {
        array[i] = originalArray[i];
      }
    }
  }
  public Object get(int index) {
    if (index < 0 || index >= array.length) {
      return null;
    }
    return array[index];
  }
  public void set(int index, Object element) {
    if (index < 0 || index >= array.length) {
      return;
    }
    array[index] = element;
  }
  public int size() {
    return array.length;
  }
  public Object remove(int removeIndex) {
    if (removeIndex < 0 || removeIndex >= array.length) {
      return null;
    }

Object toReturn = array[removeIndex];

Object[] newArray = new Object[array.length - 1];
    int originalIndex = 0;
    for (int newIndex = 0; newIndex < newArray.length; newIndex++) {
      if (newIndex == removeIndex) {
        originalIndex++;
      }
      newArray[newIndex] = array[originalIndex];
      originalIndex++;
    }
    array = newArray;
    return toReturn;
  }
  public void add(int addIndex, Object toAdd) {
    return;
  }
}
public class Example {
  public static void main(String[] unused) {
    SimpleList simpleList = new SimpleArrayList(new Integer[] {1, 2});
    for (int i = 0; i < simpleList.size(); i++) {
      System.out.println(simpleList.get(i));
    }
  }
}

> Click or hit Control-Enter to run Example.main above

Operation ArrayList

Operation	`ArrayList`
`get` and `set`	O(1)
`add` and `remove`	O(n)

get and set

O(1)

add and remove

O(n)

We can make our insertions and removals a bit faster but not copying the entire array each time. How?

Maintain an array that is larger than we need
When we need more space, get a lot more at once
To add or remove just shift items around within the existing array
Note that add and removals are still O(n/2), so O(n)—but not having to allocate memory every time will help
The tradeoff: we will usually have wasted space within our array

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);

public class Item {
  private Object value;
  private Item next;
  Item(Object setValue, Item setNext) {
    value = setValue;
    next = setNext;
  }
}
Item items = new Item((Integer) 0, null);
items = new Item((Integer) 8, items);
items = new Item((Integer) 5, items);

interface SimpleList {
  Object get(int index);
  void set(int index, Object element);
  void add(int index, Object element);
  Object remove(int index);
  int size();
}
public class SimpleLinkedList implements SimpleList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
  private Item start;
}

public class SimpleLinkedList {
  class Item {
    Object value;
    Item next;
    Item(Object setValue, Item setNext) {
      value = setValue;
      next = setNext;
    }
  }
}

In Java we can define a class inside another class.

The example above is known as a nested inner class.
Unlike outer classes, inner classes can be private.
Inner class methods have access to methods and variables in their enclosing class even if they are marked private.
Here we’re using an inner class because the Item class should not be visible outside of the SimpleLinkedList class.

> Click or hit Control-Enter to run Example.main above

public class SimpleLinkedList {
  private Item start;
  public void addToFront(Object 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!

Please provide feedback on how things are going on the forum. How did the quiz go? Is the new office hours system working? Are you staying sane?
The MP3 deadline is this weekend on your deadline day. Good luck finishing up!
Have a great weekend…

Today’s Musical Selections

Review: Algorithm Analysis

Review: At The Limit

Review: Big-O Notation

Review: Big-O Notation

Lists

Data Structure Tradeoffs

Our List Interface

`ArrayList` Operation Performance

`ArrayList` Time v. Space Tradeoffs

Questions About Array Lists?

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Java Inner Classes

`LinkedList`: `addToFront`

Questions About Lists?

Announcements

Today’s Musical Selections

Review: Algorithm Analysis

Review: At The Limit

Review: Big-O Notation

Review: Big-O Notation

Lists

Data Structure Tradeoffs

Our List Interface

ArrayList Operation Performance

ArrayList Time v. Space Tradeoffs

Questions About Array Lists?

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Another Option: Linked Lists

Java Inner Classes

LinkedList: addToFront

Questions About Lists?

Announcements

`ArrayList` Operation Performance

`ArrayList` Time v. Space Tradeoffs

`LinkedList`: `addToFront`