List ADT

OpenDSA

// List class ADT. Generalize the element type using Java Generics.
public interface List<E> { // List class ADT
  // Remove all contents from the list, so it is once again empty
  public void clear();

  // Insert "it" at the current location
  // The client must ensure that the list's capacity is not exceeded
  public boolean insert(E it);

  // Append "it" at the end of the list
  // The client must ensure that the list's capacity is not exceeded
  public boolean append(E it);

  // Remove and return the current element
  public E remove() throws NoSuchElementException;

  // Set the current position to the start of the list
  public void moveToStart();

  // Set the current position to the end of the list
  public void moveToEnd();

  // Move the current position one step left, no change if already at beginning
  public void prev();

  // Move the current position one step right, no change if already at end
  public void next();

  // Return the number of elements in the list
  public int length();

  // Return the position of the current element
  public int currPos();

  // Set the current position to "pos"
  public boolean moveToPos(int pos);

  // Return true if current position is at end of the list
  public boolean isAtEnd();

  // Return the current element
  public E getValue() throws NoSuchElementException;
  
  // Tell if the list is empty or not
  public boolean isEmpty();
}

Java Collections Framework

List Interface

Question…

• What will be printed by each of the following code snippets?

• OpenDSA AList

  List<Integer> numbers = new AList<>();
  
  for (int i = 0; i < 10000; i++) {
    numbers.append(i);
  }
  
  System.out.println(numbers.length());

• java.util.ArrayList

  List<Integer> numbers = new ArrayList<>();
  
  for (int i = 0; i < 10000; i++) {
    numbers.add(i);
  }
  
  System.out.println(numbers.size());

Dynamic Arrays

• Let’s draw a picture…

ArrayList append/add Analysis

• How should we measure the input size?
• Worst case?
• Best case?

ArrayList add Analysis

• How should we measure the input size?
  • Number of elements currently stored.
• Worst case?
  • \(\Theta(n)\)
• Best case?
  • \(\Theta(1)\)

ArrayList add Analysis

• What is the worst-case big-\(\Theta\) running time of this method?

    public static void addNumbers(int n) {
      ArrayList<Integer> nums = new ArrayList<>();
  
      for (int i = 0; i < n; i++) {
          nums.add(i); // Best case Theta(1), worst case Theta(n)
      }
    }

• \(\Theta(n)\)?

• \(\Theta(n^2)\)?

• Somewhere in-between?

Let’s time this to see if that gives any insight…

Reminder… Geometric Series

• \[\sum_{i=0}^{n} r^i = \frac{1-r^{n+1}}{1-r} \]
• \(r = 2\) is a common case…
• \[\sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]

Socrative Quiz (Summation Review)

• \[\sum_{i=0}^{n} 2^i = 2^{n+1} - 1 \]
• \[\sum_{i=1}^{n} 2^i = ?? \] A. \(2^{n+2} - 1\)
  B. \(2^{n+1} - 2\)
  C. \(2^{n} - 1\)
  D. \(2^{n}\)
  

Cost of Append in Dynamic Array

• Select array assignments as the basic operation.

• We want an amortized analysis… Average cost of the operation over a sequence of operations.

• This table shows the total and average cost after \(n\) appends:

• \(n\)	assignment cost	resize cost	total	average
  1	1	0	1	1
  2	1	1	3	1.5
  3	1	2	6	2
  4	1	0	7	1.75
  5	1	4	12	2.4
  6	1	0	13	2.167
  7	1	0	14	2
  8	1	0	15	1.875
  9	1	8	24	2.667
  …	…	…	…	…

• Total assignments equal to: \[ n + \sum_{i=0}^{\lceil \log_2 n \rceil-1} 2^{i} \]

Solving the Summation

\[ \begin{aligned} n + \sum_{i=0}^{\lceil \log_2 n \rceil-1} 2^{i} &=n + 2^{\lceil \log_2 n \rceil-1+1} - 1\\ &=n + 2^{\lceil \log_2 n \rceil} - 1 \\ &\leq n + 2^{ \log_2 n +1} - 1 \\ & = n + 2n - 1\\ &= 3n - 1 \leq 3n \end{aligned} \]

Amortized cost of append

• Total assignments for \(n\) appends is \(\leq 3n\).
• Average cost across \(n\) appends is \(\leq \frac{3n}{n} = 3\)
• Amortized cost of append is \(\Theta(1)\)

Socrative Quiz…

You are performing a code review on the following Java method. This is part of the software that manages an automobile’s safety features. loggingList is an ArrayList that stores log messages that will eventually be saved to persistent storage. Which of the following is the most appropriate evaluation of this code?

public static void respondToCollision(Area area) {

    loggingList.add("Airbag Depolyed!");
    if (area == Area.FRONT)
        deployAirbag();
}

1. LGTM
2. Spelling error in log message.
3. area == Area.FRONT should be area.equals(Area.FRONT)
4. Efficiency issues could lead to loss of life.
5. Problem with code style: Missing braces after if.

Bankers View (informal)

• Claim: Any sequence of \(n\) appends will require no more than \(3n\) assignments.
• We imagine that on every non-expanding append we deposit 3 coins
  • One is used to pay for the required assignment
  • Two are set aside for a rainy day
• When an expansion is required we pay for it with coins we saved earlier. Will there be enough?
• We have two coins for every append since the last expand
  • After the previous expand, half the space was empty
  • Each time we appended, we deposited two coins
  • Half the entries have two coins: enough for one coin per entry
  • These will “pay” for moving all entries to the new array

What about insert (not append)?

• Worst case? (When does the worst case happen?)
  • Insertion at the beginning with resize.
  • \(\Theta(n)\)
• Amortized worst case?
  • A series of \(n\) insertions at the beginning
  • Still \(\Theta(n)\)